I'm currently going through Artin's Algebra, and it has me prove the Chinese Remainder Theorem. The book states the problem in the context of congruence classes, and I think I have a solution, but I haven't found anything like it online, and I'm not sure if it's correct. My proof is as follows:

Let $\textit{a, b, u, v}$ be integers, and assume that the greatest common divisor of $\textit{a}$ and $\textit{b}$ is 1. We will show that there is an integer $\textit{x}$ such that $\textit{x}$ $\equiv$ $\textit{u}$ modulo $\textit{a}$, and $\textit{x}$ $\equiv$ $\textit{v}$ modulo $\textit{b}$. Observe that the congruence class for $\textit{u}$ modulo $\textit{a}$ is equal to the set { . . . , -a + u, u, a + u, . . . }; similarly, the congruence class for $\textit{v}$ modulo $\textit{b}$ is the set { . . . , -b + v, v, b + v, . . .}. If $\textit{x}$ exists, then it is a member of both congruence classes, so that for some integers $\textit{m}$ and $\textit{n}$, $\textit{x}$ = $\textit{ma}$ + $\textit{u}$, and $\textit{x}$ = $\textit{nb}$ + $\textit{v}$, so $\textit{ma}$ + $\textit{u}$ = $\textit{nb}$ + $\textit{v}$, and therefore $\textit{ma}$ - $\textit{nb}$ = $\textit{v - u}$. Since $\textit{a}$ and $\textit{b}$ have a common divisor of 1, the set of all their integer combinations is exactly $\mathbb{Z}$; therefore, there are integers $\textit{m}$ and $\textit{n}$ such that $\textit{ma}$ - $\textit{nb}$ = $\textit{v - u}$. Thus $\textit{x}$ exists, and the proof is complete.

Like I said, I haven't found a proof like this anywhere online, and I'm really wondering if it's valid, so I'd really appreciate if someone could help. Also, this is my first time posting, so my formatting might be below par; please let me know if I need to correct anything in that regard. Thank you!

  • 1
    $\begingroup$ Looks good! To get from $2$ congruences to $n$ congruences, you can just do it again using the result for the first $2$ congruences with the next one, and so on (so always just two at a time). $\endgroup$ – quasi May 31 at 1:42
  • 2
    $\begingroup$ Yes, this method of driving a CRT solution from the GCD Bezout identity is very well-known and is proved many times here, e.g. here and here. $\endgroup$ – Bill Dubuque May 31 at 1:48
  • 1
    $\begingroup$ As regards formatting, it's readable. For the set expressions, enclose each of them between dollar signs, but for the set braces, you need to precede each such use with a backslash. To test that out, you can edit your post to fix that. $\endgroup$ – quasi May 31 at 1:49
  • 1
    $\begingroup$ @DavidNiu: Yes, induction would be the formalization of "and so on". $\endgroup$ – quasi May 31 at 3:28
  • 1
    $\begingroup$ @DavidNiu: Even if it's a known alternate proof, the fact that you came up with both the idea and a (very clear) proof independently is commendable. Welcome to MSE! $\endgroup$ – quasi May 31 at 3:33

Your Answer

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

Browse other questions tagged or ask your own question.