We evaluate a sum involving floor functions of fractions. This problem is adapted from an exercise in Graham, Knuth, and Patashnik's Concrete Mathematics.
Integers modulo m as a group: https://en.wikipedia.org/wiki/Cyclic_group#Integer_and_modular_addition
Lagrange's Theorem: https://en.wikipedia.org/wiki/Lagrange%27s_theorem_(group_theory)
Size of subgroups: https://proofwiki.org/wiki/Order_of_Subgroup_of_Cyclic_Group
00:00 Removing the floor functions
02:03 Removing the fractional parts
04:05 Exploring through examples
06:49 Generalising the pattern
07:54 More rigorous approach (outline)
08:30 Evaluating the sum
10:20 Bonus corollary
0 Comments