Problem
NT-B2-M03-P009 Primes from \(2^p+1\)
#9
★★★☆☆ Level 3 of 5
Find all primes \(p\) such that \(p\mid2^p+1\).
For odd \(p\), use \(2^p\equiv2\pmod p\).
For \(p=2\), there is no divisibility. If \(p\) is odd, Fermat's little theorem gives \(2^p\equiv2\pmod p\). Then \(2^p+1\equiv3\pmod p\), so \(p\mid3\), hence \(p=3\). Check: \(2^3+1=9\) is divisible by \(3\).
The problem looks exponential, but is solved by a short cycle modulo a prime.