Maths Olympiad Prep

Track / Stage 7 / 172 of 300 #2052 of 2444

Problem 2052

National Olympiad second round; IMO P1/P4
Number theory Difficulty 7.6 Prove it IMO Hk TST · Hong Kong

Prove that there are infinitely many positive integers nn such that 2n+12^n + 1 is divisible by nn. Find all such nn's that are prime numbers.

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.

Next problem →

Official solution

All integers n=3kn = 3^k with kZ+k \in \mathbb{Z}^+ satisfy n2n+1n \mid 2^n + 1. Indeed, since 32+13 \mid 2 + 1, by the lifting the exponent lemma, we have
v3(23k+13k)=v3(2+1)+v3(3k)=1+k. v_3(2^{3^k} + 1^{3^k}) = v_3(2 + 1) + v_3(3^k) = 1 + k.
This implies 3k+12n+13^{k+1} \mid 2^n + 1, and hence n2n+1n \mid 2^n + 1.

The only prime number nn satisfying n2n+1n \mid 2^n + 1 is n=3n = 3. Indeed, let n=pn = p be a prime. By the Fermat little theorem, we have
2p+12+1=3(modp). 2^p + 1 \equiv 2 + 1 = 3 \pmod{p}.
This is congruent to 00 modulo pp if and only if p3p \mid 3, i.e. p=3p = 3.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.