📂Number Theory

Proof of the Chinese Remainder Theorem

Theorem

If $\gcd(n,m) = 1$, then $\begin{cases} x \equiv b \pmod{n} \\ x \equiv c \pmod{m} \end{cases}$ has exactly one solution in $1 \le x \le nm$.

Explanation

It is said that a certain mathematics book, believed to have been written in China between the 3rd and 5th centuries AD, contained the following problem.

When a certain number is grouped in threes, two remain; when grouped in fives, three remain; and when grouped in sevens, two remain. What is this number? - Sunzi Suanjing, Volume 2, Exercise 26

Using modern mathematical notation, this becomes the problem of finding the solution to $$ \begin{cases} x \equiv 2 \pmod{3} \\ x \equiv 3 \pmod{5} \\ x \equiv 2 \pmod{7} \end{cases} $$ The theorem used today to solve this problem is known as the “Chinese remainder theorem.” This is because, throughout all times and places, the oldest record concerning the solution of systems of simultaneous congruence equations was introduced in a Chinese mathematics book.

For reference, the author of the Sunzi Suanjing is known only to have the surname Sun, and has nothing to do with “Sun Wu,” who wrote “The Art of War.”

As seen in the example, this is an obvious fact, but it makes no difference at all even if two or more equations are given.

Proof

Strategy: Explicitly find the unique solution.

---

$$ \begin{equation} x \equiv b \pmod{n} \end{equation} $$ $$ \begin{equation} x \equiv c \pmod{m} \end{equation} $$ Since $x \equiv b \pmod{n}$, there exists $y \in \mathbb{Z}$ satisfying $x = ny + b$, and substituting this into $(2)$ gives $$ ny \equiv c - b \pmod{m} $$ Meanwhile, the above congruence has a unique solution $y_{0}$ in $ 1 \le y \le m$, and therefore $x = ny_{0} + b$ has a unique solution $x_{0}$ in $ 1 \le x \le nm$. Hence $$ x_{0} = ny_{0} + b $$ Here $x_{0}$ is a solution to $(1)$. Now substituting $ny_{0} = x_{0} - b$ into $ny_{0} \equiv c - b \pmod{m}$ gives $$ x_{0} \equiv c \pmod{m} $$ In other words, we can confirm that $x_{0}$ is a solution to $(2)$.

■

Code

The following code implements the Chinese remainder theorem in the R language. Given a matrix of size $n \times 2$, it finds the solution. As in the example, if the given problem is $\begin{cases} x \equiv 2 \pmod{3} \\ x \equiv 3 \pmod{5} \\ x \equiv 2 \pmod{7} \end{cases}$, then you input the matrix $S := \begin{bmatrix} 2 & 3 \\ 3 & 5 \\ 2 & 7 \end{bmatrix}$.

CRA<-function(S)  #Algorithm of chinese remainder theorem
{
  r<-S[,1]      # matrix S express below sysyem.
  mod<-S[,2]    # x = r[1] (mod mod[1])
  n<-length(r)  # x = r[2] (mod mod[2])
  # x = r[3] (mod mod[3])
  
  A<-seq(r[1],to=mod[1]*mod[2],by=mod[1])
  
  for(i in 2:n)
  {
    B=seq(r[i],to=mod[1]*mod[i],by=mod[i])
    r[1]=min(A[A %in% B])
    mod[1]=mod[1]*mod[i]
    if (i<n) {A=seq(r[1],to=mod[1]*mod[i+1],by=mod[1])}
  }
  
  return(r[1])
}
 
example<-matrix(c(2,3,3,5,2,7),ncol=2,byrow=T); example
CRA(example)

The result of running the above code is as follows. Let us confirm that $x=23$ is the answer to the given problem.