Solving a congruence using a primitive root I've asked to show that $3$ is a primitive root $\pmod{17}$ (done). Next, I was asked to solve the congruence $$7^x \equiv 6 \pmod{17}$$
I don't see how to apply the knowledge about $3$ being a primitive root to solve the above congruence. What is the relation between the two?
Thanks
 A: I suppose you've calculated all the powers of $3$ up to order $15$. So you know
$$6\equiv 3^{15}, \quad 7\equiv 3^{11}\mod 17,$$
and you have to solve the congruence
$$3^{11x}\equiv 3^{15} \mod 17\iff 11x\equiv 15\mod 16$$
since $3$ is a primitive root module $17$.
Now this is equivalent to
$$ -5x\equiv -1\iff x\equiv 5^{-1}\mod 16. $$
Since a Bézout's relation between $5$ and $16$ is $16-3\cdot 5=1$, we obtain
$$\color{red}{x\equiv} 5^{-1}\equiv -3\equiv \color{red}{13 \mod 16}.$$
A: Write $7 \equiv 3^a \bmod 17$ and $6 \equiv 3^b \bmod 17$ and solve $ax \equiv b \bmod 16$.
A: $7^6≡ 9 mod 17$
$7^7≡ 12 mod 17$
$7^6\times 7^7≡ (9\times12) =108 mod 17 ≡  6 mod 17$
$7^{13} ≡ 6 mod 17$
$7^{13} \times 7=7^{14} ≡ 42 mod 17 ≡ 8 mod 17$
$7^{14}\times 7 = 7^{15} ≡  5 mod 17$
$7^{14}\times 7^{15}=7^{29} ≡ 40 mod 17 ≡ 6 mod 17$
Next powers are $61, 125, 253, 509 . . .$
By induction we can see that general form of x  is:
$x = 13 + 16 (2^{n-1} -1)$
Where $n= 1, 2, 3 . . .$  is the index of $3^x$ (i.e. 1 for first, 2 for second,... solutions). Hence this congruence has infinitely many solutions.
