合同算術の解説

誰もがすでに合同算術を使っています:8時の10時間後は6時で、日曜日の翌日は月曜日です。n 歩進むと再び0から始まる数え方には、それ自体で完結した算術があり、そこには規則や意外な発見があって、数論とインターネットを守る暗号の中で中心的な役割を果たしていることがわかります。

0から11までの番号が付いた12個の位置がある時計と、9から2まで文字盤を1周するらせん状の道のり
0から11までの番号が付いた12個の位置がある時計と、9から2まで文字盤を1周するらせん状の道のり

余りと合同

a を n で割って余りだけを残すと、それが a mod n で、0から n − 1 までの数になります。26 = 3 × 7 + 5 なので、26 mod 7 = 5 です。同じ余りを持つ数は n を法として同じようにふるまうので、それらを合同と呼びます:26 ≡ 5 ≡ −2 (mod 7)。カール・フリードリヒ・ガウスは1801年の著書 Disquisitiones Arithmeticae(『整数論考究』)でこの記法を導入し、フェルマーやオイラーによる昔からの観察を独自の算術へと発展させました。n 個の位置がある時計では、すべての整数がその余りの位置に来て、周回した分は忘れられます。

カール・フリードリヒ・ガウス、クリスティアン・アルブレヒト・イェンセンによる1840年の肖像。1801年の『算術研究』で合同の記法 a ≡ b (mod n) を導入した。
カール・フリードリヒ・ガウス、クリスティアン・アルブレヒト・イェンセンによる1840年の肖像。1801年の『算術研究』で合同の記法 a ≡ b (mod n) を導入した。

足し算・引き算・掛け算

3つの普通の演算はいつもどおりに働き、いつでも n を法として簡約してかまいません:和の余りは余りの和の余りに等しく、差と積についても同じです。37 × 48 の一の位を求めるには、一の位どうしだけを掛けます:7 × 8 = 56 なので、一の位は6です。これこそが合同算術をコンピューターにとって便利なものにしている点です:どれほど大きな数でも、途中の値が n² を超えることはありません。

割り算には逆数が必要

割り算は例外です。どちらも mod 10 で6なので 2 × 3 ≡ 2 × 8 (mod 10) ですが、3と8は異なるため、単純に2を約分することはできません。a で割ることは、その逆数、つまり a × x ≡ 1 を満たす数 x を掛けることを意味し、逆数は a と n に共通の因数がないときに限り存在します。それを求めるのが拡張ユークリッドの互除法です:最大公約数を求めるユークリッドの割り算の手順を実行しながら、各ステップで乗数を記録していくので、余りが1になったときの乗数が逆数です。n が素数なら、0以外のすべての数に逆数があり、割り算は常にできます。

累乗、フェルマー、オイラー

累乗は繰り返します。mod 7 での3の累乗をとると、3, 2, 6, 4, 5, 1 となり、その後また3に戻ります。このサイクルの長さが3の位数です。1640年、ピエール・ド・フェルマーは、素数 p について、p が a を割り切らなければ a^(p − 1) ≡ 1 (mod p) となることに気づき、そこからどの位数も p − 1 を割り切ることがわかります。レオンハルト・オイラーはこれを証明し、p − 1 を n と互いに素な値の個数に置き換えて、任意の n に拡張しました。巨大な累乗は繰り返し二乗法で計算します:a, a², a⁴, a⁸ … をそれぞれ直前の値の二乗として n を法として簡約し、指数の2進数の各桁に応じて掛け合わせます。

ピエール・ド・フェルマーの肖像
ピエール・ド・フェルマーの肖像
レオンハルト・オイラーの肖像
レオンハルト・オイラーの肖像

チェックディジットとカレンダー

合同算術は誤りを見つけます。ISBN-10 の最後の桁は、10桁すべての重み付き和が11の倍数になるように選ばれるので、1桁の誤りや隣り合う2桁の入れ替わりはすべて検出されます。銀行カードの番号は mod 10 の Luhn チェックを、IBAN は mod 97 のチェックを使います。カレンダーは mod 7 で動いています:どの日付の曜日もいくつかの余りから求めることができ、万年暦やドゥームズデイ・ルールはこの仕組みで働いています。

暗号

現代の暗号は、計算するのは簡単でも元に戻すのは難しいモジュラー累乗の上に築かれています。1976年のディフィー–ヘルマン鍵共有では、2人が大きな素数を法とする累乗を交換することで、公開された回線上で共有の秘密を取り決めます。1977年にリベスト、シャミア、エーデルマンが発表した RSA は、n を2つの大きな素数の積として、メッセージ m を m^e mod n として暗号化し、2つの素数を知っている人だけが計算できる2つ目の指数 d で復号します。教科書の例では n = 3233 = 61 × 53、e = 17、d = 413 で、65は2790になり、2790は再び65に戻ります。

試してみましょう

モジュラー時計を開くと、30桁までの数について、a mod n や、n を法とする和・差・積・累乗・逆数・商を計算できます。どの答えにもステップが付きます:余りのある割り算、繰り返し二乗法による累乗、または拡張ユークリッドの互除法の表です。時計は、足し算のらせんから累乗のサイクルまで、答えにたどり着く様子を描き、n が小さいときは演算表ですべての答えを一度に見られます。

よくある質問

記号 ≡ はどういう意味ですか?

a ≡ b (mod n) は、a と b を n で割ったときの余りが等しいこと、言い換えれば n が a − b を割り切ることを表します。38 − 2 = 36 は12の倍数なので、38 ≡ 2 (mod 12) です。

mod はプログラミングの % 演算子と同じですか?

正の数なら同じです。負の数については、C、Java、JavaScript など多くの言語が負の余りを返します:これらの言語では −7 % 3 は −1 ですが、−7 mod 3 = 2 です。Python の % は、n が正なら数学の慣習に従います。

n を法とする数の位数とは何ですか?

a^k ≡ 1 (mod n) となる最小の k > 0 のことです。位数は a と n に共通の因数がないときにだけ存在します。2³ = 8 ≡ 1 なので mod 7 での2の位数は3であり、一方 mod 7 での3の位数は6なので、3の累乗は0でないすべての余りを一巡します:3は mod 7 の原始根です。

合同算術を考え出したのは誰ですか?

余りはそれよりずっと前から使われていて、たとえば3世紀から5世紀の中国の剰余定理や、フェルマーとオイラーの研究があります。ガウスは1801年に合同の記法とともに、それを体系的な算術にまとめ上げました。

試してみますか?

ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。

モジュラー時計を開く