64th Putnam 2003

Show that ∏_i=1ⁿ lcm(1, 2, 3, ... , [n/i]) = n!.

Solution

The power of p dividing n! is [n/p] + [n/p²] + [n/p³] + ... (the multiples of p each contribute one, then the multiples of p² each contribute another one and so on.

The power of p dividing lcm(1, 2, 3, ... , k) is m where p^m ≤ k < p^m+1. So the power of p dividing lcm(1, 2, ... , [n/i]) is m where p^m ≤ n/i < p^m+1 or n/p^m+1 < i ≤ n/p^m. There are [n/p^m] - [n/p^m+1] such i. So the total power of p is ∑ m([n/p^m] - [n/p^m+1]) = ∑ m[n/p^m] - ∑(m-1)[n/p^m] = ∑ [n/p^m], which is the same.

64th Putnam 2003

© John Scholes
jscholes@kalva.demon.co.uk
8 Dec 2003
Last corrected/updated 8 Dec 03