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.
2
$\begingroup$
$\endgroup$
-
$\begingroup$ For some reason this reminds me of some theorem involving Mersenne numbers, but I think there were some extra conditions... $\endgroup$ – abiessu Apr 15 '16 at 0:16
-
$\begingroup$ On the "Mersenne" note, you have $(2^p-1)(2^p+1)\equiv 0\pmod {2p+1}$ since $2^{-1}\pmod{2p+1}$ exists. $\endgroup$ – abiessu Apr 15 '16 at 0:21
-
$\begingroup$ @abiessu (not sure but) : the Mersenne numbers also say that if $p$ is prime and $2^p-1$ is not prime, then $2^p-1$ is divisible by $2kp+1$ for some $k$, and that its lowest divisor (which is prime) has this form. here $2^{2p}-1 = (2^p-1)(2^p+1)$ is divisible by $2p+1$, if you prove that $gcd(2p+1,2^p+1) = 1$ then $2^p-1$ is divisible by $2p+1$, and this is clearly the lowest $2kp+1$ dividing $2^p-1$, hence it is prime. $\endgroup$ – reuns Apr 15 '16 at 0:27
-
$\begingroup$ I'll note that this question does not require knowledge of Mersenne primes $\endgroup$ – George Apr 15 '16 at 0:32
-
$\begingroup$ that doesn't require any knowledge on the Lucas Lehmer test, only that if $q$ prime divides $2^p-1$ with $p$ prime then $q = 2kp+1$. $\endgroup$ – reuns Apr 15 '16 at 0:33
9
$\begingroup$
$\endgroup$
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.
answered Apr 15 '16 at 0:38
