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

More generally, we will prove by induction on $k$ that for each $k\in\mathbb{N}$ there exists $n_k\in\mathbb{N}$ that has exactly $k$ distinct prime divisors such that $n_k\mid 2^{n_k}+1\qquad\text{and}\qquad 3\nmid n_k.$

$\textbf{Proof}$
For $k=1$ we may take $n_1=3$ , which clearly satisfies the conditions.

Assume the claim holds for some $k\ge1$ and write $n_k=3^a m$ with $3\nmid m$ , so that $m$ has exactly $k-1$ distinct prime divisors. Then $3n_k=3^{a+1}m$ has exactly $k$ prime divisors and $2^{3n_k}+1 = (2^{n_k}+1)\left(2^{2n_k}-2^{n_k}+1\right),$ so $3n_k\mid 2^{3n_k}+1$ because $3\mid 2^{2n_k}-2^{n_k}+1$ .

We shall now find a prime $p\nmid n_k$ such that $p\mid 2^{3n_k}+1$ but $p\nmid 2^{n_k}+1$ . Setting $n_{k+1}=3^a p n_k$ then produces a number with exactly $k+1$ distinct prime divisors satisfying the required divisibility.

It remains to show that for every integer $a>2$ there exists a prime divisor of $a^3+1=(a+1)(a^2-a+1)$ which does not divide $a+1$ . Observe that $\gcd(a^2-a+1,\;a+1)=\gcd(3,\;a+1).$ If $3\nmid (a+1)$ , then $3$ divides $a^3+1$ but not $a+1$ , so we may take $p=3$ . Otherwise $a+1\equiv0\pmod3$ , so $a=3b-1$ and $a^2-a+1=9b^2-9b+3=3(3b^2-3b+1),$ and the factor $3b^2-3b+1$ is not divisible by $3$ . Hence $a^2-a+1$ has a prime divisor different from $3$ , and any such prime divisor $p$ divides $a^3+1$ but not $a+1$ . This completes the induction.

$\blacksquare$

2000 IMO (Problems) • Resources
Preceded by Problem 4	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 6
All IMO Problems and Solutions

Page

Toolbox

Search

2000 IMO Problems/Problem 5

Solution

See Also