Chinese Remainder Theorem Explanation

I'm reading through a brief example of the Chinese remainder theorem and am having difficulty understand the process they are going through.

Consider two primes p and q. For an arbitrary a < p and b < q, there exists a unique y less than p × q such that y ≡ a (mod p) and y ≡ b (mod q).

Consider p=5 and q=7. Consider a=4 and b=3,there exists a unique y less than 35 such that y ≡ 4 (mod 5) and y ≡ 3 (mod 7), that is y = 24.

Method:

Use Euclids algorithm to compute the smallest u such that u × q ≡ 1 ( mod p), it gives 7×u≡1(mod5) ≡ u = 3

Compute y=(((a−b)×u)modp)×q+b,it gives y=(((4−3)×3)mod 5)×7+3 = (3 mod 5)×7+3 = 3×7+3 = 24

I'm having quite a lot of trouble trying to find out what is going on here and how the method utilises Euclid's algorithm. Can anybody please help and explain it better and simpler? Thank you!

Solution 1:

First, before addressing your questions, let's prove slightly different form of CRT, one that is very easy to remember and often more efficient to apply.

Theorem $\:$ (Easy CRT) $\rm\ \ $ If $\rm\ m,\:n\:$ are coprime integers then $\rm\ m^{-1}\ $ exists $\rm\ (mod\ n)\ \ $ and

$\rm\displaystyle\quad\quad\quad\quad\quad \begin{eqnarray}\rm x&\equiv&\rm\ a\ (mod\ m) \\ \rm x&\equiv&\rm\ b\ (mod\ n)\end{eqnarray} \ \iff\ \ x\ \equiv\ a + m\ \bigg[\frac{b-a}{m}\ mod\ n\:\bigg]\ \ (mod\ m\:n)$

Proof $\rm\ (\Leftarrow)\ \ \ mod\ m:\ x\ \equiv\ a + m\ [\,\cdots\,]\ \equiv\ a\:,\ $ and $\rm\ mod\ n\!\!:\ x\ \equiv\ a + (b-a)\ m/m\ \equiv\ b\:.$

$\rm (\Rightarrow)\ \ $ The solution is unique $\rm\ (mod\ m\:n)\ $ since if $\rm\ x',\:x\ $ are solutions then $\rm\ x'\equiv x\ $ mod $\rm\:m,n\:$ therefore $\rm\ m,\:n\ |\ x'-x\ \Rightarrow\ m\:n\ |\ x'-x\ \ $ since $\rm\ \:m,\:n\:$ coprime $\rm\:\Rightarrow\ lcm(m,n) = m\:n\:.\ \, $ QED

Note $\ $ Easy CRT is not only easy to apply, but also very easy to remember. Namely note $\rm\ x\equiv a\pmod m\iff x = a + m\,k,\:$ for some integer $\rm\:k\:$. This further satisfies the second congruence iff $\rm\:mod\ n\!:\ x = a + m\,k\equiv b$ $\iff$ $\rm k\:\equiv (b-a)/m,\ $ hence the "Easy CRT" solution. This enables the $(\Leftarrow)$ proof, i.e. fill in the dots in $\rm\:a + m\ [\,\cdots\,]\:$ so that it is $\rm\equiv b\pmod n\:$

The extended Euclidean algorithm may be used to compute the modular inverse $\rm\, m^{-1}\pmod n $ and, hence, the above bracketed value $\rm\ (b-a)/m = (b-a)m^{-1}\ mod\ n.\ $ For small numbers one can often compute this "fraction" by judicious cancellation and twiddling, e.g. see the many worked examples in prior posts here.

The more symmetric form of CRT that you mention in your question often proves more convenient for theoretical (vs. computational) purposes. Notice that it works by computing the elements $\rm\,e = uq \equiv 1\pmod p\,$ and $\rm\,f = vp\equiv 1\pmod q,\, $ i.e. $\rm\, e \equiv (1,0),\, f \equiv (0,1)\ mod\ (p,q).\,$ Then $\rm\,y = (a,b) = a(1,0)+b(0,1) = ae+bf\,$ yields the solution. This can be presented more structurally as a ring isomorphism $\rm\,\Bbb Z/pq \cong \Bbb Z/p \times \Bbb Z/q,\,$ as rschwieb touches on in his answer.

Note that $\rm\,e,f\,$ are idempotents, i.e. $\rm\,e^2\!\equiv e,\,f^2\!\equiv f\,$ by $\rm \,e^2\! = (1,0)^2\! = (1^2,0^2)= (1,0)$. Generally idempotents in $\rm\:\Bbb Z_n\:$ correspond to factorizations of $\rm\:n\:$ into coprime factors. Namely, if $\rm\:e^2 = e\in\Bbb Z_n\:$ then $\rm\:n\:|\:e(e\!-\!1)\:$ so $\rm\:n = jk,\ j\:|\:e,\ k\:|\:e\!-\!1,\:$ so $\rm\:(j,k)= 1\:$ by $\rm\:(e,e\!-\!1) = 1.\:$ Conversely if $\rm\:n = jk\:$ for $\rm\:(j,k)= 1,\:$ then by CRT, $\rm\:\Bbb Z_n\cong \Bbb Z_j\times \Bbb Z_k\:$ which has nontrivial idempotents $\rm\:(0,1),\,(1,0).\:$ It is not difficult to explicitly work out the details of the correspondence. Some integer factorization algorithms can be viewed as searching for nontrivial idempotents. For more on the correspondence between idempotents and factorizations see Peirce Decomposition.

Solution 2:

Let me write the integers as $\Bbb Z$, the integers mod $m$ as $\Bbb Z_m$, and that makes the integers mod $n$ also $\Bbb Z_n$. I'd like to use these two letters instead of $p$ and $q$, but feel free to substitute them into what I write next.

The meaning

Now there is always a well-defined additive map from $\Bbb Z\to \Bbb Z_n\times \Bbb Z_m$ where you send $z\mapsto (z\pmod m,z\pmod n)$. (From now on, let me suppress the mods in each pair: just remember that the first is mod $n$ and the second is mod $m$.)

When $m$ and $n$ are coprime, the Chinese remainder theorem says: this map is onto!

In general, the map does not have to hit everything in $\Bbb Z_n\times \Bbb Z_m$, but when $m$ and $n$ are coprime it does.

The strategy

Here is the strategy your proof is describing. You have $(a,b)\in\Bbb Z_n\times \Bbb Z_m$. Our goal is to find $z$ such that $z\mapsto (z,z)=(a,b)$. To accomplish that, we could find $z'$ that maps to $(a,0)$, and $z''$ that maps to $(0,b)$, and by additivity then $z'+z''$ maps to $(a,b)$.

how the method utilises Euclid's algorithm.

The Euclidean algorithm is just a tool to find a $u$ such that $um\equiv 1\pmod n$ and an element $v$ such that $vn\equiv 1\pmod m$. Using the Euclidean algorithm on coprime integers $m$ and $n$ , we can find explicit $u$ and $v$ such that $um+vn=1$, and then computing mod $m$ and mod $n$ separately we see that $u$ and $v$ are what we need to complete the next step.

After you have $um\equiv 1\pmod{n}$, you are free to multiply both sides with $a$ so that $aum\equiv a\pmod n$, you have succeeded in finding an element $z'=aum$, because

$$aum\equiv a\pmod n\\ aum\equiv 0\pmod m\\ \implies(aum,aum)=(a,0)$$

Similarly,

$$bvn\equiv b\pmod m\\ bvn\equiv 0\pmod n\\ \implies(bvn,bvn)=(0,b)$$

So, $z''=bvn$ is our other half.

Since the mapping $\Bbb Z\to \Bbb Z_n\times\Bbb Z_m$ is additive, $z=aum+bvn$ maps to $(a,0)+(0,b)=(a,b)$, and we've shown that $z$ does the trick.