Let $p=2q+1$ and $q$ be prime numbers, with $q\equiv 3\:(4)$. Show that $2^q\equiv 1\:(p)$.

So far I've tried to write $q$ as an expression of $p$ and I am assuming that I have to use little Fermat somehow, since $p$ is prime. But I can't figure out how to combine those two and I fail to see an alternative. I also don't see how to use the fact that $q\equiv 3\:(4)$.

I've also tried rewriting the equation to $2^q-1\equiv 0\:(p)$ from which I need to show that $p=2q+1|2^q-1$. But I also got stuck there.

Any help is appreciated.

  • Since $q\equiv 3\pmod{4}\implies p\equiv 7\pmod{8}$

  • You have to show $2^{\frac{p-1}{2}}\equiv 1\pmod{p}$

  • Note that $\left(\frac{2}{p}\right)\equiv 2^{\frac{p-1}{2}}\pmod{p}$ is $1$ if $p\equiv \pm{1}\pmod{8}$ and $-1$ if $p\equiv \pm{3}\pmod{8}$. Here $\left(\frac{a}{p}\right)$ denotes the Legendre Symbol and i have used Euler's criterion which says $\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\pmod{p}$.

  • From Apostol's Analytic Number Theory Book this proof

  • $\begingroup$ Is there a way to prove this without the use of the Legendre Symbol? I understand what you did and what it means, just wondering if there's a way without it. $\endgroup$ – SirCircle Oct 8 at 13:16
  • 1
    $\begingroup$ I have added the screen shot. Hope it helps :) $\endgroup$ – crskhr Oct 8 at 15:22

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.