EulerFermatTheorem Challenging

Problem - 4239

Let $p$ be an odd prime, and $n=\frac{2^{2p}-1}{3}$ in an integer. Prove $2^{n-1}\equiv 1\pmod{n}$.


The given condition yields $$n-1=\frac{2^{2p}-4}{3}\implies 3\times(n-1)=4\times (2^{p-1}+1)(2^{p-1}-1)$$

Because $p$ is an odd prime, Fermat's little theorem gives $2^{p-1}\equiv 1\pmod{p}$, or $p\mid(2^{p-1}-1)$. Then, the right side of the above equation must be a multiple of $2p$. But because $p$ is prime, $2p$ cannot be divisible by $3$. Hence, it must hold that $$2p\mid(n-1)\implies\quad (2^{2p}-1)\mid(2^{n-1}-1)$$

Meanwhile, the given condition implies $n\mid (2^{2p}-1)$. Therefore it must be true that $n\mid(2^{n-1}-1)$ or $2^{n-1}\equiv 1\pmod{n}$.

report an error