中国剰余定理の証明
定理
$\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世紀の間に中国で書かれたと伝えられるある数学書には、次のような問題があったという。
ある数を三つずつ組にすると二つ余り、五つずつ組にすると三つ余り、七つずつ組にすると二つ余る。この数は何か。- 孫子算経下巻、演習問題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$が与えられた問題の答えとなることを確認してみよう。
