2000 IMO Problems/Problem 5

Does there exist a positive integer $n$ such that $n$ has exactly 2000 prime divisors and $n$ divides $2^n + 1$ ?

Solution

Let $N=2^n+1$ . We will assume for the sake of contradiction that $n|N$ .

$2^n+1 \equiv 0$ (mod $n$ ) $\Rightarrow 2^n \equiv -1$ (mod $n$ ). So 2 does not divide $n$ , and so $n$ is odd.

Select an arbitrary prime factor of $n$ and call it $p$ . Let's represent $n$ in the form $p^am$ , where $m$ is not divisible by $p$ .

Note that $p$ and $m$ are both odd since $n$ is odd. By repeated applications of Fermat's Little Theorem:

$N = 2^n+1 = 2^{p^am} + 1 = (2^{p^{a-1}m})^p + 1 \equiv 2^{p^{a-1}m} + 1$ (mod $p$ )

Continuing in this manner, and inducting on k from 1 to $a$ ,

$2^{p^{a-k}m}+1 \equiv (2^{p^{a-k-1}m})^p + 1$ (mod $p$ ) $\equiv 2^{p^{a-k-1}m} + 1$ (mod $p$ )

So we have $N \equiv 2^m+1$ (mod $p$ )

Since $p$ is relatively prime to $m$ , $N \equiv 1+1$ (mod $p$ ) $\equiv 2$ (mod $p$ )

Since $p$ is odd, $N$ is not divisible by $p$ . Hence $N$ is not divisible by $n$ . So we have a contradiction, and our original assumption was false, and therefore $N$ is still not divisible by $n$ .

Page

Toolbox

Search

2000 IMO Problems/Problem 5

Solution