# Solution

Use the table of powers and indexes provided to solve the following congruence: $3x^{14} \equiv 2 \pmod{23}$

Some powers and related indexes $\pmod{23}$
$$\begin{array}{rclcrcl|rclrcl} 5^1 &\equiv& 5 && 5^{12} &\equiv& 18 & \text{ind}_5 1 &=& 22 & \text{ind}_5 12 &=&20\\ 5^2 &\equiv& 2 && 5^{13} &\equiv& 21 & \text{ind}_5 2 &=& 2 & \text{ind}_5 13 &=&14\\ 5^3 &\equiv& 10 && 5^{14} &\equiv& 13 & \text{ind}_5 3 &=& 16 & \text{ind}_5 14 &=&21\\ 5^4 &\equiv& 4 && 5^{15} &\equiv& 19 & \text{ind}_5 4 &=& 4 & \text{ind}_5 15 &=&17\\ 5^5 &\equiv& 20 && 5^{16} &\equiv& 3 & \text{ind}_5 5 &=& 1 & \text{ind}_5 16 &=&8\\ 5^6 &\equiv& 8 && 5^{17} &\equiv& 15 & \text{ind}_5 6 &=& 18 & \text{ind}_5 17 &=&7\\ 5^7 &\equiv& 17 && 5^{18} &\equiv& 6 & \text{ind}_5 7 &=& 19 & \text{ind}_5 18 &=&12\\ 5^8 &\equiv& 16 && 5^{19} &\equiv& 7 & \text{ind}_5 8 &=& 6 & \text{ind}_5 19 &=&15\\ 5^9 &\equiv& 11 && 5^{20} &\equiv& 12 & \text{ind}_5 9 &=& 10 & \text{ind}_5 20 &=&5\\ 5^{10} &\equiv& 9 && 5^{21} &\equiv& 14 & \text{ind}_5 10 &=& 3 & \text{ind}_5 21 &=&13\\ 5^{11} &\equiv& 22 && 5^{22} &\equiv& 1 & \text{ind}_5 11 &=& 9 & \text{ind}_5 22 &=&11\\ \end{array}$$

Either by calculating them, or by simply consulting the table given, we first note that the powers of $5$ generate all of the values from $1$ to $22$, so $5$ is a primitive element modulo $23$.

As such, we can find $\text{ind}_5 n$ for any $n$ from $1$ to $22$ by simply identifying the exponent that can be placed on $5$ to obtain $n$. This again, has been provided to us in the table.

Recalling that for a primitive root $r$ of $n$, $x \equiv y \pmod{n}$ implies $\text{ind}_r x \equiv \text{ind}_r y \pmod{\phi(n)}$, we know that $3x^{14} \equiv 2 \pmod{23}$ implies

$$\text{ind}_5 3x^{14} \equiv \text{ind}_5 2 \pmod{22}$$

Again, for a primitive root $r$ of $n$, we know $\text{ind}_r ab \equiv \text{ind}_r a + \text{ind}_r b \pmod{\phi(n)}$, so we can rewrite the last congruence as

$$\text{ind}_5 3 + \text{ind}_5 x^{14} \equiv \text{ind}_5 2 \pmod{22}$$

Using one more property of indexes -- namely, that $\text{ind}_r a^p \equiv p \cdot \text{ind}_r a \pmod{\phi(n)}$, we have

$$\text{ind}_5 3 + 14 \text{ind}_5 x \equiv \text{ind}_5 2 \pmod{22}$$

Now, plugging in the appropriate values shown in the table given, we have

$$16 + 14 \text{ind}_5 x \equiv 2 \pmod{22}$$

Isolating the $x$, we get

$$14 \text{ind}_5 x \equiv -14 \pmod{22}$$

Noting that $\gcd(14,22) = 2$, we can't divide both sides by $14$ without also dividing the modulus by $2$, so

$$\text{ind}_5 x \equiv -1 \pmod{11}$$

Equivalently,

$$\text{ind}_5 x \equiv 10 \pmod{11}$$

which tells us that either

$$\text{ind}_5 x \equiv 10 \text{ or } 21 \pmod{22}$$

Finally, looking up the corresponding powers in the table given, we arrive at our solution:

$$x \equiv 9 \text{ or } 14 \pmod{23}$$