Track / Stage 5 / 123 of 400 #723 of 1964

Problem 723

AIME late

Number theory Difficulty 5.3 Prove it

(Canada, 1983). Let $p$ be a prime number. Show that there are infinitely many integers $n$ such that $p$ divides $2^{n}-n$ .

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

. If $p=2$ , all even numbers work. If $p>2$ , we have $2^{p-1} \equiv 1$ modulo $p$ . We deduce that for $n=(k p-1)(p-1)$ , where $k$ is any positive integer, $2^{n}$ and $n$ are both congruent to 1 modulo $p$ .

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.