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

1 Answer 1

Reset to default
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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .