Chinese Reminder Theoremの略

ステートメント

k個の整数m1,m2,…,mkが互いに素ならば、任意の整数a1,a2,…,akに対して

x ≡ a1 (mod m1),
︙
x ≡ ak (mod mk)

を満たす整数xがm1m2…mkを法として一位に存在する。

具体例

略

証明

k=2の場合

存在

x ≡ a (mod m)
x ≡ b (mod n)

を満たすxがmnを法として一位に存在することを示す。 ユークリッドの互除法より mu + nv = 1を満たすu,vが存在する。このとき，

nv ≡ 1 (mod m)
mu ≡ 1 (mod n)

なので、x ≡ anv + bmu (mod mn)とするとxが求める解になる。

一意性：

x, yを任意の解とすると、 x - y ≡ 0 (mod m), x - y ≡ 0 (mod n) より、x-yはm, nで割り切れる。m,nは互いに素なので、x-yはmnの倍数、つまり x - y ≡ 0 (mod mn)

気持ち

任意のX,Yに対してx = anX + bmYとすれば、なんでも合同式を満たすので、肝は一意性が言えることか。と思ったけど、そうでもないか。 x ≡ anX (mod m)だけど、例えばnがmの倍数だとすると x ≡ 0 (mod m)になっちゃう。

====

言葉で直感的な意味を説明すると、 m1, m2, … , mkが互いに素ならば、各miに対する剰余を指定すれば、m1m2…mkを法として整数を一意に識別可能、ということ。

例えばm1,m2=5,7とすると、2つの数字を指定すれば5x7=35個の中から1つを選べる、ということ。よく考えると、指定できる数字はmod 5, mod 7で選ぶので35通りしかない。なので、crtの言っていることは、数字の指定の仕方に漏れや重複がない、ということ。

====

例えばm1=3,m2=4として、a1=2, a3=3とすると、

□□■□□■□□■□□■
□□□■□□□■□□□■

上の図で、■が重なるのは11番目の1箇所だけだよ、ということ。