中国剰余定理 | 初等整数論

1 2つの条件をまとめる

例 1.1. $x \equiv 2 \pmod 3$ と $x \equiv 3 \pmod 5$ をともに満たす整数 $x$ を求める。 $3$ と $5$ は互いに素なので、§A4.3 補題 1.1により $3u+5v=1$ を満たす整数 $u,v$ が存在する。 $u=2,v=-1$ と取ると、 $3\times2+5\times(-1)=1$ である。

x = 2 \times 5 \times (-1) + 3 \times 3 \times 2 = -10 + 18 = 8

とおくと、 $5v=1-3u\equiv1\pmod3$ より $x\equiv2\pmod3$ であり、 $3u=1-5v\equiv1\pmod5$ より $x\equiv3\pmod5$ である。したがって $8$ は二つの条件を満たす。

2 中国剰余定理

補題 2.1. $m,n$ を互いに素な正の整数、 $a,b$ を整数とする。 $mu+nv=1$ を満たす整数 $u,v$ を取り、 $x_0=anv+bmu$ とおく。整数 $x$ が

x\equiv a\pmod m,\qquad x\equiv b\pmod n

をともに満たすための必要十分条件は、 $x\equiv x_0\pmod{mn}$ である。

証明.§A4.3 補題 1.1により、 $mu+nv=1$ を満たす整数 $u,v$ が存在する。 $nv\equiv1\pmod m$ 、 $mu\equiv1\pmod n$ であるから、 $x_0=anv+bmu$ は二つの合同式を満たす。

整数 $x$ も二つの合同式を満たすなら、ある整数 $s,t$ によって $x-x_0=ms=nt$ と書くことができる。したがって、

x-x_0=(mu+nv)(x-x_0)=mn(ut+vs)

であり、 $x\equiv x_0\pmod{mn}$ が成り立つ。逆に、 $x\equiv x_0\pmod{mn}$ なら、 $m$ と $n$ はともに $x-x_0$ を割り切るので、 $x$ は二つの合同式を満たす。▨

定理 2.2. $r\ge2$ を整数とし、 $m_1,\ldots,m_r$ をどの二つも互いに素な正の整数、 $a_1,\ldots,a_r$ を整数とする。 $M=m_1\cdots m_r$ とおく。ある整数 $x_0$ が存在して、整数 $x$ がすべての $i=1,\ldots,r$ について $x\equiv a_i\pmod{m_i}$ を満たすための必要十分条件は、 $x\equiv x_0\pmod M$ である。

証明. $r=2$ の場合は補題 2.1による。 $k\ge2$ とし、 $r=k$ の場合に主張が成り立つと仮定する。帰納法の仮定により、最初の $k$ 個の合同式は、ある整数 $c$ と $P=m_1\cdots m_k$ を用いて $x\equiv c\pmod P$ とまとめることができる。

$P$ と $m_{k+1}$ に $1$ より大きい公約数があれば、§A4.2 定理 2.2により、その公約数に素因子 $p$ が存在する。 $p$ は $P$ と $m_{k+1}$ をともに割り切り、§A4.2 補題 2.1を繰り返し用いると、 $p$ は $m_1,\ldots,m_k$ のいずれかも割り切る。これは法がどの二つも互いに素であることに反するので、 $P$ と $m_{k+1}$ は互いに素である。補題 2.1により、 $x\equiv c\pmod P$ と $x\equiv a_{k+1}\pmod{m_{k+1}}$ は、法 $Pm_{k+1}$ の一つの合同式にまとめることができる。数学的帰納法により、すべての整数 $r\ge2$ について主張が成り立つ。▨

3 3条件への拡張

例 3.1. $x\equiv2\pmod3$ 、 $x\equiv3\pmod5$ 、 $x\equiv2\pmod7$ をともに満たす整数 $x$ を求める。例 1.1の構成と補題 2.1により、最初の二つの合同式は $x\equiv8\pmod{15}$ と同値である。 $15$ と $7$ は互いに素であり、 $15\times1+7\times(-2)=1$ なので、補題 2.1の構成で $u=1,v=-2$ と取ると

x = 8 \times 7 \times (-2) + 2 \times 15 \times 1 = -112 + 30 = -82 \equiv 23 \pmod{105}

となる。したがって、解の全体は $x\equiv23\pmod{105}$ で表される。実際、 $23=3\times7+2=5\times4+3=7\times3+2$ であり、三つの条件をすべて満たす。

問題 3.2. $0\le x<30$ を満たす整数 $x$ のうち、 $x^2\equiv x\pmod{30}$ を満たすものをすべて求めよ。

解答.

$x^2\equiv x\pmod{30}$ は $30\mid x(x-1)$ と同値である。§A4.2 定理 2.2により、この条件は $2,3,5$ がそれぞれ $x(x-1)$ を割り切ることと同値である。§A4.2 補題 2.1により、各素数 $p=2,3,5$ について、 $p\mid x(x-1)$ ならば $p\mid x$ または $p\mid x-1$ である。逆に、どちらかの因子を $p$ が割り切るならば、積も $p$ で割り切れる。したがって、各法では $x\equiv0\pmod p$ または $x\equiv1\pmod p$ となる。

$a,b,c$ をそれぞれ $0,1$ から選び、

x\equiv a\pmod2,\qquad x\equiv b\pmod3,\qquad x\equiv c\pmod5

とする。定理 2.2により、各組 $(a,b,c)$ に対応する解は法 $30$ でただ一つ存在する。 $15$ は法 $2$ で $1$ 、法 $3,5$ で $0$ である。 $10$ は法 $3$ で $1$ 、法 $2,5$ で $0$ であり、 $6$ は法 $5$ で $1$ 、法 $2,3$ で $0$ である。したがって、対応する解は

x\equiv15a+10b+6c\pmod{30}

である。八つの組を代入し、 $0$ 以上 $30$ 未満の余りに直すと、

x=0,1,6,10,15,16,21,25

を得る。どの解からも三つの余りの組が定まり、異なる組は同じ解に対応しないため、これらが解のすべてである。▨

4 法が互いに素でないとき

法が互いに素でない場合、中国剰余定理はそのままでは使えません。 $x \equiv a \pmod m$ と $x \equiv b \pmod n$ が両立するのは $a \equiv b \pmod{\gcd(m,n)}$ のときに限られ、両立すれば解は法 $\mathrm{lcm}(m,n)$ のもとで一意に定まります（互いに素な場合はこの条件が自動的に満たされ、 $\mathrm{lcm}(m,n)=mn$ に戻ります）。

5 応用：大きな数を「小分けにして」計算する

中国剰余定理は現代の計算機にも直結しています。巨大な整数の演算を1つの大きな法で行う代わりに、いくつかの小さい互いに素な法で並列に計算し、最後に中国剰余定理で1つの答えに復元する、という技法です。多倍長演算のライブラリや、 RSA 暗号の復号（法 $n=pq$ での計算を、法 $p$ ・法 $q$ それぞれで行ってから CRT で合成する）では、この方法で計算量が大きく減ることが知られています。「大きな世界の計算」を「小さな世界の計算の組み合わせ」に分解する、という発想そのものが実装レベルで生きている例です。

§A4.6中国剰余定理

1 2つの条件をまとめる

2 中国剰余定理

3 3条件への拡張

4 法が互いに素でないとき

5 応用：大きな数を「小分けにして」計算する

例題

演習

前提記事