Number theoryDifficulty 7.6Prove itIMO Hk TST · Hong Kong
Prove that there are infinitely many positive integers n such that 2n+1 is divisible by n. Find all such n'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.
All integers n=3k with k∈Z+ satisfy n∣2n+1. Indeed, since 3∣2+1, by the lifting the exponent lemma, we have v3(23k+13k)=v3(2+1)+v3(3k)=1+k. This implies 3k+1∣2n+1, and hence n∣2n+1.
The only prime number n satisfying n∣2n+1 is n=3. Indeed, let n=p be a prime. By the Fermat little theorem, we have 2p+1≡2+1=3(modp). This is congruent to 0 modulo p if and only if p∣3, i.e. p=3.
Source: MathNet,
licensed CC-BY-4.0.
Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.