| | |
Evaluate $\textrm{ind}_3 x$ (when $7$ is the modulus) for integers $x$ between $1$ and $6$, inclusive.
Solve the following congruence: $6x^{12} \equiv 11\pmod{17}$
Trying to isolate the $x$, we multiply both sides of the congruence by the multiplicative inverse of $6$ modulo $17$, which we quickly determine to be $3$, by inspection.
$$3 \cdot 6 x^{12} \equiv 3 \cdot 11 \pmod{17}$$ or equivalently, $$x^{12} \equiv 16 \pmod{17}$$If we can locate a primitive root for $17$, we can use indices to pull the exponent $12$ down -- just like logarithms can be used to pull exponents down 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 (x^{12}) \equiv \textrm{ind}_3 16 \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,
$$12 \cdot \textrm{ind}_3 x \equiv \textrm{ind}_3 16 \pmod{16}$$Now, appealing to the table above, we replace the index on the right with it's corresponding value...
$$12 \cdot \textrm{ind}_3 x \equiv 8 \pmod{16}$$Note, since $12$, $8$, and $16$ are all divisible by $4$, we can reduce this congruence to
$$3 \textrm{ind}_3 x \equiv 2 \pmod{4}$$$3$ is its own multiplicative inverse, modulo $4$, so multiplying both sides by $3$ yields
$$\textrm{ind}_3 x \equiv 6 \equiv 2 \pmod{4}$$Of course, there are multiple incongruent values, modulo $16$, that satisfy the above. In particular, $$\textrm{ind}_3 x \equiv 2, 6, 10, \textrm{ or } 14 \pmod{16}$$ Appealing to our table above, we see the solution is then given by $$x \equiv 9, 15, 8, \textrm{ or } 2 \pmod{17}$$
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}$$