中国の剰余定理
中国の剰余定理の最も基本的な形は次のような形式で述べることができる。
中国の剰余定理(ちゅうごくのじょうよていり、英: Chinese remainder theorem)は、中国の算術書『孫子算経』に由来する整数の剰余に関する定理である。あるいは、それを一般化した可換環論における定理でもある。中国人の剰余定理(ちゅうごくじんのじょうよていり)、孫子の定理(そんしのていり、英: Sunzi's theorem)とも呼ばれる。
『孫子算経』には、「3で割ると2余り、5で割ると3余り、7で割ると2余る数は何か」という問題とその解法が書かれている。中国の剰余定理は、この問題を他の整数についても適用できるように一般化したものである。
引き続き『孫子算経』の問題を考える。3 と 5 × 7 = 35, 5 と 3 × 7 = 21, 7 と 3 × 5 = 15 はそれぞれ互いに素であるから、拡張されたユークリッドの互除法により、 (m, n) = (3, 35), (5, 21), (7, 15) それぞれについて、不定方程式
mx + ny = 1
の整数解(特殊解)が計算できる。具体的には、
3 × 12 + 35 × (−1) = 1,
5 × (−4) + 21 × 1 = 1,
7 × (−2) + 15 × 1 = 1
となる。したがって、以下の合同式が成立する:
-35 ≡ 1 (mod 3),
21 ≡ 1 (mod 5),
15 ≡ 1 (mod 7).
すると、連立合同式
x ≡ a1 (mod 3),
x ≡ a2 (mod 5),
x ≡ a3 (mod 7)
の一つの解が
x = −35a1 + 21a2 + 15a3
であることが容易に確かめられる。しかも定理により解は 3 × 5 × 7 = 105 を法として一意的であったから、すべての解は k を任意の整数として、
−35a1 + 21a2 + 15a3 + 105k
と表されることもわかる。つまり、これがこの問題の一般解である。
do#.UdgOFeaCjIU G・H・ハーディ、E.M.ライト(英語版)『数論入門I』示野信一・矢神毅 訳、シュプリンガー・フェアラーク東京〈シュプリンガー数学クラシックス8〉、2001年7月。ISBN 978-4-431-70848-3。http://homepage1.nifty.com/shimeno/hr/。 - 原書第5版(1979年)の邦訳。 G・H・ハーディ、E・M・ライト『数論入門I』示野信一・矢神毅 訳、丸善出版〈シュプリンガー数学クラシックス8〉、2012年7月。ISBN 978-4-621-06226-5。http://pub.maruzen.co.jp/book_magazine/book_data/search/9784621062265.html。 - ハーディ & ライト (2001)の再出版。
前原昭二『数学基礎論入門』朝倉書店〈復刊基礎数学シリーズ23〉、2006年3月20日(原著1977年6月1日)。ISBN 978-4-254-11723-3。http://www.asakura.co.jp/books/isbn/978-4-254-11723-3/。