Solving a congruence using a primitive root

Question

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

Answer 1

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}.$$

Answer 2

Write $7 \equiv 3^a \bmod 17$ and $6 \equiv 3^b \bmod 17$ and solve $ax \equiv b \bmod 16$.

Answer 3

$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.