Explain solution of this system of non-linear congruence equations

Question

So I have a system of non-linear congruence equations (i may be wrong in terms): \begin{cases} x^3 \equiv 21\ (\textrm{mod}\ 23) \\ x^5 \equiv 17\ (\textrm{mod}\ 23) \end{cases} Somewhere I've read that to solve this system one should:

1. Find the solution of $3\cdot a + 5\cdot b = 1$ with Extended Euclidean Algorithm
2. Use $a$ and $b$ values from previous step in the next formula: $x \equiv 21^a\times17^b\ (\textrm{mod}\ 23)$
3. If $a$ or $b$ is negative, then calculate the modular inverse of $21$ or $17$ and use it in second formula with $-a$ or $-b$

And I don't understand why is it working. I've tried to perform some calculations to get the second formula but didn't succeeded. : (

Can you please explain me this?

Answer 1

I finally got it. Jack D'Aurizio's solution is correct, but in my case i just wanted to understand why is solution from the question working.

---

So we have a system of non-linear congruence equations.

1. We can see that $gcd(3, 5) = 1$ (greatest common divisor of exponents), and because of that $\exists a,b : 3a+5b=1$. After solving this with Extended Euclidean Algorithm we have $a=2$ and $b=-1$.
2. Now let's multiply first congruence by $a$ — $(x^3)^2 \equiv 21^2\ (\textrm{mod}\ 23)$
3. And the second one by $b$ — $(x^5)^{-1} \equiv 17^{-1}\ (\textrm{mod}\ 23)$
4. After that we have to "open exponent brackets", multiply the equations and finally find $x$: \begin{equation}x^6\times x^{-5}\ \equiv\ 21^2\times 17^{-1}\ (\textrm{mod}\ 23)\end{equation} \begin{equation}x\ \equiv\ 4\times 19\ (\textrm{mod}\ 23)\end{equation} \begin{equation}x\ \equiv\ 7\ (\textrm{mod}\ 23)\end{equation}

---

So as you can see, we've used Extended Euclidean Algorithm to find special exponents that will lead to reducing $x$'s exponent after equations multiplication.

Answer 2

Since neither $3$ or $5$ are divisors of $\varphi(23)=22$, both the maps $$ f:x\mapsto x^3,\qquad g:x\mapsto x^5 $$ are bijective on $\mathbb{F}_{23}$. In particular, since $3^{-1}\equiv 15\pmod{22}$ and $5^{-1}\equiv 9\pmod{22}$, $$ f^{-1}:x\mapsto x^{15},\qquad g^{-1}:x\mapsto x^9 $$ and $x^3\equiv 21\pmod{23}$ is equivalent to $x\equiv 7\pmod{23}$, as well as $x^5\equiv 17\pmod{23}$ is equivalent to $x\equiv 7\pmod{23}$. So $\color{red}{x\equiv 7\pmod{23}}$ is the wanted solution.