中国剰余定理の公式｜余りの条件をみたす数がただ1つある証明・孫子の問題（23）・下2けたの求め方【大学数学・東大京大レベル】

中国剰余定理の公式｜余りの条件をみたす数がただ1つある証明・孫子の問題（23）・下2けたの求め方【大学数学・東大京大レベル】

合格大作戦 算数・数学公式辞典 › 数と式

大学受験

x≡a ⁣ ⁣(modm),  x≡b ⁣ ⁣(modn) ⟹ x は mn を法としてただ1つx\equiv a\!\!\pmod m,\ \ x\equiv b\!\!\pmod n\ \Longrightarrow\ x\ \text{は}\ mn\ \text{を法としてただ1つ}

m, nm,\ n が互いに素のとき。例：x≡2(mod3), x≡3(mod5), x≡2(mod7)  ⟺  x≡23(mod105)x\equiv2\pmod3,\ x\equiv3\pmod5,\ x\equiv2\pmod7\iff x\equiv23\pmod{105}

この公式のポイント

  • 割る数が互いに素なら、余りの条件をみたす数は必ずある
  • その数は積 mnmn ごとにただ1つ
  • 実際の計算は x=a+mkx=a+mk とおいて不定方程式
  • 互いに素でないと解がないこともある
うかるくん

うかるくん

3で割ると2余り、5で割ると3余る数って、必ずあるの？

合格先生

合格先生

割る数が互いに素なら必ずある。しかも mnmn ごとにただ1つだ。余りの組が全部ちがうから、もれなく1回ずつ出てくるんだぞ。

中国剰余定理

「3で割ると2余り、5で割ると3余る数は？」のように、いくつかの数で割った余りを指定したとき、それをみたす数がいつあり、どれだけあるかを教えてくれる定理です。

割る数が互いに素のとき

mm と nn が互いに素（最大公約数が1）のとき、どんな整数 a, ba,\ b についても

x≡a(modm),x≡b(modn)x\equiv a\pmod m,\qquad x\equiv b\pmod n

をみたす整数 xx が存在し、それは mnmn を法としてただ1つ（0≤x<mn0\le x<mn の範囲にちょうど1つ）。

3つ以上の条件でも、割る数がどの2つも互いに素なら同じことが言える（法は全部の積）。

5で割った余り3で割った余り01234012012345678910111213140〜14 の15個が15マスに1つずつ入る3で割って2余り、5で割って3余る → 8
m=3, n=5m=3,\ n=5 の場合：0〜14 の余りの組はすべてちがい、15マスに1つずつ入る

名前は、中国の古い数学書『孫子算経』にある「3で割ると2余り、5で割ると3余り、7で割ると2余る数は何か」という問題に由来します（答えは23）。日本の和算では、同じ考え方が「百五減算」として知られています。

なぜ成り立つのか（証明）

存在すること：x≡a(modm)x\equiv a\pmod m をみたす数のうち、次の nn 個を考えます。

a,a+m,a+2m,…,a+(n−1)ma,\quad a+m,\quad a+2m,\quad\dots,\quad a+(n-1)m

この nn 個を nn で割った余りはすべてちがいます。もし a+ima+im と a+jma+jm（0≤j<i≤n−10\le j<i\le n-1）の余りが同じなら、差 (i−j)m(i-j)m は nn で割り切れます。mm と nn は互いに素なので、i−ji-j が nn で割り切れることになりますが、0<i−j<n0<i-j<n なので矛盾です。

余りは 00 から n−1n-1 までの nn 種類しかないので、nn 個の余りにはどの値もちょうど1回ずつ出てきます（鳩の巣原理と同じ考え方）。だから nn で割った余りが bb と同じになるものが必ずあり、それが求める xx です。

ただ1つであること：x, yx,\ y がどちらも条件をみたせば、x−yx-y は mm でも nn でも割り切れます。m, nm,\ n は互いに素なので x−yx-y は mnmn で割り切れ、x≡y(modmn)x\equiv y\pmod{mn} です。

3つ以上のとき：はじめの2つの条件を「mnmn で割った余り」の1つの条件にまとめ、次の条件と組み合わせることをくり返します。

実際に求めるときは、x=a+mkx=a+mk とおいて mk≡b−a(modn)mk\equiv b-a\pmod n を解きます。これは1次不定方程式を解くことと同じです。

① 3で割ると2余る数25811141720232629323538② そのうち5で割ると3余る（15ごと）25811141720232629323538③ さらに7で割ると2余る（105ごと）25811141720232629323538答え 23（次は 23＋105＝128）
孫子の問題：条件を1つずつ加えてしぼりこむと23。周期は 3×5×7=1053\times5\times7=105

大学受験での使い方

大学受験

例題1（孫子の問題）

3で割ると2余り、5で割ると3余り、7で割ると2余る正の整数のうち、最小のものを求めなさい。

解き方

3で割ると2余る数は 2, 5, 8, 11, …2,\ 5,\ 8,\ 11,\ \dots。このうち5で割ると3余る最初の数は 88 なので、2つの条件をまとめると x≡8(mod15)x\equiv8\pmod{15}。

8, 23, 38, …8,\ 23,\ 38,\ \dots のうち7で割ると2余るのは 2323（23=7⋅3+223=7\cdot3+2）。

3、5、7はどの2つも互いに素なので、解は x≡23(mod105)x\equiv23\pmod{105} で、最小の正の整数は 2323。

答え　2323

大学受験

例題2（1次不定方程式で解く）

x≡4(mod7)x\equiv4\pmod 7、x≡6(mod11)x\equiv6\pmod{11} をみたす整数 xx をすべて求めなさい。

解き方

x=7k+4x=7k+4 とおくと 7k+4≡6(mod11)7k+4\equiv6\pmod{11}、つまり 7k≡2(mod11)7k\equiv2\pmod{11}。

7⋅8=56=5⋅11+17\cdot8=56=5\cdot11+1 より 7⋅8≡1(mod11)7\cdot8\equiv1\pmod{11}。両辺に 88 をかけて k≡16≡5(mod11)k\equiv16\equiv5\pmod{11}。

k=11l+5k=11l+5 を入れて x=7(11l+5)+4=77l+39x=7(11l+5)+4=77l+39。（確かめ：39=7⋅5+4=11⋅3+639=7\cdot5+4=11\cdot3+6）

答え　x=77l+39x=77l+39（ll は整数）

大学受験

例題3（下2けたを求める）

21002^{100} の下2けたを求めなさい。

解き方

100=4⋅25100=4\cdot25 で、44 と 2525 は互いに素。それぞれで割った余りを調べます。

21002^{100} は4で割り切れるので 2100≡0(mod4)2^{100}\equiv0\pmod4。

210=1024=41⋅25−12^{10}=1024=41\cdot25-1 より 210≡−1(mod25)2^{10}\equiv-1\pmod{25}。よって 2100=(210)10≡(−1)10=1(mod25)2^{100}=(2^{10})^{10}\equiv(-1)^{10}=1\pmod{25}。

25で割ると1余る数 1, 26, 51, 761,\ 26,\ 51,\ 76 のうち4の倍数は 7676。中国剰余定理より、100で割った余りはただ1つに決まり 2100≡76(mod100)2^{100}\equiv76\pmod{100}。

答え　7676

高校の範囲をこえる内容と入試での使い方

「3で割ると2余り、5で割ると3余る数」のような問題は、数学A「数学と人間の活動」の整数の性質で、1次不定方程式などを使って解く問題として出てきます。ただし「中国剰余定理」という名前と、一般の形の証明は高校の教科書の中心内容ではなく、大学の整数論・代数学で学ぶ発展内容です。

  • 答案での使い方：具体的な数の問題では、x=7k+4x=7k+4 とおいて不定方程式を解く、または候補を順に調べる方法で、答えを実際に求めて書きます。「中国剰余定理より」とだけ書いて済ませるのは避けましょう。
  • 存在や個数を問う証明問題：「余りの組がすべてちがう」ことを使う問題では、上の証明（nn 個の余りがすべてちがう）の流れを答案に書きます。
  • 大きな数の余り：例題3のように、法を互いに素な数に分けて計算すると楽になります。
  • 検算：求めた xx を、それぞれの数で実際に割って確かめます。
  • 難関大の入試では、この定理が背景になっている整数問題があります。

よくある間違い

腕でバツを作る合格先生

合格先生

割る数が互いに素でないと、解がないこともある。4で割ると1余り、6で割ると2余る数は存在しないぞ。

  • 互いに素でない数で使う：x≡1(mod4)x\equiv1\pmod4 と x≡2(mod6)x\equiv2\pmod6 は、前者は奇数、後者は偶数を求めるので解がない。
  • 答えを1つだけ書く：「すべて求めよ」なら、mnmn ごとにくり返す無数の解（x≡23(mod105)x\equiv23\pmod{105} など）を答える。
  • まとめた法を和にする：2つの条件をまとめた法は m+nm+n ではなく mnmn。

練習問題

○の札を持つうかるくん

うかるくん

候補を書き出して、順にしぼりこもう！

  1. 大学受験 3で割ると1余り、4で割ると2余る正の整数のうち、最小のものを求めなさい。
    答えと解説を見る4で割ると2余る数 2, 6, 10, …2,\ 6,\ 10,\ \dots のうち3で割ると1余る最初の数は 1010。一般には x≡10(mod12)x\equiv10\pmod{12}。答え 1010
  2. 大学受験 x≡3(mod5)x\equiv3\pmod5、x≡5(mod8)x\equiv5\pmod8 をみたす整数 xx を、4040 を法として求めなさい。
    答えと解説を見るx=8k+5x=8k+5 とおくと 8k+5≡3k≡3(mod5)8k+5\equiv3k\equiv3\pmod5 より k≡1(mod5)k\equiv1\pmod5。x=8(5l+1)+5=40l+13x=8(5l+1)+5=40l+13。答え x≡13(mod40)x\equiv13\pmod{40}
  3. 大学受験 4で割ると1余り、5で割ると2余り、7で割ると3余る正の整数のうち、最小のものを求めなさい。
    答えと解説を見る7で割ると3余る数 3, 10, 17, …3,\ 10,\ 17,\ \dots のうち5で割ると2余る最初の数は 1717（x≡17(mod35)x\equiv17\pmod{35}）。17=4⋅4+117=4\cdot4+1 で4で割ると1余るので条件をみたす。答え 1717（一般には x≡17(mod140)x\equiv17\pmod{140}）

関連する公式

よくある質問

中国剰余定理とは？

割る数 m と n が互いに素なら、m で割った余りと n で割った余りを指定したとき、それをみたす整数が mn ごとにただ1つあるという定理です。

なぜ「中国」の名前がついているのですか？

中国の古い数学書『孫子算経』に、3で割ると2余り、5で割ると3余り、7で割ると2余る数を求める問題があることに由来します。答えは23です。

実際にはどうやって求めますか？

x＝a＋mk とおいて、n で割った余りの条件から k を求めます。1次不定方程式を解くのと同じです。小さな数なら候補を順に調べても求められます。

割る数が互いに素でないとどうなりますか？

解がないこともあります。たとえば4で割ると1余り、6で割ると2余る数は、奇数と偶数の条件が矛盾するのでありません。

あわせて読みたい

出典・参考

  • 文部科学省「高等学校学習指導要領（平成30年告示）」数学A（数学と人間の活動）
  • 大学初年級の整数論・代数学（範囲外の発展内容）

最終更新：2026年10月11日／作成：大学受験合格大作戦