📂Number Theory

Proof of the Chinese Remainder Theorem

Theorem

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

Explanation

It is said that a mathematics book written in China between the 3rd and 5th centuries AD contained this problem.

If a number is grouped by threes, two remain; by fives, three remain; and by sevens, two remain. What is the number? - Sunzi’s Arithmetic, Exercise 26

Using the modern mathematical expression, it becomes a 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.” It is because the earliest recorded solution to simultaneous congruence equations, regardless of time and place, was introduced in a Chinese mathematics book.

Note that the author of Sunzi’s Arithmetic is known only by the surname Sun and has no relation to Sun Wu, who wrote “The Art of War.”

As seen in the example, even if more than one equation is given, it does not matter at all.

Proof

Strategy: Concrete proof of a 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 congruence above 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 the 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, $x_{0}$ is confirmed to be the solution to $(2)$.

■

Code

The following code implements the Chinese remainder theorem in R language. It finds the solution when given a matrix of size $n \times 2$. For the given problem $\begin{cases} x \equiv 2 \pmod{3} \\ x \equiv 3 \pmod{5} \\ x \equiv 2 \pmod{7} \end{cases}$, just 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 executing the above code is as follows. Let’s confirm that $x=23$ is the answer to the given problem.