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!

  • 2
    $\begingroup$ Your particular example is trivial because $4^{2010} \equiv 1^{2010} =1 \pmod 3$ $\endgroup$ – 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?

  • $\begingroup$ I would like to solve the first congruence using Euclid's Algorithm, I don't always see the result just by looking at a congruence, so I've been using Euclid's Algorithm to solve them. But I don't know how to use it for the first congruence. $\endgroup$ – luchka13 Jun 18 at 11:51
  • 1
    $\begingroup$ @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. $\endgroup$ – Bill Dubuque Jun 18 at 15:06
  • $\begingroup$ i know how to make the second and third congruence with Euclid's Algorithm, and i get the correct answers, but I have no idea how to do that with the first one $\endgroup$ – luchka13 Jun 18 at 16:28
  • $\begingroup$ @luchka13 Agaim precisely where are you stuck? At $\, 4^n\equiv 1^n\equiv 1\pmod{3}?\ $ $\endgroup$ – Bill Dubuque Jun 18 at 20:27
  • $\begingroup$ i do all these congruences with Euclid's Algorithm, so the second and third congruence don't cause me any problems, the first one, though, i don't even know how to start.. i do them EXACTLY like this video shows. youtube.com/watch?v=4-HSjLXrfPs But i don't know how to do the first one. are the steps the same or what? $\endgroup$ – luchka13 Jun 19 at 8:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.