Difference between revisions of "1982 USAMO Problems/Problem 4"
(→Solution: Essentially chooses Fermat Numbers until We get to a composite one, 1+1/2+...+1/32+1/64+1/64=1, will write motivation soon) |
(Removed Solution 1 (nonsense); revised the structure and presentation of Solution 2 (own)) |
||
(3 intermediate revisions by the same user not shown) | |||
Line 2: | Line 2: | ||
Prove that there exists a positive integer <math>k</math> such that <math>k\cdot2^n+1</math> is composite for every integer <math>n</math>. | Prove that there exists a positive integer <math>k</math> such that <math>k\cdot2^n+1</math> is composite for every integer <math>n</math>. | ||
− | == Solution | + | == Solution == |
+ | Indeed, <math>\boxed{k=2935363331541925531}</math> has the requisite property. | ||
− | + | To see why, consider the primes <math>3,\ 5,\ 17,\ 257,\ 65537,\ 6700417,\ 641</math>, and observe that <cmath>\begin{align*}k&\equiv 1\pmod{3}\\ k&\equiv 1\pmod{5}\\ k&\equiv 1\pmod{17}\\ k&\equiv 1\pmod{257}\\ k&\equiv 1\pmod{65537}\\ k&\equiv 1\pmod{6700417}\\ k&\equiv -1\pmod{641}\end{align*}</cmath> | |
− | == | + | Moreover, <cmath>\begin{align*}\text{ord}_{3}\left(2\right)&=2\\ \text{ord}_{5}\left(2\right)&=4\\ \text{ord}_{17}\left(2\right)&=8\\ \text{ord}_{257}\left(2\right)&=16\\ \text{ord}_{65537}\left(2\right)&=32\\ \text{ord}_{6700417}\left(2\right)&=64\\ \text{ord}_{641}\left(2\right)&=64\end{align*}</cmath> |
− | |||
− | + | We conclude that <cmath>\begin{align*}n\equiv 1\pmod{2}&\implies k\cdot 2^{n}-1\equiv k\cdot\left(-1\right)+1\equiv 0\pmod{3}\\ n\equiv 2\pmod{4}&\implies k\cdot 2^{n}-1\equiv k\cdot\left(-1\right)+1\equiv 0\pmod{5}\\ n\equiv 4\pmod{8}&\implies k\cdot 2^{n}-1\equiv k\cdot\left(-1\right)+1\equiv 0\pmod{17}\\ n\equiv 8\pmod{16}&\implies k\cdot 2^{n}-1\equiv k\cdot\left(-1\right)+1\equiv 0\pmod{257}\\ n\equiv 16\pmod{32}&\implies k\cdot 2^{n}-1\equiv k\cdot\left(-1\right)+1\equiv 0\pmod{65537}\\ n\equiv 32\pmod{64}&\implies k\cdot 2^{n}-1\equiv k\cdot\left(-1\right)+1\equiv 0\pmod{6700417}\\ n\equiv 0\pmod{64}&\implies k\cdot 2^{n}-1\equiv k\cdot1+1\equiv 0\pmod{641}\end{align*}</cmath> | |
− | + | And <math>k>>3,5,17,257,65537,6700417,641</math> so the relevant values will, in fact, always be composite. <math>\blacksquare</math> | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | And | ||
− | |||
− | |||
== See Also == | == See Also == |
Latest revision as of 01:15, 4 June 2021
Problem
Prove that there exists a positive integer such that
is composite for every integer
.
Solution
Indeed, has the requisite property.
To see why, consider the primes , and observe that
Moreover,
We conclude that
And so the relevant values will, in fact, always be composite.
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.