Difference between revisions of "2007 USAMO Problems/Problem 5"
m (wik) |
Roadnottaken (talk | contribs) (I removed the "Solution 1" heading from the middle of the solution.~~~~) |
||
Line 11: | Line 11: | ||
Now we assume the result holds for <math>\displaystyle{n}</math>. Note that <math>\displaystyle{a_{n}}</math> satisfies the [[recursion]] | Now we assume the result holds for <math>\displaystyle{n}</math>. Note that <math>\displaystyle{a_{n}}</math> satisfies the [[recursion]] | ||
− | |||
<div style="text-align:center;"><math>\displaystyle{a_{n+1}= (a_{n}-1)^{7}+1} = a_{n}\left(a_{n}^{6}-7(a_{n}-1)(a_{n}^{2}-a_{n}+1)^{2}\right)</math></div> | <div style="text-align:center;"><math>\displaystyle{a_{n+1}= (a_{n}-1)^{7}+1} = a_{n}\left(a_{n}^{6}-7(a_{n}-1)(a_{n}^{2}-a_{n}+1)^{2}\right)</math></div> | ||
Revision as of 17:19, 2 May 2007
Problem
Prove that for every nonnegative integer , the number is the product of at least (not necessarily distinct) primes.
Contents
[hide]Solution
We prove the result by induction.
Let be . 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.
See also
2007 USAMO (Problems • Resources) | ||
Preceded by Problem 4 |
Followed by Problem 6 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |