# Is my solution of elementary number theory question correct?

Question:

Let $p$ be a prime and let $q$ be an odd prime dividing $\frac{(3^p − 1)}{2}$. Show that $q \equiv 1 (\bmod p)$.

My attempt:

$\frac{3^p - 1}{2} = kq \to 3^p - 1 = 2kq \to 3^p=2kq + 1 \to 3^{p-1}*3^1 = 2kq + 1$

Using Fermat's little theorem: $3^{p-1} \equiv 1 (\bmod p)$ because: $\gcd(3, p) = 1$

Thus: $(3^{p-1}*3^1 = 2kq + 1) \bmod p \to (3 = 2kq + 1) \bmod p \to q = \frac{2}{2} \equiv 1 (\bmod p)$

Am I correct? any help would be appreciated.

• It's a little hard to tell what happened to $k$ in that last step. I see why $2kq\equiv 2 \pmod{p}$, but that gives us $kq\equiv 1$, not $q\equiv 1$. Am I making sense? Nov 28 '16 at 18:58
• @GTonyJacobs you are correct, $kq \equiv 1$ is not helpful. Nov 28 '16 at 19:01
• Also, we don't know that $\gcd(3,p)=1$, because $p$ could equal $3$. Nov 28 '16 at 19:14
• @GTonyJacobs would you please give me a hint to solve this problem? thank you. Nov 28 '16 at 19:23
• I will, when I figure out a solution! Let me think about it.... Nov 28 '16 at 20:07

It's a bit tricky but I got the answer:

We start with $0 \equiv \frac{3^{p}-1}{2} \pmod{q}$

$3^{p}-1 = 2qk$

$3^{p} = 2qk + 1$ this meants that $1 \equiv 3^{p} \pmod{q}$

By the latter we have that $Ord_{q}(3) = p$ $\Rightarrow p|\phi(q) = p|(q-1)$

We express this relation by:

$0 \equiv (q-1) \pmod p$ $\Rightarrow$ $(q-1) = pk$ $\Rightarrow$ $1 \equiv q \pmod p$