2
$\begingroup$

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.

|cite|improve this question
$\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$

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.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.