Show that ∏i=1n lcm(1, 2, 3, ... , [n/i]) = n!.
The power of p dividing n! is [n/p] + [n/p2] + [n/p3] + ... (the multiples of p each contribute one, then the multiples of p2 each contribute another one and so on.
The power of p dividing lcm(1, 2, 3, ... , k) is m where pm ≤ k < pm+1. So the power of p dividing lcm(1, 2, ... , [n/i]) is m where pm ≤ n/i < pm+1 or n/pm+1 < i ≤ n/pm. There are [n/pm] - [n/pm+1] such i. So the total power of p is ∑ m([n/pm] - [n/pm+1]) = ∑ m[n/pm] - ∑(m-1)[n/pm] = ∑ [n/pm], which is the same.
64th Putnam 2003
© John Scholes
8 Dec 2003
Last corrected/updated 8 Dec 03