Solving congruence equations

Question

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?

Answer 1

$$2^2=4,2^3=8,2^4=16\equiv-7,2^5\equiv9,2^6\equiv18\equiv-5,2^{11}\equiv9(-5)\equiv1$$

$5^2\equiv2\pmod{23},5^5=5(5^2)^2\equiv5\cdot2^2\equiv20\equiv-3,5^6\equiv2^3\equiv8,$ $5^{11}=5^5\cdot5^6\equiv-3\cdot8\equiv-1$

So, $5$ is a primitive root $\pmod{23}$ unlike $2$

$7\equiv-16\equiv5^{11}(5^2)^4\equiv5^{19}\implies$ind$_57=19$

$11\equiv-12\equiv2^2(-3)\equiv(5^2)^25^5\equiv5^9$

Using Discrete logarithm, $7x^6\equiv11\pmod{23}$

$\implies$ind$_57+6$ind$_5x\equiv$ind$_511\pmod{22}\implies19+6$ind$_5x\equiv9\pmod{22}$

$\implies6$ind$_5x\equiv-10\pmod{22}\equiv12$

As $6a=12+22b\implies3y=6+11b\implies3a\equiv6\pmod{11}\implies a\equiv2\pmod{11}$ as $(3,11)=1$

$\implies$ind$_5x\equiv2\pmod{11}\implies x\equiv2^5\pmod{23}$

Answer 2

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