Show that $2^q\equiv 1$ mod p

Question

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.

Answer 1

• 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