"In addition to being a theorem and an algorithm, we would suggest to the reader that the Chinese remainder theorem is also a state of mind." - "Introduction to Mathematical Cryptography" by Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman

Problem: $x≡amodm,x≡bmodn$ where $g(m,n)=1$, find $x$.

Proof that solution exists:

- write $x$ as $x=a+mymodm$[]
- put into equation 2, $a+my≡bmodn⟹my≡(b−a)modn$
- since $g(m,n)=1$, then there must exists $mm_{′}=1modn$.
- multiplying by $m_{′}$ on both sides, we get $y≡m_{′}(b−a)modn$
- $y=m_{′}(b−a)+nz$, putting into eq (1), x is of form: $a+mm_{′}(b−a)+mnz$

Proof that solution is unique:

- In modulo arithmetic, if $c≡c_{′}modm$, then $m∣(c−c_{′})$, then let $c≡c_{′}modm⟹m∣c−c_{′}$ and $c≡c_{′}modn⟹n∣c−c_{′}$
- then $mn∣(c−c_{′})$, thus $c≡c_{′}modmn$. Thus, $c,c_{′}$ are same modulo $mn$.

This can be easily generalised to arbitrary congruences with each pairwise modulo are co-prime, i.e. $g(m_{i},m_{j})=1$. There’s a very beautiful general solution to CRT.