Solution

Solve the following congruence:   $7^x \equiv 6\pmod{17}$


If we can locate a primitive root for $17$, we can use indices to pull the variable out of the exponent -- just like logarithms can be used to pull variables out of exponents when solving exponential equations.

In calculating the following powers$\pmod{17}$, and not seeing any duplicates until $n = \varphi(17) = 16$, it must be the case that $3$ is a primitive root for $17$:

$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16\\\hline 3^n & 3 & 9 & 10 & 13 & 5 & 15 & 11 & 16 & 14 &8 & 7 & 4 & 12 & 2 & 6 & 1\\ \end{array}$$

So, let's calculate the corresponding index values:

$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16\\\hline \textrm{ind}_3 & 16 & 14 & 1 & 12 & 5 & 15 & 11 & 10 & 2 & 3 & 7 & 13 & 4 & 9 & 6 & 8\\ \end{array}$$

Now, returning to our original congruence, "we take an index, base $3$ of both sides" (remember, doing this changes the modulus to $\varphi(17) = 16$) to obtain

$$\textrm{ind}_3 (7^x) \equiv \textrm{ind}_3 6\pmod{16}$$

However, we know that for any primitive root $r$ and $a$ relatively prime to $m$, we have $\textrm{ind}_r a^k \equiv k \cdot \textrm{ind}_r a \pmod{\varphi(m))}$ when $k$ is a positive integer. As such,

$$x \cdot \textrm{ind}_3 7 \equiv \textrm{ind}_3 6 \pmod{16}$$

Using the table above to look up the index values shown, we have

$$11x \equiv 15 \pmod{16}$$

Solving this is routine. We simply find the appropriate multiplicative inverse (by the Euclidean Algorithm, if necessary) of the coefficient on $x$ and multiply by that value on both sides. In this case, $11^{-1} \equiv 3$ is quickly found by inspection. So,

$$x \equiv 3 \cdot 15 \pmod{16}$$ or equivalently, $$x \equiv 13 \pmod{16}$$