Given $p=33179$ and $2^{2p+1}\equiv 2\; \pmod{2p+1}$, deduce $2p+1$ is prime.
All I can think of is using Fermat's little theorem: $2^{2p}\equiv 1\pmod{2p+1}$ which just tells me it may be prime.
Given $p=33179$ and $2^{2p+1}\equiv 2\; \pmod{2p+1}$, deduce $2p+1$ is prime.
All I can think of is using Fermat's little theorem: $2^{2p}\equiv 1\pmod{2p+1}$ which just tells me it may be prime.
Note that $2^{\varphi(2p+1)}\equiv 1\pmod{2p+1}$. It follows that the order of $2$ modulo $2p+1$ is a common divisor of $\varphi(2p+1)$ and $2p$.
The order of $2$ modulo $2p+1$ is obviously greater than $2$, so $p$ divides $\varphi(2p+1)$. But if $2p+1$ is composite, then it is a product of primes that are all less than $p$. In that case, $p$ cannot be a factor of $\varphi(2p+1)$. Thus $2p+1$ must be prime.