合同算術の時計

法(モジュラス)nと演算を選ぼう。結果をmoduloの時計上で確認し、加算・乗算表を調べよう。

計算例 — 合同算術の時計

式	7 x 5 (mod 12)
結果	11

ページを開いたときに計算機が表示する値です。上の入力を変えると再計算されます。

インタラクティブシミュレーションを読み込んでいます...

法が素数なら、割り算が戻ってくる 🖖

モジュロ演算は、a ≡ b (mod n) と表記され、巡回的な法nの下で整数を扱います。この代数系は可換環 Z/nZ を形成します。法pが素数である場合、この環は体となり、ゼロ以外のすべての元が乗法逆元を持ちます。この構造は、現代の暗号、巡回符号、および時計の演算の基礎を成しています。

なぜ「時計算術」と呼ばれるのか 🖖

12時間表示の時計では、11時の4時間後は15時ではなく3時になり、12を過ぎると数は先頭に戻ります。これがまさに合同算術です。a ≡ b (mod n) は、a と b を n で割った余りが等しいことを意味します。つまり 15 ≡ 3 (mod 12) です。要点は、合同算術は割り算の余りだけを残すということで、このツールの時計は数が輪を描いて回る様子を見せてくれます。

9の倍数判定は隠れた合同算術 🖖

「各桁の和が9の倍数なら、その数も9で割り切れる」という昔ながらの規則は、まさに合同算術です。10 ≡ 1 (mod 9) なので、10 のどのべき乗も ≡ 1 となり、ある数はその各桁の和と (mod 9) で合同になります。同じ事実が、手計算を確かめる何世紀も前からの手法「九去法」を支えています。

合同算術 — いつ割れて、いつ割れないのか

あなたはどの合同算術のケースにいますか？

mod n で計算するとは余りだけを残すことで、足し算・引き算・掛け算は無傷で生き残ります。生き残らないのは割り算です。ある数で割れるか、つまり逆元を持つかは、その数が n と因数を共有するかだけで決まります。素数の法が合成数の法とまるで違う振る舞いをするのはそのためです。どのケースかは、演算と n がどんな数かで決まります。

足し算 — n が何であっても必ず行儀がよい 13 + 5 ≡ 6 (mod 12)

素数の法 — 0 でない元すべてで割れる φ(7) = 6 ⇒ gcd(a, 7) = 1 ∀a ≠ 0

合成数の法 — ほとんどの元では割れない 2 × 3 ≡ 0, φ(6) = 2

繰り返しの累乗 — 巡回し、その場所をフェルマーが告げる a^p−1 ≡ 1 (mod p)

足し算 — n が何であっても必ず行儀がよい

わかっていること: どんな法でも構いません。mod n の加算・減算・乗算はつねに定義され、どの元にも加法の相手がいます。

確認すること: 13 + 5 ≡ 6 (mod 12)

計算例: 12 時間の時計：13 + 5 = 18、そして 18 mod 12 = 6。1 時の 5 時間後は 6 時です。

このケースを開く: 時計 mod 12

足し算 — n が何であっても必ず行儀がよい. mod 12 の加算表。どの行も前の行を 1 つずらしたもので、どの値もちょうど一度だけ現れます。どんな法でも構いません。mod n の加算・減算・乗算はつねに定義され、どの元にも加法の相手がいます。 — mod 12 の加算表。どの行も前の行を 1 つずらしたもので、どの値もちょうど一度だけ現れます。

素数の法 — 0 でない元すべてで割れる

わかっていること: n が素数。すると 0 でない元は n と因数を共有せず、どれも乗法の逆元を持ちます。

確認すること: φ(7) = 6 ⇒ gcd(a, 7) = 1 ∀a ≠ 0

計算例: mod 7：3 × 4 = 12 ≡ 5。0 でない 6 つの値 1…6 はすべて可逆で、乗算表には最初の行を除いて 0 が現れません。

このケースを開く: 素数 mod 7

素数の法 — 0 でない元すべてで割れる. mod 7 の乗算表。最初の行より下に 0 はなく、どの行も 1 から 6 の並べ替えです。 n が素数。すると 0 でない元は n と因数を共有せず、どれも乗法の逆元を持ちます。 — mod 7 の乗算表。最初の行より下に 0 はなく、どの行も 1 から 6 の並べ替えです。

合成数の法 — ほとんどの元では割れない

わかっていること: n が合成数。n と互いに素な値だけが逆元を持ち、残りは零因子で、それらで割ることに意味はありません。

確認すること: 2 × 3 ≡ 0, φ(6) = 2

計算例: mod 6：2 × 4 = 8 ≡ 2。gcd(2,6) = 2、gcd(4,6) = 2 なので 2 も 4 も可逆ではありません。単元は 1 と 5 だけ、6 つのうち 2 つです。

このケースを開く: 合成数 mod 6

合成数の法 — ほとんどの元では割れない. mod 6 の乗算表。0 が散らばっていて、並べ替えになっている行は 2 つだけです。 n が合成数。n と互いに素な値だけが逆元を持ち、残りは零因子で、それらで割ることに意味はありません。 — mod 6 の乗算表。0 が散らばっていて、並べ替えになっている行は 2 つだけです。

繰り返しの累乗 — 巡回し、その場所をフェルマーが告げる

わかっていること: mod n での累乗。素数 p と p で割り切れない a について、指数は p − 1 を割る周期で巡ります。

確認すること: a^p−1 ≡ 1 (mod p)

計算例: mod 13：7¹² ≡ 1。フェルマーの小定理が 1 から 12 までのどの底についてもこれを保証し、大きな累乗を一つも計算せずに済みます。

このケースを開く: フェルマー mod 13

繰り返しの累乗 — 巡回し、その場所をフェルマーが告げる. mod 13 での各底の累乗。指数 12 の列は、どの単元についても 1 に戻ります。 mod n での累乗。素数 p と p で割り切れない a について、指数は p − 1 を割る周期で巡ります。 — mod 13 での各底の累乗。指数 12 の列は、どの単元についても 1 に戻ります。

全プロセスの詳細解説

7 12 mod 13 の評価（フルグリッド上） 5 ステップ
7¹² を書き下すことなく 7¹² mod 13 を計算せよ。これは n = 13, a = 7, k = 12 における a^k 演算であり、グリッドは a^k mod 13 の完全な表である。
1. 7¹² は 13 841 287 201 であり、0 から 12 の間の値になるはずの答えに対して 11 桁の数である。剰余演算は乗法を行っても保たれる。積の剰余は各因数の剰余のみに依存するため、最後ではなく各ステップの後に剰余をとる（簡約する）ことができる。
  
  $7^{12} = 13841287201, x y mod n = ((x mod n) (y mod n)) mod n$
2. 四則演算を行う前に、フェルマーの小定理によって答えは確定している。素数 p と p で割り切れない a に対して、a^p−1 ≡ 1 であり、ここでは p = 13 かつ k は正確に p − 1 であるため、結果は 1 となる。したがって、以下の記述は答えの探求というよりも定理の検証である。
  
  $p = 13 prime, 13 ∤ 7 ⟹ 7^{12} = 7^{p - 1} \equiv 1 (mod 13)$
3. 自乗（2 乗）は指数を 2 倍にするため、3 回の自乗で 7⁸ に達する。各行は次の行が始まる前に剰余をとる（簡約する）ため、計算全体のどの数値も 100 を超えない。
  
  $7^{2} = 49 \equiv 10, 7^{4} \equiv 1 0^{2} = 100 \equiv 9, 7^{8} \equiv 9^{2} = 81 \equiv 3 (mod 13)$
4. 12 は 8 + 4 であり、これらの累乗は両方とも途中で計算されているため、あと 1 回の乗法で完了する。12 個の 7 を左から右へ順に掛け合わせる場合に必要な 11 回の乗法に対して、合計 4 回の乗法で済む。そして、この計算量の削減は法（モジュラス）ではなく指数に応じて大きくなる。
  
  $12 = 110 0_{2} = 8 + 4 ⟹ 7^{12} \equiv 7^{8} \cdot 7^{4} \equiv 3 \times 9 = 27 \equiv 1 (mod 13)$
5. 7^k ≡ 1 を満たす最小の k を意味する 7 の位数は 12 を割り切らなければならないため、1、2、3、4、6、12 のいずれかとなる。5 つの真の約数を検証するとそれらすべてが除外されるため、位数は正確に 12 である。
  
  $7^{1} \equiv 7, 7^{2} \equiv 10, 7^{3} \equiv 5, 7^{4} \equiv 9, 7^{6} \equiv 12 ⟹ ord_{13} (7) = 12$
解答

3 回の自乗と最後の乗法により、エラーなしで a = 7 に対するツールの行が再現される。すなわち、k = 2 で 10、k = 4 で 9、k = 8 で 3、そしてフェルマーが予言した通り k = 12 で 1 となる。位数は 12 でありその真の約数ではないため（位数の検証では k = 6 で 12 が必要であり、これは 1 ではない）、その行は 1 から 12 までの順列となり、すべての非ゼロ剰余に正確に 1 回ずつ到達する。これにより 7 は mod 13 における原始根となる。ここで、行を逆方向に読んでみる。11 が与えられたとき、k を求めよ。これに対する繰り返し二乗法（square-and-multiply）は存在せず、探索を行うしかない。順方向が容易で逆方向が困難というこの非対称性こそが、ディフィー・ヘルマン鍵共有の基盤全体である。このアルゴリズムは表には不可能なスケールで拡張される。2048 ビットの指数に必要な剰余乗法は高々約 4 000 回であるが、それが示す累乗を書き下すにはおよそ 2.7 × 10⁶¹⁶ 桁が必要となる。

$ord_{13} (7) = 12 ⟹ {7^{k} mod 13}_{k = 1}^{12} = {1, 2, \dots, 12}$

学習の道すじ

2つの値が衝突するとき

この次に誕生日のパラドックス

参考文献 (1)

The congruence sign this tool prints, and the book that introduced it: C. F. Gauss, Disquisitiones arithmeticae. Leipzig, 1801 — Section I defines a ≡ b (mod n); Section II is where a prime modulus starts behaving like a field. Digitised by the Smithsonian Libraries.

42Math チーム · 更新 2026-08-17

公表された資料と照合しています。訂正のご指摘を歓迎します。編集方針 · 訂正

数学のレッスン一覧 →

例題

時計 mod 12 - 時計の算術:13 ≡ 1 (mod 12) なので、13+5は6に巡回する。
素数 mod 7 - 素数を法とする場合:0でない乗算の行は置換として振る舞う。
合成数 mod 6 - 合成数を法とする場合、gcd(row,n) > 1 となる行は繰り返しパターンを示す。
フェルマー mod 13 - フェルマー型のパターン:素数pとgcd(a,p)=1に対して a^(p-1) ≡ 1 mod p が成り立つ。