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!
Best Answer
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.