<s>[INST] Solving congruence equations Solve: $7x^6\equiv 11 \pmod{23}$ and $5^x\equiv 19 \pmod{23}$
I can solve simple congruence equations but how do I go about solving these?
 [/INST] Fermat's little theorem says that $n^{22} \equiv 1 \pmod{23}$, which means that the last equation can be rewritten to an equation of the form $x \equiv a \pmod{22}$. To figure out $a$, we just need all powers of $5$ that is congruent to $19 \pmod{23}$. A quick search reveals that  $15$ is the only one.
Also, the first equation can be divided by $7$, to get $x^6 \equiv 18 \pmod{23}$
We now have the two equations
$$
x^6 \equiv 18\pmod{23} \qquad x \equiv 15 \pmod{22}
$$
There exist cube roots $\pmod{23}$, but not unique square roots. So the first equation has two solutions $\pmod{23}$.
The cube root of $18$ is calculated like this: Fermat's little theorem says that $18^{22n}\cdot 18 \equiv 18\pmod{23}$. Especially, $18^{45}\equiv 18$. That means that $(18^{15})^3 \equiv 18$, and it's the only congruence class for which this holds. $18^{15} \equiv 4 \pmod {23}$, so our equations are now reduced to
$$
x^2 \equiv 4 \pmod{23} \qquad x \equiv 15 \pmod{23}
$$
The first equation here has two solutions. One is easy to guess (it's $2$), and the other is easy to get from there (it's $-2 \equiv 21$). Thus we get two possible linear congruence equations:
$$
x \equiv 2 \pmod{23}\quad \wedge \quad x \equiv 15 \pmod{22} \\ \text{or} \\ x\equiv 21\pmod{23}\quad \wedge\quad x\equiv 15 \pmod{22}
$$
</s>