"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: where , find .

Proof that solution exists:

  • write as []
  • put into equation 2,
  • since , then there must exists .
  • multiplying by on both sides, we get
  • , putting into eq (1), x is of form:

Proof that solution is unique:

  • In modulo arithmetic, if , then , then let and
  • then , thus . Thus, are same modulo .

This can be easily generalised to arbitrary congruences with each pairwise modulo are co-prime, i.e. . There’s a very beautiful general solution to CRT.