Maths Olympiad Prep

Library / /27 of 136

Number theory Difficulty 7.6 National Olympiad, round 2 Prove it 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.

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.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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