Explain solution of this system of non-linear congruence equations 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:


*

*Find the solution of $3\cdot a + 5\cdot b = 1$ with Extended Euclidean Algorithm

*Use $a$ and $b$ values from previous step in the next formula: $x \equiv 21^a\times17^b\ (\textrm{mod}\ 23)$

*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?
 A: 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.
A: 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.


*

*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$.

*Now let's multiply first congruence by $a$ — $(x^3)^2 \equiv 21^2\ (\textrm{mod}\ 23)$ 

*And the second one by $b$ — $(x^5)^{-1} \equiv 17^{-1}\ (\textrm{mod}\ 23)$

*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.
