Difference between revisions of "1982 USAMO Problems/Problem 4"
| Line 3: | Line 3: | ||
== Solution == | == Solution == | ||
| − | {{ | + | |
| + | Let <math>p</math> be a prime number that divides <math>2^y-1</math> and <math>x</math> be a whole number less than <math>y</math> such that <cmath>k\equiv -1\cdot2^{y-x}\pmod{p}</cmath> If <math>n-x</math> is a multiple of <math>y</math>, then, for some integer <math>r</math>, <cmath>k\cdot2^{n}\equiv-1\cdot2^{y-x}\cdot2^{x+ry}\pmod{p}</cmath> This simplifies to <cmath>k\cdot2^{n} \equiv -1\pmod{p}</cmath> This implies that <math>k\cdot2^{n}+1\equiv 0 \pmod{p}</math>. Thus we conclude that there exists an integer <math>k</math> such that <math>k\cdot2^{n}+1</math> is composite for all integral <math>n</math>. | ||
== See Also == | == See Also == | ||
Revision as of 14:47, 6 August 2013
Problem
Prove that there exists a positive integer 
such that 
is composite for every integer 
.
Solution
Let 
be a prime number that divides 
and 
be a whole number less than 
such that ![\[k\equiv -1\cdot2^{y-x}\pmod{p}\]](http://latex.artofproblemsolving.com/6/3/c/63c413fb0c02c520d2186620ba38f47cc5b76ac5.png)
If 
is a multiple of , then, for some integer 
, ![\[k\cdot2^{n}\equiv-1\cdot2^{y-x}\cdot2^{x+ry}\pmod{p}\]](http://latex.artofproblemsolving.com/3/7/b/37b9797a8c2c22a344a5592298a41934f427c391.png)
This simplifies to ![\[k\cdot2^{n} \equiv -1\pmod{p}\]](http://latex.artofproblemsolving.com/5/5/7/557efbc414345f3d7edad64dce22d8adc14fcb8b.png)
This implies that 
. Thus we conclude that there exists an integer such that 
is composite for all integral .
See Also
| 1982 USAMO (Problems • Resources) | ||
| Preceded by Problem 3 |
Followed by Problem 5 | |
| 1 • 2 • 3 • 4 • 5 | ||
| All USAMO Problems and Solutions | ||
These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. 
