1982 USAMO Problems/Problem 4

Problem

Prove that there exists a positive integer $k$ such that $k\cdot2^n+1$ is composite for every integer $n$ .

Solution

Indeed, $\boxed{k=2935363331541925531}$ has the requisite property.

To see why, consider the primes $3,\ 5,\ 17,\ 257,\ 65537,\ 6700417,\ 641$ , and observe that $\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*}$

Moreover, $\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*}$

We conclude that $\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*}$

And $k>>3,5,17,257,65537,6700417,641$ so the relevant values will, in fact, always be composite. $\blacksquare$

1982 USAMO (Problems • Resources)
Preceded by Problem 3	Followed by Problem 5
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions

Page

Toolbox

Search

1982 USAMO Problems/Problem 4

Problem

Solution

See Also