# 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 $\displaystyle x^5 \equiv 6 \pmod{17}$

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

$\displaystyle (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 $\displaystyle x^5 \equiv 6 \pmod{17}$

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

$\displaystyle (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:

$\displaystyle 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?

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

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

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

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

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

So the solution is $\displaystyle 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 $\displaystyle x^5 \equiv 6 \pmod{17}$

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

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

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

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

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

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

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

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

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

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