1
$\begingroup$

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!

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

1 Answer 1

Reset to default
0
$\begingroup$

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?

$\endgroup$
5
  • $\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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 at 8:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .