Difference between revisions of "2007 USAMO Problems/Problem 5"
m (→Solution) |
Hamster1800 (talk | contribs) (Moved the solution to above the box) |
||
Line 4: | Line 4: | ||
== Solution == | == Solution == | ||
− | |||
− | |||
Let <math>\displaystyle{a_{n}}</math> be <math>7^{7^{n}}+1</math>. We prove the result by induction. | Let <math>\displaystyle{a_{n}}</math> be <math>7^{7^{n}}+1</math>. We prove the result by induction. | ||
Line 16: | Line 14: | ||
Since <math>\displaystyle{a_n - 1}</math> is an odd power of <math>\displaystyle{7}</math>, <math>\displaystyle{7(a_n-1)}</math> is a perfect square. Therefore <math>\displaystyle{a_{n}^{6}-7(a_{n}-1)(a_{n}^{2}-a_{n}+1)^{2}}</math> is a difference of squares and thus composite, i.e. it is divisible by <math>\displaystyle{2}</math> primes. By assumption, <math>\displaystyle{a_n}</math> is divisible by <math>\displaystyle{2n + 3}</math> primes. Thus <math>\displaystyle{a_{n+1}}</math> is divisible by <math>\displaystyle{2+ (2n + 3) = 2(n+1) + 3}</math> primes as desired. | Since <math>\displaystyle{a_n - 1}</math> is an odd power of <math>\displaystyle{7}</math>, <math>\displaystyle{7(a_n-1)}</math> is a perfect square. Therefore <math>\displaystyle{a_{n}^{6}-7(a_{n}-1)(a_{n}^{2}-a_{n}+1)^{2}}</math> is a difference of squares and thus composite, i.e. it is divisible by <math>\displaystyle{2}</math> primes. By assumption, <math>\displaystyle{a_n}</math> is divisible by <math>\displaystyle{2n + 3}</math> primes. Thus <math>\displaystyle{a_{n+1}}</math> is divisible by <math>\displaystyle{2+ (2n + 3) = 2(n+1) + 3}</math> primes as desired. | ||
+ | |||
+ | {{USAMO newbox|year=2007|num-b=4|num-a=6}} |
Revision as of 21:44, 25 April 2007
Problem
Prove that for every nonnegative integer , the number is the product of at least (not necessarily distinct) primes.
Solution
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) | ||
Preceded by Problem 4 |
Followed by Problem 6 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |