Let $q>3$ be an odd prime and let $q=2Q+1$. Prove that:
(a) $q\,|\,(3^Q-1) \iff q\equiv ±1 \pmod {12}$
adpated from Number Theory with Applications, James A. Anderson, James M. Bell. Ch 3.9 Q12 (a)
Any hint from the question? Thanks.
Edit 1: (DELETED BECAUSE IT IS WRONG) Edit 2: I have proved for the one-sided statement. Let me put it here first and wait for me to prove the another side of statement
Lemma 1: Iff $\exists x \in \mathbb{Z}^+, x>3: x^2\equiv 3 \pmod {p}$, then $p\equiv\pm1 \pmod{12}$
Proof:
Forward Statement:
By quadratic reciprocity, $(\frac{p}{3})=(\frac{3}{p})(-1)^{\frac{p-1}{2} \frac{3-1}{2}}=(-1)^{\frac{p-1}{2}}$
For $y^2\equiv p \pmod{3}$,
Case 1: If $(\frac{p}{3})=0$, then $3 \mid p \Rightarrow p \equiv 0 \pmod{3}$
Case 2: If $(\frac{p}{3})=1$, then by Fermat little thm, $y^2 \equiv 1 \pmod{3}$, $\therefore p \equiv 1 \pmod{3}$
On the other hand, $1=(-1)^{\frac{p-1}{2}} \Rightarrow p$ is even.
$\therefore$ By Chinese Remainder theorem, $p \equiv 1 \pmod{12}$
Case 3: If $(\frac{p}{3})=-1$, then $y^2 \equiv 2 \pmod{3}$, $\therefore p \equiv 2 \pmod{3}$
On the other hand, $-1=(-1)^{\frac{p-1}{2}}$
$\therefore \exists t \in \mathbb{Z}^+: \frac{p-1}{2} = 2t+1 \Rightarrow p-1=4t+2\Rightarrow p=4t+3\Rightarrow p\equiv 3 \pmod{4}$
By Chinese Remainder theorem, $p \equiv 11 \pmod{12}$
Combining the latter two cases, $p \equiv \pm 1 \pmod{12}$
Edit 3: Here is the proof of backward statement:
If $p$ is an odd prime, then $(\frac{p}{3}) \equiv p \pmod{3}$
Case 1: $p\equiv 1 \pmod{12} \Rightarrow p\equiv 1 \pmod{3}, \therefore (\frac{p}{3})=1$
Also, $\exists \alpha \in \mathbb{Z}^+: p-11=12 \alpha \Rightarrow p=12\alpha +11$
$(\frac{3}{p})=(\frac{p}{3}) (-1)^{\frac{p-1}{2}}=1(-1)^{\frac{12t}{2}}=1$
Case 2: $p\equiv 11 \pmod{12} \Rightarrow p\equiv -1 \pmod{3}, \therefore (\frac{p}{3})=-1$
$\therefore \exists \beta \in \mathbb{Z}^+ : p-11=12 \beta \Rightarrow p=12\beta +11$
$(\frac{3}{p})=(\frac{p}{3})(-1)^{\frac{12\beta+11-1}{2}}=(-1)(-1)=1$
Combining the above two cases, $(\frac{p}{3}) = 1$
Edit 4:
There are two cases: $q \equiv 1 \pmod{4}$ and $q\equiv 3 \pmod{4}$:
Case 1: $q \equiv 1 \pmod{4} \Rightarrow (\frac{q}{3}) = (\frac{3}{q})(-1)^{\frac{q-1}{2}} = 1, \therefore q\equiv 1 \pmod{3}$
$\therefore$ By Chinese Remainder thm, $q \equiv 1 \pmod{12}$
Case 2: $q \equiv 3 \pmod{4} \Rightarrow (\frac{q}{3}) = -1, \therefore q \equiv 2 \pmod{3}$
$\therefore$ By Chinese Remainder thm, $q \equiv 11 \pmod{12}$
(The converse way is similar to that in edit 3).
(Edit 5: I changed the above from "statement" to "lemma 1")
Edit 5:
By using Lemma 1,
$(\frac{3}{q}) = 1 \Leftrightarrow (\frac{3}{q}) \equiv 3^{\frac{p-1}{2}} \pmod{q} \Leftrightarrow 1 \equiv 3^{\frac{q-1}{2}} \pmod{q}$
$\therefore$ The thm is proved.