logo

中国人の剰余定理の証明 📂整数論

中国人の剰余定理の証明

要約

$\gcd(n,m) = 1$と$\begin{cases} x \equiv b \pmod{n} \\ x \equiv c \pmod{m} \end{cases}$が$1 \le x \le nm$でぴったり一つの解を持つ。

説明

紀元3世紀から5世紀に中国で書かれたと伝えられるある数学の書物に、こんな問題があったらしい。

ある数を3つずつグループにすると2が余り、5つずつにすると3が余り、7つずつにすると2が余る。この数は何か？ - 孫子算経下巻、演習問題26

現代的な数学の表現を使うと、 $$ \begin{cases} x \equiv 2 \pmod{3} \\ x \equiv 3 \pmod{5} \\ x \equiv 2 \pmod{7} \end{cases} $$ の解を求める問題になる。今になってこの問題を解決するために使われる定理は「中国の剰余定理」として知られている。時代や場所を問わず、連立合同方程式の解に関する最古の記録が中国の数学書で紹介されたからだ。

ちなみに、孫子算経の著者はただ孫氏であると知られており、「孫子兵法」を書いた「孫武」とは全く関係がない。

例に見られるように、与えられた式が二つ以上であっても全く問題ない。

証明

戦略：具体的に唯一の解を求める。

$$ \begin{equation} x \equiv b \pmod{n} \end{equation} $$ $$ \begin{equation} x \equiv c \pmod{m} \end{equation} $$ $x \equiv b \pmod{n}$であるから、$x = ny + b$を満たす$y \in \mathbb{Z}$が存在し、これを$(2)$に代入すると、 $$ ny \equiv c - b \pmod{m} $$ 一方、上の合同式は$ 1 \le y \le m$で唯一の解$y_{0}$を持ち、したがって$x = ny_{0} + b$は$ 1 \le x \le nm$で唯一の解$x_{0}$を持つ。したがって $$ x_{0} = ny_{0} + b $$ ここで、$x_{0}$は$(1)$の解である。今、$ny_{0} \equiv c - b \pmod{m}$に$ny_{0} = x_{0} - b$を代入すると $$ x_{0} \equiv c \pmod{m} $$ 言い換えると、$x_{0}$が$(2)$の解であることを確認できる。

■

コード

以下のコードはR言語で中国の剰余定理を実装したものだ。$n \times 2$サイズの行列を与えると、解を求めてくれる。与えられた問題が$\begin{cases} x \equiv 2 \pmod{3} \\ x \equiv 3 \pmod{5} \\ x \equiv 2 \pmod{7} \end{cases}$なら、行列$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)

上記のコードを実行した結果は以下の通りだ。$x=23$が与えられた問題の答えであることを確認しよう。

20190227_212607.png