# How to solve Chinese Remainder Theorem with exponantial values

I need help solving this Chinese Remainder Theorem, but I would like to solve it using Euclid's Algorithm.

\begin{align*} 2x &\equiv 4^{2010} \pmod{3} \\ 15x &\equiv 13 \pmod{4} \\ 3x &\equiv (-29) \pmod{5} \end{align*}

I know how to solve regular exercises like this, I don't know how to solve a congruence with exponent using Euclid's Algorithm. So, if anyone could help me solve the first congruence with Euclid's Algorithm, that would be great. Thank you for the answers!

• Your particular example is trivial because $4^{2010} \equiv 1^{2010} =1 \pmod 3$ – Deepak Jun 18 at 10:43

As @Deepak commented, the first congruence boils down to $$2x \equiv -x \equiv 1 \pmod 3$$, the sound to $$15x \equiv -x \equiv 1 \pmod 4$$ and the third to $$3x \equiv 1 \pmod 5$$. Can you take it from here?
• @luchka13 Do you mean using Euclid to compute the inverse of the leading coefficients $\,2,15,3?\,$ Please describe how you tried to solve the first congruence so we can see exactly where you got stuck. – Bill Dubuque Jun 18 at 15:06
• @luchka13 Agaim precisely where are you stuck? At $\, 4^n\equiv 1^n\equiv 1\pmod{3}?\$ – Bill Dubuque Jun 18 at 20:27