2007 USAMO Problems/Problem 5
Prove that for every nonnegative integer , the number is the product of at least (not necessarily distinct) primes.
Let be . We prove the result by induction.
The result holds for because is the product of primes. Now we assume the result holds for . Note that satisfies the recursion
Since is an odd power of , is a perfect square. Therefore is a difference of squares and thus composite, i.e. it is divisible by primes. By assumption, is divisible by primes. Thus is divisible by primes as desired.
|2007 USAMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5 • 6|
|All USAMO Problems and Solutions|