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?

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.
