中国の剰余定理

出典: フリー百科事典『ウィキペディア（Wikipedia）』

中国の剰余定理（ちゅうごくのじょうよていり）あるいは中国人の剰余定理（ちゅうごくじんのじょうよていり）(Chinese Remainder Theorem) は『孫子算経 』に由来する整数の剰余に関する定理である。そもそもの定理の発見者や発見時期は定かではないが、前述の『孫子算経』から孫子の名を取って孫子の定理（そんしのていり）とも呼ばれる。アメリカの数学者L.E.Dicksonが、数論の歴史についての著書の中で呼んだのが最初であるとされる。

3 ～ 5 世紀ごろ成立したとされる中国の算術書『孫子算経』には「3 で割れば 2 余り，5 で割れば 3 余り， 7 で割れば 2 余るような数は何か」という問いと解法が書かれている。中国の剰余定理はこの問いを他の整数についても適用できるように一般化したものである。

[編集] 定理

中国の剰余定理の最も基本的な形は次のような形式で述べることができる。

与えられた二つの整数 m, n が互いに素ならば、任意に与えられる整数 a, b に対し、連立合同式

$x \equiv a \pmod m,$

$x \equiv b \pmod n$

を満たす整数 x が mn を法として唯一つ存在する。

これは明らかに次のように拡張できる。すなわち

与えられた k 個の整数 m₁, m₂, ...,m_k がどの二つも互いに素ならば、任意に与えられる整数a₁, a₂, ..., a_k に対し

$\begin{matrix} x &\equiv& a_1 \pmod{m_1},\\ x &\equiv& a_2 \pmod{m_2},\\ & \vdots & \\ x &\equiv& a_k \pmod{m_k} \end{matrix}$

を満たす整数 x が m₁m₂…m_k を法として唯一つ存在する。

孫子算経の「3 で割れば 2 余り，5 で割れば 3 余り， 7 で割れば 2 余るような数」について当てはめてみると、定理は

$x \equiv 2 \pmod 3,$

$x \equiv 3 \pmod 5,$

$x \equiv 2 \pmod 7$

を満たすような整数 x が存在することを示している。しかもこの x は、3 × 5 × 7 = 105 を法として一意的であるといっている。つまり、ある y があってこの y も上の式の解であったならば、必ず

$x \equiv y \pmod{105}$

が成立する。

[編集] 解法

定理により解が存在することは保証されたが、実際に解を計算できるかどうかは別問題である。中国の剰余定理の場合は解を計算することも容易である。解くための方法は幾つかある。

[編集] 互除法

「3,5,7」の例で解法を考えてみる。ユークリッドの互除法を使えば

2 × 3 + (-1) × 5 = 1,

(-2) × 3 + 1 × 7 = 1,

3 × 5 + (-2) × 7 = 1

である。これをつかうと

-35 = ((-1) × 5)×(1 × 7) ≡ 1 (mod 3), ≡ 0 (mod 5), ≡ 0 (mod 7),

-84 = (2 × 3)×((-2) × 7) ≡ 0 (mod 3), ≡ 1 (mod 5), ≡ 0 (mod 7),

-90 = ((-2) × 3)×(3 × 5) ≡ 0 (mod 3), ≡ 0 (mod 5), ≡ 1 (mod 7)

が成り立つことがわかるので、

2 × (-35) + 3 × (-84) + 2 × (-90) = -502

は一つの解である。すると -502 + 3 × 5 × 7 × k (k ∈ Z) も明らかに解である。また定理により解は 3 × 5 × 7 = 105 を法として一意的であったから、逆にすべての解は -502 + 105k (k ∈ Z) の形をしていることも分かる。つまり、これがこの問いの一般の解である。