3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$ Nov 28 '16 at 18:58
  • $\begingroup$ @GTonyJacobs you are correct, $kq \equiv 1$ is not helpful. $\endgroup$
    – Node.JS
    Nov 28 '16 at 19:01
  • 1
    $\begingroup$ Also, we don't know that $\gcd(3,p)=1$, because $p$ could equal $3$. $\endgroup$ Nov 28 '16 at 19:14
  • $\begingroup$ @GTonyJacobs would you please give me a hint to solve this problem? thank you. $\endgroup$
    – Node.JS
    Nov 28 '16 at 19:23
  • 1
    $\begingroup$ I will, when I figure out a solution! Let me think about it.... $\endgroup$ Nov 28 '16 at 20:07
4
$\begingroup$

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$

$\endgroup$
0

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.