Putnam 2003, Problem B-3

Show that for each positive integer \( n \),
\[
n! = \prod_{i=1}^n \text{lcm}\{1, 2, \ldots, \lfloor n/i \rfloor\}.
\]
(Here lcm denotes the least common multiple, and \( \lfloor x \rfloor \) denotes the greatest integer \( \leq x \).)

Solution:
### First solution:  
It is enough to show that for each prime \( p \), the exponent of \( p \) in the prime factorization of both sides is the same. On the left side, it is well-known that the exponent of \( p \) in the prime factorization of \( n! \) is  
\[
\sum_{i=1}^n \left\lfloor \frac{n}{p^i} \right\rfloor.
\]  
(To see this, note that the \( i \)-th term counts the multiples of \( p^i \) among \( 1, \ldots, n \), so that a number divisible exactly by \( p^i \) gets counted exactly \( i \) times.) This number can be reinterpreted as the cardinality of the set \( S \) of points in the plane with positive integer coordinates lying on or under the curve \( y = n p^{-x} \): namely, each summand is the number of points of \( S \) with \( x = i \).  

On the right side, the exponent of \( p \) in the prime factorization of \( \text{lcm}(1, \ldots, \lfloor n/i \rfloor) \) is \( \lfloor \log_p \lfloor n/i \rfloor \rfloor = \lfloor \log_p (n/i) \rfloor \). However, this is precisely the number of points of \( S \) with \( y = i \). Thus  
\[
\sum_{i=1}^n \left\lfloor \log_p \left\lfloor \frac{n}{i} \right\rfloor \right\rfloor = \sum_{i=1}^n \left\lfloor \frac{n}{p^i} \right\rfloor,
\]  
and the desired result follows.  


### Second solution:  
We prove the result by induction on \( n \), the case \( n = 1 \) being obvious. What we actually show is that going from \( n - 1 \) to \( n \) changes both sides by the same multiplicative factor, that is,  
\[
n = \prod_{i=1}^{n-1} \frac{\text{lcm}\{1,2,\ldots,\lfloor n/i \rfloor\}}{\text{lcm}\{1,2,\ldots,\lfloor (n-1)/i \rfloor\}}.
\]  
Note that the \( i \)-th term in the product is equal to 1 if \( n/i \) is not an integer, i.e., if \( n/i \) is not a divisor of \( n \). It is also equal to 1 if \( n/i \) is a divisor of \( n \) but not a prime power, since any composite number divides the lcm of all smaller numbers. However, if \( n/i \) is a power of \( p \), then the \( i \)-th term is equal to \( p \).  

Since \( n/i \) runs over all proper divisors of \( n \), the product on the right side includes one factor of the prime \( p \) for each factor of \( p \) in the prime factorization of \( n \). Thus the whole product is indeed equal to \( n \), completing the induction.