2007 USAMO Problems/Problem 5
Contents
[hide]Problem
(Titu Andreescu) Prove that for every nonnegative integer , the number is the product of at least (not necessarily distinct) primes.
Solutions
Solution 1
The proof is by induction. The base is provided by the case, where . To prove the inductive step, it suffices to show that if for some positive integer then is composite. As a consequence, has at least two more prime factors than does . To confirm that is composite, observe that Also each factor exceeds 1. It suffices to check the smaller one; gives Hence is composite and the proof is complete.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
See also
- <url>viewtopic.php?t=145849 Discussion on AoPS/MathLinks</url>
2007 USAMO (Problems • Resources) | ||
Preceded by Problem 4 |
Followed by Problem 6 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.