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

Let $p$ be a prime number that divides $2^y-1$ and $x$ be a whole number less than $y$ such that $k\equiv -1\cdot2^{y-x}\pmod{p}$ If $n-x$ is a multiple of $y$ , then, for some integer $r$ , $k\cdot2^{n}\equiv-1\cdot2^{y-x}\cdot2^{x+ry}\pmod{p}$ This simplifies to $k\cdot2^{n} \equiv -1\pmod{p}$ This implies that $k\cdot2^{n}+1\equiv 0 \pmod{p}$ . Thus we conclude that there exists an integer $k$ such that $k\cdot2^{n}+1$ is composite for all integral $n$ .

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