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!
As @Deepak commented, the first congruence boils down to $2x \equiv -x \equiv 1 \pmod 3$, the second to $15x \equiv -x \equiv 1 \pmod 4$ and the third to $3x \equiv 1 \pmod 5$. Can you take it from here?