0

The proof of the CRT goes as follows:
Given the number $x \epsilon Z_m$, $m=m_1m_2...m_k$ $$M_k = m/m_k$$ construct: $$ x = a_1M_1y_1+a_2M_2y_2+...+a_nM_ny_n$$ where $y_k$ is the particular inverse of $M_k\ mod\ m_k$ $$\Rightarrow x\equiv a_kM_ky_k\equiv a_k(mod\ m_k)$$

What I don't understand is:
how is $x\equiv a_1M_1y_1+a_2M_2y_2+...+a_kM_ky_k$ and this lies in $mod\ m$? Is this because there is some rule in modular arithmetic for adding two numbers in two different mod worlds like: $c \mod d \ + e\ mod f = (c+d)(mod(ef))$? As far as I know, there isn't one like that. And how does the addition of these items all in a different mod world provide the solution for x?

mathmaniage
  • 596

2 Answers2

1

I think $x$ is calculated in $\mathbf Z$, using representatives of $M_k^{-1}\bmod m_k$. Note that the congruence class of $x$ $\bmod m$ is independent of the choice of the representatives.

Bernard
  • 175,478
  • but why do we mod m? What is the cause for it? – mathmaniage May 02 '19 at 11:28
  • and why do the moduli have to be pairwise relatively prime? – mathmaniage May 02 '19 at 11:33
  • I don't quite see your problem. The Chinese Remainder theorem is about solving systems of congruences. Isn't that clear to you? – Bernard May 02 '19 at 11:33
  • yes, that's clear but why does $x$ lie in mod m? what's the reason for it? – mathmaniage May 02 '19 at 11:34
  • That's what the C.R.T. is about: you have a set of congruence equation modulo $m_1, m_2,\dots, m_k$ and you can deduce a common solution. The C.R.T. asserts that if the $m_i$ are pairwise coprime, this solution is unique modulo $m_1m_2\dotsm m_k$. – Bernard May 02 '19 at 11:49
  • yes, but, I've seen a couple of books and resources, but nowhere does it mathematically deduce that the solution lies in mod m, where $m=m_1m_2...m_k$ – mathmaniage May 02 '19 at 11:51
  • The formulation I know asserts there is a ring isomorphism $$\mathbf Z/m_1\dotsm m_k\mathbf Z\simeq \mathbf Z/m_1\mathbf Z\times\dotsm\times\mathbf Z/m_k\mathbf Z $$. – Bernard May 02 '19 at 11:57
  • Is this something we can understand without abstract algebra? Can you point to a link or something for understanding this deduction? – mathmaniage May 02 '19 at 11:59
  • Maybe this web page ? – Bernard May 02 '19 at 12:02
  • yep that was it, it explains the reason, but, I didnt understand this part: if $z\equiv a mod p$ and y is the solution z-y is a multiple of pq, if p and q are coprime, why do they need to be coprime? and why should $z-y \geq pq.$ – mathmaniage May 02 '19 at 12:50
  • That's because if both $y,z\equiv a\mod p$ and $y,z\equiv b \mod q$; it means that $y-a$ and $z-a$ are divisible by $p$, whenve $z-y$ is also divisible by $p$. Similarly, you can check $z-y$ is divisible by $q$. So as it's divisible by both $p$ and $q$, Gauß'lemma says that, if $p$ and $q$ are coprime, it's divisible by $pq$. If they're not coprime , you can't be sure of the conclusion. For instance, $20$ is divisible by $4$ and by $10$; but it's not divisible by $40$. – Bernard May 02 '19 at 13:24
  • Gauß'lemma? Google only found gauss lemma, but, that was related to polynomial. Is that the one you meant? – mathmaniage May 02 '19 at 13:34
  • and can't the product of pq exceed (z-y) in which case it wouldn't be divisible? – mathmaniage May 02 '19 at 13:35
  • It's a consequence of an arithmetic Gauß' lemma I meant. The lemma itself says that if $a$ divides $bc$ and is coprime to $b$, it divides $c$. If I remember well, all this can be proved from Bézout's identity. – Bernard May 02 '19 at 13:38
  • If $pq>z-y$, it implies $z-y=0$, i.e. z=y$. – Bernard May 02 '19 at 13:39
  • but the lemma you mention, its for $a|bc$ where a and b are coprime, but here, it's more like: $pq|x$ where p and q are coprime, where x=(z-y) – mathmaniage May 02 '19 at 14:04
  • I donn't remember the exact proof at the ùmoment, but all these results ultimately rely on Bézout. – Bernard May 02 '19 at 14:14
0

The part 2 of the chinese remainder theorem, which starts off at this page and continues to the next, explains the concept of lcm required to understand the OP's question and the concept why the solution exists in mod m, which is actually only a way of finding the minimum solution.

mathmaniage
  • 596