# Thread: Solving congruences using primitive roots

1. ## Solving congruences using primitive roots

Given that 3 is a primitive root modulo 17, determine all solutions to the congruence $x^5 \equiv 6 \pmod{17}$

Since 3 is a primitive root we have: $x = 3^m$ and so

$(3^m)^5 \equiv 6 \pmod{17}$

I am not sure how to progress on from here...

cheers for any help!

2. Originally Posted by usagi_killer
Given that 3 is a primitive root modulo 17, determine all solutions to the congruence $x^5 \equiv 6 \pmod{17}$

Since 3 is a primitive root we have: $x = 3^m$ and so

$(3^m)^5 \equiv 6 \pmod{17}$

I am not sure how to progress on from here...

cheers for any help!

We work modulo 17 in the following:

$3^{5m}=6=2\cdot 3\Longrightarrow 3^{5m-1}=2=3^{14}\Longrightarrow 5m-1=14\Longrightarrow$...

Tonio

3. ohh thanks very much, i actually just figured out another method, is this correct?

$3^{5m} \equiv 6 \equiv 3^{15} \pmod{17}$

$\implies 5m \equiv 15 \pmod{16}$

$\implies -3 \times 5m \equiv 15 \times -3 \pmod{16}$

$\implies m \equiv -45 \equiv 3 \pmod{16}$

Thus $x = 3^3 \equiv 10 \pmod{17}$

So the solution is $x \equiv 10 \pmod{17}$

Is this valid?

Cheers!

4. Originally Posted by usagi_killer
Given that 3 is a primitive root modulo 17, determine all solutions to the congruence $x^5 \equiv 6 \pmod{17}$

Since 3 is a primitive root we have: $x = 3^m$ and so

$(3^m)^5 \equiv 6 \pmod{17}$

I am not sure how to progress on from here...

cheers for any help!
Multiplying the congruence $x^5\equiv6\pmod{17}$ by $3$ we get, equivalently, $3x^5\equiv18\equiv1\pmod{17}$.

There exists a positive integer $m$ such that $x\equiv3^m\pmod{17}$ and so $3x^5\equiv3^{5m+1}\equiv{17}$. Finally, $3^{5m+1}\equiv1\equiv3^{16}\pmod{17}$, which is equivalent to solving $5m+1\equiv{16}\equiv0\pmod{16}$. The solution in the range $0\leq i\leq16$ is $m=3$.

The solutions of the original congruence are given by $x\equiv3^3\equiv10\pmod{17}$.

5. Originally Posted by melese
Multiplying the congruence $x^5\equiv6\pmod{17}$ by $3$ we get, equivalently, $3x^5\equiv18\equiv1\pmod{17}$.

There exists a positive integer $m$ such that $x\equiv3^m\pmod{17}$ and so $3x^5\equiv3^{5m+1}\equiv{17}$. Finally, $3^{5m+1}\equiv1\equiv3^{16}\pmod{17}$, which is equivalent to solving $5m+1\equiv{16}\equiv0\pmod{16}$. The solution in the range $0\leq i\leq16$ is $m=3$.

The solutions of the original congruence are given by $x\equiv3^5\equiv10\pmod{17}$.
Thanks heaps for the help!

But for the last congruence you mean $x \equiv 3^3 \equiv 10 \pmod{17}$ right? :P