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

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}$$.