Solve $7^x \equiv 6 \pmod{17}$ given 3 is a primitive root $\bmod 17$

Question

It's easy to show that 3 is a primitive root $\bmod 17$, but how do I use it prove the congruence?

Is there a general way to solve any congruence of the form $a^x \equiv b \pmod{c}$ if you know a primitive root $\bmod c$ and c is big (without brute force)?

Answer 1

Here if you observe that $7=3^{11}\quad \& \quad 6=3^{15}$ so Putting above we have

$3^{11x}\equiv 3^{15}~ \pmod{17}$

$\implies 3^{11x-15}\equiv 1 \pmod{17}$

3 is primitive root so $11x-15=16n$ for some $n\in \mathbb{Z}$

$\implies x=\dfrac{16n+15}{11}$ will be integer

You can easily see that $n=8$ satifies this ,So $x=13$ will be a solution of given .

There will be more solution of this too.

Answer 2

You can reduce the amount of brute force quite significantly. Using an interval $d$ of approximately $\sqrt{c}$, make an "island" of values $a\cdot g^i$ with $i\in \{0,d{-}1\}$, then calculate all $g^{jd}$ and identify the coinciding value.

$\begin{array}{c|c} k\ (d=4) &g^k & a\cdot g^k & b\cdot g^k \\ \hline 0 & 1 & 7 & 6 \\ 1 & 3 & \color{red}{4} & \color{violet}{1} \\ 2 & 9 & 12 & 3 \\ 3 & 10 & 2 & 9 \\ 4 & 13\\ 8 & 16\\ 12 & \color{red}{4}\\ 16 & \color{violet}{1}\\ \end{array}$

giving, $\bmod 17$, $7\cdot 3\equiv 3^{12}$ and $6\cdot 3\equiv 3^{16}$ , so $7\equiv 3^{11}$ and $6\equiv 3^{15}$.

Then we need to find $11x\equiv 15 \bmod 16 (=\phi(17))$, which means finding the inverse of $11\bmod 16$, which here is $3$, giving $x\equiv 15\cdot 3 \equiv 13\bmod 16$.

Obviously for this exercise in small numbers this is more work thn simply calculating the powers of $7 \bmod 17$, but for larger numbers it avoids calculating all powers.

Because $3$ is a primitive root $\bmod 17$, we are guaranteed to find suitable exponents in the first stage.