中国剰余定理（高校数学）

$0$ から $14$ までで、$3$ で割って $2$ 余る数は
$$ 2,\ 5,\ 8,\ 11,\ 14 $$
である。これを $5$ で割った余りは順に $2,0,3,1,4$ で、$3$ になるのは $8$ だけである。$0$ から $14$ までには条件をみたす数がちょうど 1 つある。

$0$ から $14$ までの $15$ 個の数を、「$3$ で割った余り」を行、「$5$ で割った余り」を列とする $3\times5$ の表に置く（図 1）。たとえば $8$ は、$3$ で割って $2$ 余り $5$ で割って $3$ 余るので、2 行目・3 列目（行・列の番号は $0$ から数える）に入る。$15$ 個の数が $15$ 個のマスにちょうど 1 つずつ入り、空いたマスも、2 つ入るマスもない。

$4$ で割って $1$ 余り、$6$ で割って $2$ 余る数はない。$4$ で割って $1$ 余る数は奇数、$6$ で割って $2$ 余る数は偶数だからである。一方、$4$ で割って $1$ 余り、$6$ で割って $3$ 余る数は $9,21,33,\dots$ とあり、$12$ ずつ離れている（$24$ ずつではない）。$4$ と $6$ は公約数 $2$ をもつので、ex-crths-start-table のようにはいかない。

ex-crths-start-find の連立合同式 $x\equiv2\pmod3$、$x\equiv3\pmod5$ の解の全体は、$x\equiv8\pmod{15}$ をみたす整数全体
$$ \dots,\ -7,\ 8,\ 23,\ 38,\ \dots $$
である（thm-crths-main で示す）。$-7$ も、$3$ で割ると $-7=3\cdot(-3)+2$ で $2$ 余り、$5$ で割ると $-7=5\cdot(-2)+3$ で $3$ 余る。

1. $3\cdot2+5\cdot(-1)=6-5=1$ なので $(s,t)=(2,-1)$ である。
2. $15=7\cdot2+1$ なので $15\cdot1+7\cdot(-2)=1$、つまり $(s,t)=(-2,1)$ で $7\cdot(-2)+15\cdot1=1$ である。
3. $5$ は $3k$ を割るなら $k$ を割る。たとえば $3k=45$ なら $k=15$ で、確かに $5$ の倍数である。

1. $x\equiv2\pmod3$、$x\equiv3\pmod5$。ex-crths-bezout の (1) から $s=2$、$t=-1$ で、$nt=5\cdot(-1)=-5$、$ms=3\cdot2=6$ である。
   $$ x_0=2\cdot(-5)+3\cdot6=-10+18=8 $$
   なので、解は $x\equiv8\pmod{15}$ である。
2. 同じ法で、余りの組を変えても $nt=-5$ と $ms=6$ はそのまま使える。$-5\equiv10\pmod{15}$ なので、$x\equiv a\pmod3$、$x\equiv b\pmod5$ の解は
   $$ x\equiv10a+6b\pmod{15} $$
   である。$10$ は「$3$ で割って $1$ 余り、$5$ で割り切れる数」、$6$ は「$3$ で割り切れ、$5$ で割って $1$ 余る数」である。たとえば $a=1$、$b=4$ なら $x\equiv10+24=34\equiv4$ で、確かに $4$ は $3$ で割って $1$ 余り、$5$ で割って $4$ 余る（図 1 の 1 行目・4 列目）。

$3$ で割ると $2$ 余り、$5$ で割ると $3$ 余り、$7$ で割ると $2$ 余る数を求める。この問いは古い中国の算術書の問題として知られ、Ste17 Question 2.2.1 にも紹介されている。
段 1。$x\equiv2\pmod3$ なので $x=2+3t$（$t$ は整数）と書ける。$x\equiv3\pmod5$ に代入すると $2+3t\equiv3$、つまり $3t\equiv1\pmod5$ である。$3\cdot2=6\equiv1$ なので $t\equiv2\pmod5$、$t=2+5u$ と書ける。よって $x=2+3(2+5u)=8+15u$ である。
段 2。$x\equiv2\pmod7$ に代入すると $8+15u\equiv2\pmod7$ である。$8\equiv1$、$15\equiv1\pmod7$ なので $1+u\equiv2$、つまり $u\equiv1\pmod7$、$u=1+7v$ と書ける。よって
$$ x=8+15(1+7v)=23+105v $$
である。
答えは $x\equiv23\pmod{105}$ で、たとえば $23=3\cdot7+2=5\cdot4+3=7\cdot3+2$ である。

$x\equiv2\pmod3$、$x\equiv3\pmod4$、$x\equiv1\pmod5$ を解く。$3,4,5$ はどの 2 つも互いに素なので、解は法 $60$ でただ 1 つであり、ex-crths-successive と同じ逐次代入で $x\equiv11\pmod{60}$ と求まる。

$\operatorname{lcm}(4,6)=12$、$\operatorname{lcm}(3,5)=15$、$\operatorname{lcm}(6,10)=30$ である。$\gcd(m,n)\cdot\operatorname{lcm}(m,n)=mn$ が成り立ち（$2\cdot12=24$、$1\cdot15=15$、$2\cdot30=60$）、互いに素なら $\operatorname{lcm}(m,n)=mn$ である。この関係は素因数分解を使って示せる（素因数分解の一意性。本記事では証明しない）。下の比較表でだけ使う。

1. $x\equiv1\pmod4$、$x\equiv3\pmod6$。$g=2$ は $1-3=-2$ を割るので解がある。$x=1+4t$ を代入して $4t\equiv2\pmod6$ で、$t\equiv2\pmod3$（$t=2$ で $8\equiv2$）なので $x=1+4(2+3u)=9+12u$ である。解は $x\equiv9\pmod{12}$ で、法 $24$ で数えると $9$ と $21$ の $2$ つになる。
2. $x\equiv1\pmod4$、$x\equiv2\pmod6$。$g=2$ は $1-2=-1$ を割らないので解はない（ex-crths-start-fail）。
   同じ型の例 (3) を開く

   (3) $x\equiv7\pmod{10}$、$x\equiv3\pmod{12}$。$g=2$ は $7-3=4$ を割る。$x=7+10t$ を代入して $10t\equiv-4\pmod{12}$。$t=2$ で $20\equiv8\equiv-4$ なので、$x=27$ が解で、解は $x\equiv27\pmod{60}$ である（$\operatorname{lcm}(10,12)=60$）。$27=10\cdot2+7=12\cdot2+3$ である。

$7$ と $11$ は $\psi(7)=(1,2)$、$\psi(11)=(2,1)$ である。

• 和：$7+11=18\equiv3\pmod{15}$ で $\psi(3)=(0,3)$。成分ごとに足すと $(1+2,\ 2+1)=(3,3)\equiv(0,3)$ で一致する。
• 積：$7\cdot11=77=15\cdot5+2$ なので $\psi(2)=(2,2)$。成分ごとに掛けると $(1\cdot2,\ 2\cdot1)=(2,2)$ で一致する。

$15$ が $x^2-1$ を割ることは、$3$ と $5$ の両方が $x^2-1$ を割ることと同じである（両方が割るなら、thm-crths-main の証明の段 5 と同じく $15$ も割る）。法 $3$ では $x\equiv1,2$（$\pm1$）、法 $5$ では $x\equiv1,4$（$\pm1$）が解で、それぞれ $2$ 個ある。組は $2\cdot2=4$ 通りで、対応する $x$ は
$$ x\equiv1,\ 4,\ 11,\ 14\pmod{15} $$
の $4$ 個である（図 3）。たとえば $4^2=16=15+1$、$11^2=121=15\cdot8+1$ である。奇数の素数を法とすると $x^2\equiv1$ の解は $\pm1$ の $2$ 個だけだが（合同式の割り算と逆元）、法 $15$ では $4$ 個になる。法 $105=3\cdot5\cdot7$ なら $2\cdot2\cdot2=8$ 個である。

下 2 桁は $100$ で割った余りである。$100=4\cdot25$ で、$4$ と $25$ は互いに素なので、法 $4$ と法 $25$ に分けて計算する。
段 1（法 $4$）。$7\equiv-1\pmod4$ なので $7^{2026}\equiv(-1)^{2026}=1\pmod4$ である。
段 2（法 $25$）。$7^2=49\equiv-1\pmod{25}$ なので $7^4\equiv1$ である。$2026=4\cdot506+2$ なので $7^{2026}=(7^4)^{506}\cdot7^2\equiv49\equiv24\pmod{25}$ である。
段 3（まとめる）。$x\equiv1\pmod4$、$x\equiv24\pmod{25}$ を解く。$x=24+25t$ とおくと、$24\equiv0$、$25\equiv1\pmod4$ なので $x\equiv t\equiv1\pmod4$、$t=1$ として $x=49$ である。よって $7^{2026}$ の下 2 桁は $49$ である。

$4$ と $6$ は公約数 $2$ をもつ。$x\equiv1\pmod4$ なら $x$ は奇数、$x\equiv2\pmod6$ なら $x$ は偶数なので、両方をみたす $x$ はない。prf-crths-main の段 1 で使った $4s+6t=1$ となる $s,t$ は、左辺がいつも偶数なのでとれない。余りの組 $(1,2)$ は図 2 の灰色のマスで、thm-crths-general の条件（$2$ が $1-2$ を割る）をみたさない。

$x\equiv1\pmod4$、$x\equiv3\pmod6$ の解は $x\equiv9\pmod{12}$ である（ex-crths-general-use の (1)）。法 $24$ で数えると $9$ と $21$ の $2$ 個あり、「法 $mn=24$ でただ 1 つ」は成り立たない。$21-9=12$ は $4$ でも $6$ でも割り切れるが、$24$ では割り切れない。prf-crths-main の段 5 で互いに素を使ったところが崩れている。

$4,6,9$ の 3 つ全部の公約数は $1$ だけである。しかし $x\equiv1\pmod4$、$x\equiv0\pmod6$、$x\equiv0\pmod9$ には解がない。最初の 2 つだけで、奇数と偶数の食い違いが起きるからである。cor-crths-many で「どの 2 つも互いに素」を仮定したのは、2 つずつまとめる段で thm-crths-main を使うためである。