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
If
is a multiple of
, then, for some integer
,
This simplifies to
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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.