MENU
  1. トップ
  2. 基礎体系
  3. 基礎数学
  4. 基礎 数学A
  5. 【基礎 数学(数学A)】Module 10：整数の性質(3) 合同式

【基礎 数学(数学A)】Module 10：整数の性質(3) 合同式

当ページのリンクには広告が含まれています。

本モジュールの目的と構成

前モジュールまでに、我々は整数が「素数」という原子から構成されていること、そして「ユークリッドの互除法」が整数の関係性を解き明かす強力なアルゴリズムであることを学びました。本モジュールでは、整数論における最も強力でエレガントな言語であり、思考の道具である合同式 (Modular Arithmetic) の世界を深く探求します。

合同式の考え方の本質は、「割り算の余り（剰余）」のみに着目し、同じ余りを持つ整数を「同じ」ものと見なす、という大胆な視点の転換にあります。時計の文字盤を思い浮かべてください。13時は1時であり、14時は2時です。これは、時間を12で割った余りの世界、すなわち mod 12 の世界で我々が思考していることに他なりません。この「循環する数の世界」を数学的に厳密に体系化したのが、19世紀の偉大な数学者カール・フリードリヒ・ガウスによって導入された合同式です。

この新しい数体系を学ぶことで、巨大な数のべき乗の余りを求める問題や、曜日や周期に関する問題、さらには不定方程式の解法までが、驚くほどシンプルで統一的なアプローチで解決できるようになります。合同式は、複雑な整数の世界を、有限個の「剰余類」というシンプルな世界に写し取り、その中での計算に置き換える、強力な「次元削減」ツールなのです。

本モジュールは、以下の学習項目を通じて、この剰余の世界の文法と応用を体系的にマスターすることを目指します。

  1. 合同式の定義とその性質: 「aとbはmを法として合同である」という概念を厳密に定義し、それが等式の性質（反射律、対称律、推移律）とよく似た、整合性のとれた関係であることを確認します。
  2. 合同式の四則演算: 合同式の世界で、足し算、引き算、掛け算がどのように行えるか、その基本ルールを確立します。特に、割り算が通常の計算とは異なり、特別な注意を要することを見ます。
  3. 一次合同方程式の解法: ax ≡ b (mod m) という、合同式の世界における一次方程式の解法を学びます。これは一次不定方程式と密接に関連しています。
  4. 合同式を用いた余りの問題: 合同式の最も直接的な応用として、巨大な数のべき乗の余りを、計算機なしで効率的に求めるテクニックを習得します。
  5. 曜日の計算: 曜日が7を法とする合同式の世界でモデル化できることを見、未来や過去の曜日を計算する問題に応用します。
  6. 繰り返し模様と合同式: 数の並びや図形など、周期的に繰り返すあらゆる現象が、合同式の考え方で分析できることを探ります。
  7. オイラーの定理: フェルマーの小定理を、法が合成数の場合に一般化した、強力なオイラーの定理を学びます。そのために不可欠なオイラーのφ関数も導入します。
  8. ウィルソンの定理: ある数が素数であるための、階乗を用いた美しく驚くべき必要十分条件、ウィルソンの定理を紹介します。
  9. 合同式の応用（暗号理論への導入）: 合同式、特にフェルマーの定理やオイラーの定理が、現代社会を支える公開鍵暗号（RSA暗号）の理論的根幹となっていることを学び、その仕組みの一端に触れます。
  10. 合同式を用いた整数問題の解法: 整数問題において、合同式が「解の候補を絞り込む」「解の不存在を証明する」ための強力なフィルターとして、いかに有効であるかを、様々な問題を通じて体得します。

このモジュールを修了する時、皆様は、整数の問題を「余り」という新しいレンズを通して見ることで、その本質的な構造をより鮮やかに見抜く能力を身につけているはずです。その能力は、皆様の整数問題に対するアプローチを、根本から変革することでしょう。

目次

1. 合同式の定義とその性質

整数問題を解く際、我々の関心はしばしば、ある数が「何で割り切れるか」あるいは「何で割るといくつ余るか」という点に集中します。合同式は、この「余り」の情報だけを抽出し、それを中心とした新しい計算体系を構築するための、エレガントな言語です。この言語を導入することで、数の世界は、無限に広がる直線上のものではなく、有限個の点を巡る「サイクル」として捉え直されます。

1.1. 合同式の定義

【定義】

2つの整数 \(a, b\) と、正の整数 \(m\) がある。

このとき、「\(a-b\) が \(m\) の倍数である」とき、「\(a\) と \(b\) は \(m\) を法として合同である」といい、

\[

a \equiv b \pmod{m}

\]

と書く。

  • \(m\) を法 (modulus) と呼びます。
  • この式は「a is congruent to b modulo m」と読みます。

同値な定義

この定義は、以下の表現と完全に同値です。

「\(a\) を \(m\) で割ったときの余りと、\(b\) を \(m\) で割ったときの余りが等しい。」

証明:

  • (\(\implies\)) a-b = mk (kは整数) と仮定する。a = qm + r (0 \le r < m) とすると、b = a - mk = (qm+r) - mk = (q-k)m + r。よって、bをmで割った余りもrとなり、等しい。
  • (\(\impliedby\)) a = q_1 m + r, b = q_2 m + r と仮定する。a-b = (q_1-q_2)m となり、a-b は m の倍数である。

直感的な理解

a ≡ b (mod m) とは、数の世界を m 個のグループ（剰余類）に分割し、a と b が同じグループに属している、と宣言することです。

例えば、mod 5 の世界では、すべての整数は、5で割った余りによって、以下の5つのグループのいずれかに分類されます。

  • 余り0のグループ: {…, -10, -5, 0, 5, 10, …} → これらを代表して 0 と見なす。
  • 余り1のグループ: {…, -9, -4, 1, 6, 11, …} → これらを代表して 1 と見なす。
  • 余り2のグループ: {…, -8, -3, 2, 7, 12, …} → これらを代表して 2 と見なす。
  • 余り3のグループ: {…, -7, -2, 3, 8, 13, …} → これらを代表して 3 と見なす。
  • 余り4のグループ: {…, -6, -1, 4, 9, 14, …} → これらを代表して 4 と見なす。

この世界では、例えば 13 と 8 は、どちらも「余り3のグループ」に属しているので、「同じ」ものと見なします。これが 13 ≡ 8 (mod 5) の意味です。

1.2. 合同式の基本性質

合同式は、等号 = と非常によく似た性質を持っており、それゆえに代数的な操作がしやすくなっています。これらの性質は、合同という関係が同値関係であることを示しています。

\(a, b, c, d\) を整数、\(m\) を正の整数とします。

1. 反射律 (Reflexive Property)

\[ a \equiv a \pmod{m} \]

証明: a-a=0 は、0 = m \times 0 なので、m の倍数である。

2. 対称律 (Symmetric Property)

\[ a \equiv b \pmod{m} \implies b \equiv a \pmod{m} \]

証明: a ≡ b (mod m) ならば a-b = mk (kは整数)。両辺に-1を掛けると b-a = m(-k) となり、b-a も m の倍数である。

3. 推移律 (Transitive Property)

\[ a \equiv b \pmod{m} \text{ かつ } b \equiv c \pmod{m} \implies a \equiv c \pmod{m} \]

証明: a-b = mk_1, b-c = mk_2 (k1, k2は整数) と書ける。この2式を足し合わせると、

(a-b) + (b-c) = mk_1 + mk_2

a-c = m(k_1+k_2)

となり、a-c も m の倍数である。

これらの3つの性質があるおかげで、我々は合同式を、等式と同じような感覚で（ただし注意点はある）、移項したり、等式をつないだりすることができます。

その他の便利な性質

  • \(a \equiv b \pmod{m} \iff a \pm mk \equiv b \pmod{m}\) (kは整数)法 m の倍数を足したり引いたりしても、合同関係は変わらない。これは、余りが変わらないことを考えれば自明です。この性質を使って、合同式に現れる数を、より小さな（絶対値が小さい）数に置き換えることができます。
    • 例: 177 \equiv 177 - 52 \times 3 \equiv 21 \pmod{52}
    • 例: 4 \equiv 4-5 \equiv -1 \pmod{5} (負の数を使うと計算が楽になることがある)
  • \(a \equiv b \pmod{m}, c \equiv d \pmod{m} \implies a \pm c \equiv b \pm d \pmod{m}\) (加法・減法)
  • \(a \equiv b \pmod{m}, c \equiv d \pmod{m} \implies ac \equiv bd \pmod{m}\) (乗法)
  • \(a \equiv b \pmod{m} \implies a^n \equiv b^n \pmod{m}\) (べき乗)これらの四則演算に関する重要な性質は、次のセクションで詳しく証明し、その使い方を探求します。

合同式は、整数が持つ周期的な構造を浮き彫りにするための、強力なX線写真のようなものです。この新しい記法に慣れ、その背後にある「余りの世界」の感覚を掴むことが、整数論のより深い領域へと進むための、不可欠な第一歩となります。

2. 合同式の四則演算

合同式が強力なツールである理由は、それが単なる関係の記述に留まらず、その中で**計算（代数的操作）**が可能である点にあります。足し算、引き算、掛け算については、等式とほぼ同じ感覚で扱うことができます。しかし、割り算に関しては、整数の世界特有の注意が必要となり、その制約を理解することが、合同式を正しく使いこなすための鍵となります。

2.1. 加法・減法・乗法

これらの演算は、合同式の定義から直接証明できる、非常に直感的で使いやすい性質を持っています。

【定理】

\(a, b, c, d\) を整数、\(m\) を正の整数とする。

\(a \equiv b \pmod{m}\) かつ \(c \equiv d \pmod{m}\) のとき、以下の合同式が成り立つ。

  1. 加法: \(a+c \equiv b+d \pmod{m}\)
  2. 減法: \(a-c \equiv b-d \pmod{m}\)
  3. 乗法: \(ac \equiv bd \pmod{m}\)

証明

  • 仮定: a-b = mk_1, c-d = mk_2 (k1, k2は整数) と書ける。
  • 加法の証明:(a+c) – (b+d) = (a-b) + (c-d) = mk_1 + mk_2 = m(k_1+k_2)よって、(a+c)-(b+d) は m の倍数なので、a+c ≡ b+d (mod m)。
  • 減法の証明:(a-c) – (b-d) = (a-b) – (c-d) = mk_1 – mk_2 = m(k_1-k_2)よって、(a-c)-(b-d) は m の倍数なので、a-c ≡ b-d (mod m)。
  • 乗法の証明:ac – bd を考える。a=b+mk_1, c=d+mk_2 を代入する。ac – bd = (b+mk_1)(d+mk_2) – bd= (bd + bmk_2 + dmk_1 + m^2k_1k_2) – bd= bmk_2 + dmk_1 + m^2k_1k_2= m(bk_2 + dk_1 + mk_1k_2)よって、ac-bd は m の倍数なので、ac ≡ bd (mod m)。

べき乗への拡張

乗法の性質を繰り返し適用することで、べき乗に関する以下の重要な性質が導かれます。

【系】

\(a \equiv b \pmod{m}\) のとき、任意の自然数 \(n\) について、

\[

a^n \equiv b^n \pmod{m}

\]

これらの性質の威力

これらの性質により、合同式の中に現れる数を、計算しやすいように、同じ余りを持つ別の数に自由に置き換えることができます。これが、巨大な数の計算を簡略化する際の基本操作となります。

例: 123 \times 456 を 7 で割った余りを求めよ。

  • 123 = 7 \times 17 + 4 \implies 123 \equiv 4 \pmod{7}
  • 456 = 7 \times 65 + 1 \implies 456 \equiv 1 \pmod{7}
  • 乗法の性質より、123 \times 456 \equiv 4 \times 1 \equiv 4 \pmod{7}
  • よって、余りは 4。

例: \(13^{100}\) を 7 で割った余りを求めよ。

  • まず、底を小さくする。13 = 7 \times 1 + 6 \implies 13 \equiv 6 \pmod{7}また、負の数を使うとさらに便利。13 \equiv 6 \equiv -1 \pmod{7}
  • べき乗の性質より、13^{100} \equiv (-1)^{100} \pmod{7}
  • (-1)^{100} = 1 なので、13^{100} \equiv 1 \pmod{7}
  • よって、余りは 1。

2.2. 割り算の難しさ

加法・減法・乗法が直感的に成り立ったのに対し、割り算はそうはいきません。

例えば、実数の世界では 6x = 10 ならば両辺を2で割って 3x = 5 とできます。

合同式の世界で考えてみましょう。

6 \equiv 10 \pmod{4} (6-10=-4は4の倍数なので、これは正しい)

この両辺を2で割って、3 \equiv 5 \pmod{4} とできるでしょうか？

3-5=-2 は4の倍数ではないので、これは誤りです。

なぜ単純に割れないのか？

ac \equiv bc \pmod{m} は、ac – bc = mk、すなわち (a-b)c = mk を意味します。

この式から、a-b が m の倍数である（つまり a \equiv b \pmod{m}）と結論付けるには、c と m の関係が重要になります。もし c が m と共通の因数を持っていると、その因数が c の側で吸収されてしまい、a-b は m の倍数である必要がなくなってしまうのです。

上記の例 6 \equiv 10 \pmod{4} は 2 \cdot 3 \equiv 2 \cdot 5 \pmod{4} です。

これは (3-5) \cdot 2 = 4k、-4 = 4k を意味し、成り立っています。

しかし、ここから 3-5 が4の倍数であるとは言えません。

2.3. 合同式の正しい割り算

では、合同式の割り算はどのように行えばよいのでしょうか。

【定理】

\(c, m\) の最大公約数を \(d = \text{G.C.D.}(c, m)\) とする。

このとき、

\[

ac \equiv bc \pmod{m} \iff a \equiv b \pmod{\frac{m}{d}}

\]

証明:

ac ≡ bc (mod m)

⇔ (a-b)c が m の倍数

⇔ (a-b)c = mk (kは整数)

c=dc’, m=dm’ (c’とm’は互いに素) を代入。

⇔ (a-b)dc’ = dm’k

⇔ (a-b)c’ = m’k

c’とm’は互いに素なので、a-b が m’ の倍数でなければならない。

⇔ a-b が \(\frac{m}{d}\) の倍数

⇔ a ≡ b (mod m/d)

この定理は、「両辺と法を、共通の因数で一緒に割る」と覚えることができます。

例: 6 \equiv 10 \pmod{4}

a=3, b=5, c=2, m=4

d = G.C.D.(c, m) = G.C.D.(2, 4) = 2

m/d = 4/2 = 2

したがって、3 \equiv 5 \pmod{2} となります。

3-5=-2 は2の倍数なので、これは正しい。

最も重要な特別ケース：法と互いに素な数での割り算

上記の定理で、もし割る数 c と法 m が互いに素であったなら、d = G.C.D.(c,m) = 1 となります。

この場合、定理は以下のようになります。

【系】

\(c\) と \(m\) が互いに素であるとき、

\[

ac \equiv bc \pmod{m} \implies a \equiv b \pmod{m}

\]

が成り立つ。

これは、法と互いに素な数であれば、等式と同じように両辺を割り算（キャンセル）できることを意味します。この性質は、次に学ぶ一次合同方程式を解く上で、極めて重要な役割を果たします。

例: 10k \equiv 20 \pmod{21}

kを求めたい。両辺を10で割りたい。

割る数10と法21は、G.C.D.(10, 21)=1で、互いに素です。

したがって、単純に両辺を10で割ることができます。

k \equiv 2 \pmod{21}

合同式の四則演算、特に割り算のルールを正確にマスターすることは、合同式を自由自在に操るための必須条件です。加法・減法・乗法は直感的に、割り算は「法とのG.C.D.」を意識して、慎重に扱う。この感覚を身につけることで、合同式はあなたの強力な数学的武器となります。

3. 一次合同方程式の解法

合同式の四則演算を学んだことで、我々は合同式で書かれた「方程式」を解く準備が整いました。その最も基本的なものが、一次合同方程式 (Linear Congruence Equation) です。これは、ax ≡ b (mod m) の形で与えられ、この式を満たす整数 x を見つけ出す問題です。この方程式の解法は、一次不定方程式 ax-my=b の解法と本質的に同じであり、両者は互いに翻訳可能な、コインの裏表のような関係にあります。

3.1. 一次合同方程式とは

【定義】

整数 a, b と法 m (正の整数) が与えられたとき、

\[

ax \equiv b \pmod{m}

\]

という形の、未知数 x に関する合同式を一次合同方程式という。

この方程式の解は、mod m の世界で考えます。つまり、x ≡ x_0 (mod m) のように、m を法とする剰余類として解を表現するのが一般的です。

3.2. 解の存在条件

一次不定方程式 ax - my = b が解を持つための条件は、b が G.C.D.(a, -m) = G.C.D.(a, m) の倍数であることでした。一次合同方程式 ax ≡ b (mod m) は、この不定方程式と全く同値なので、解の存在条件も同じになります。

【解の存在条件】

一次合同方程式 ax ≡ b (mod m) が解を持つための必要十分条件は、b が d = G.C.D.(a, m) の倍数であることである。

  • 例: 6x ≡ 4 (mod 10)
    • a=6, m=10 → d = G.C.D.(6, 10) = 2
    • b=4。4は2の倍数なので、この方程式は解を持つ。
  • 例: 6x ≡ 3 (mod 10)
    • d = G.C.D.(6, 10) = 2
    • b=3。3は2の倍数ではないので、この方程式は解を持たない。（6x-3 が10の倍数になることはない、なぜなら 6xは偶数なので6x-3は常に奇数だから）

3.3. 一次合同方程式の解法

解が存在する場合、その解法は大きく分けて、a と m が互いに素な場合と、そうでない場合に分けられます。

ケース1：a と m が互いに素な場合

G.C.D.(a, m) = 1 の場合、解は mod m でただ一つ存在します。

この場合、我々の目標は、x の係数 a を 1 に変えることです。そのためには、a に掛けて 1 (mod m) になる数、すなわち a の**法 m に関する乗法の逆数（モジュラ逆数）**を見つける必要があります。

方法A：試行錯誤

ax – b が m の倍数になる x を、x=1, 2, … と代入して探す。m が小さければ有効。

例: 3x ≡ 4 (mod 5)

  • x=1: 3 ≡ 4 (偽)
  • x=2: 6 ≡ 1 ≡ 4 (偽)
  • x=3: 9 ≡ 4 (真)。よって x=3 は解。
  • 解は x ≡ 3 (mod 5)。

方法B：合同式の変形

合同式の性質を使い、係数を1に近づけていく。

例: 7x ≡ 8 (mod 11)

  • 8 \equiv 8+11 \equiv 19 などは使えない。8 \equiv 8-11 \equiv -37x \equiv -3 \pmod{11}
  • 両辺に数を足したり引いたりして、係数が割り切れるようにする。7x \equiv -3 \equiv -3+11 = 87x \equiv 8 \equiv 8+11 = 197x \equiv -3 \equiv -3+11 \times 2 = 19
  • 賢い変形:7x \equiv 8 \pmod{11}両辺に2を掛けてみる。14x \equiv 16 \pmod{11}14 \equiv 3 (mod 11), 16 \equiv 5 (mod 11)3x \equiv 5 \pmod{11}3x \equiv 5+11 = 16 (割れない)3x \equiv 5+11 \times 2 = 27 (割れる！)3x \equiv 27 \pmod{11}3と11は互いに素なので、両辺を3で割れる。x \equiv 9 \pmod{11}

方法C：拡張ユークリッド互除法（最も体系的）

ax ≡ 1 (mod m) となる x（モジュラ逆数）を、一次不定方程式 ax – my = 1 を解くことで見つけ、それを b 倍する。

例: 7x ≡ 8 (mod 11)

  1. まず 7x' ≡ 1 (mod 11) を解く。これは不定方程式 7x' - 11y' = 1 と同値。
    • 11 = 7 \times 1 + 4
    • 7 = 4 \times 1 + 3
    • 4 = 3 \times 1 + 1
    • 1 = 4 - 3 \times 1
    • = 4 - (7 - 4 \times 1) \times 1 = 2 \cdot 4 - 1 \cdot 7
    • = 2 \cdot (11 – 7 \times 1) – 1 \cdot 7 = 2 \cdot 11 – 3 \cdot 7よって、7(-3) – 11(-2) = 1。x’ = -3 が一つの解。x’ \equiv -3 \equiv 8 \pmod{11}。
  2. したがって、7 の mod 11 での逆数は 8 である。（検算: 7 \times 8 = 56 = 5 \times 11 + 1 \equiv 1）
  3. 元の式 7x ≡ 8 (mod 11) の両辺に、この逆数 8 を掛ける。8 \cdot 7x \equiv 8 \cdot 8 \pmod{11}1 \cdot x \equiv 64 \pmod{11}64 = 5 \times 11 + 9 \implies 64 \equiv 9x \equiv 9 \pmod{11}方法Bの結果と一致します。

ケース2：a と m が互いに素でない場合

d = G.C.D.(a, m) > 1 の場合。

解の存在条件より、b は d の倍数でなければならない。

解法:

方程式 ax ≡ b (mod m) の両辺と法を、すべて d で割る。

\[

\frac{a}{d}x \equiv \frac{b}{d} \pmod{\frac{m}{d}}

\]

この新しい合同式では、係数 a/d と法 m/d は互いに素になる。

したがって、これはケース1の問題に帰着し、mod (m/d) でただ一つの解 x \equiv x_0 (mod m/d) が得られる。

解の個数

x \equiv x_0 (mod m/d) は、x = (m/d)k + x_0 (kは整数) を意味する。

これを mod m の世界で考えると、

k=0, 1, 2, …, d-1 の d 個の値を代入したときに、mod m で異なる解が得られる。

したがって、元の合同式 ax ≡ b (mod m) は、mod m の世界で d 個の解を持つ。

例: 6x ≡ 4 (mod 10)

  1. a=6, b=4, m=10。d = G.C.D.(6,10)=2。b=4 は d=2 の倍数なので解は存在する。
  2. 両辺と法を d=2 で割る。3x \equiv 2 \pmod{5}
  3. この新しい合同式を解く。3x \equiv 2+5=7 (ダメ)3x \equiv 2+5 \times 2 = 12 (OK)3x \equiv 12 \pmod{5}3と5は互いに素なので、3で割れる。x \equiv 4 \pmod{5}
  4. これが解の基本形。x は、5で割ると4余る数。x = 4, 9, 14, …これを mod 10 の世界で考えると、x=4 → 6 \times 4 = 24 \equiv 4 (mod 10) (OK)x=9 → 6 \times 9 = 54 \equiv 4 (mod 10) (OK)x=14 → 6 \times 14 = 84 \equiv 4 (mod 10) (OK)解は x \equiv 4, 9 \pmod{10} の2個 (d=2個)。

一次合同方程式の解法は、一次不定方程式の理論の、より洗練された表現です。法と係数が互いに素であるかどうかに注目し、そうでない場合は公約数で割って帰着させる、という流れをマスターすることが、この分野を攻略する鍵となります。

4. 合同式を用いた余りの問題

合同式の理論が持つ最も直接的で強力な応用の一つが、巨大な数のべき乗など、直接計算するのが困難な数の余りを求める問題です。通常の割り算（除法の原理）では手に負えないような計算も、合同式の性質、特にべき乗に関する性質やフェルマーの小定理などを利用することで、驚くほど簡単かつ機械的に解決することができます。

4.1. 基本戦略：数を小さくする

合同式を用いて余りの問題を解く際の基本戦略は、一貫して「計算する数を、より小さくて扱いやすい数に置き換える」ことです。そのためのテクニックは、主に2つあります。

戦略1：底 (Base) を小さくする

  • 合同式 a^n (mod m) を計算する際に、まず底 a を m で割った余りに置き換えます。
  • a ≡ r (mod m) ならば、a^n ≡ r^n (mod m) が成り立つため、より小さい数 r のべき乗を考えればよくなります。
  • 特に、余りが 1 や -1 になる数を見つけることができると、計算は劇的に単純化されます。

戦略2：指数 (Exponent) を小さくする

  • 底を小さくしても計算がまだ大変な場合、指数 n を小さくすることを考えます。
  • このために用いるのが、フェルマーの小定理や、その一般化であるオイラーの定理です。
    • フェルマーの小定理: p が素数で a が p で割り切れないとき、a^(p-1) ≡ 1 (mod p)。
    • オイラーの定理: a と n が互いに素なとき、a^φ(n) ≡ 1 (mod n)。
  • これらの定理は、指数部分に p-1 や φ(n) という「周期」が存在することを示しています。これを利用して、大きな指数 n を、p-1 や φ(n) で割った余りに置き換えることができます。

4.2. ケーススタディ

例題1：底を小さくするのが有効な場合

2025^2025 を 7 で割った余りを求めよ。

思考プロセス

  1. 底を小さくする:まず、底である 2025 を法 7 で考えます。2025 ÷ 7 を計算する。2025 = 2023 + 2 = (7 \times 289) + 2よって、2025 \equiv 2 \pmod{7}。
  2. 合同式を置き換える:2025^{2025} \equiv 2^{2025} \pmod{7}計算する数が、2025から2へと大幅に小さくなりました。
  3. べき乗の周期性を見つける:次に、2^n (mod 7) の周期を調べます。
    • 2^1 ≡ 2
    • 2^2 ≡ 4
    • 2^3 ≡ 8 ≡ 1
    • 2^4 ≡ 2 \times 2^3 \equiv 2 \times 1 \equiv 22, 4, 1 という周期3の繰り返しになっていることが分かります。特に 2^3 ≡ 1 (mod 7) という関係は非常に便利です。
  4. 指数を小さくする:この周期3を利用して、指数 2025 を小さくします。2025 を周期 3 で割った余りを求めます。2025 = 3 \times 675 なので、余りは0です。2025 \equiv 0 \pmod{3}（各桁の和 2+0+2+5=9 が3の倍数なので、2025は3の倍数）2025 = 3 \times 675したがって、2^{2025} = 2^{3 \times 675} = (2^3)^{675}
  5. 最終計算:(2^3)^{675} \equiv 1^{675} \equiv 1 \pmod{7}

結論: 2025^2025 を 7 で割った余りは 1 です。

別解：フェルマーの小定理の利用

  • 法 7 は素数であり、底 2 は 7 で割り切れないので、フェルマーの小定理が使えます。
  • 2^{7-1} \equiv 2^6 \equiv 1 \pmod{7}
  • 指数 2025 を周期 6 で割った余りを求めます。2025 = 6 \times 337 + 32025 \equiv 3 \pmod{6}
  • したがって、2^{2025} = 2^{6 \times 337 + 3} = (2^6)^{337} \times 2^3\equiv 1^{337} \times 2^3 \equiv 1 \times 8 \equiv 1 \pmod{7}
  • 結果は一致します。

例題2：指数を小さくするのが有効な場合

3^{200} を 101 で割った余りを求めよ。

思考プロセス

  1. 底を小さくする:底は3であり、法101より小さいので、このステップは不要です。
  2. フェルマーの小定理の適用:
    • 法 101 は素数です。（2,3,5,7で割り切れないことを確認）
    • 底 3 は 101 で割り切れない。
    • したがって、フェルマーの小定理が適用できます。p=101, a=33^{101-1} \equiv 3^{100} \equiv 1 \pmod{101}
  3. 指数を分解する:求めたい指数は 200 です。200 = 100 \times 2
  4. 最終計算:3^{200} = 3^{100 \times 2} = (3^{100})^2\equiv 1^2 \equiv 1 \pmod{101}

結論: 3^{200} を 101 で割った余りは 1 です。

この問題では、3^n (mod 101) の周期を手作業で見つけるのはほぼ不可能です。フェルマーの小定理がいかに強力であるかが分かります。

4.3. 複数の合同式の組み合わせ

例題3: 29^{2020} を 15 で割った余りを求めよ。

法 15 は合成数なので、フェルマーの小定理は直接使えません。しかし、15 = 3 \times 5 と互いに素な素数に分解できるので、中国の剰余定理の考え方が応用できます。

思考プロセス

  1. 法を分解して考える:x = 29^{2020} とおく。x を mod 3 と mod 5 でそれぞれ考える。
    • mod 3:29 = 3 \times 9 + 2 \implies 29 \equiv 2 \equiv -1 \pmod{3}x = 29^{2020} \equiv (-1)^{2020} = 1 \pmod{3}
    • mod 5:29 = 5 \times 5 + 4 \implies 29 \equiv 4 \equiv -1 \pmod{5}x = 29^{2020} \equiv (-1)^{2020} = 1 \pmod{5}
  2. 結果を統合する:我々は、x が以下の連立合同式を満たすことを突き止めました。\[\begin{cases}x \equiv 1 \pmod{3} \x \equiv 1 \pmod{5}\end{cases}\]
    • x ≡ 1 (mod 3) は、x-1 が3の倍数であることを意味する。
    • x ≡ 1 (mod 5) は、x-1 が5の倍数であることを意味する。
    • したがって、x-1 は3と5の公倍数、すなわち15の倍数でなければならない。
    • よって、x-1 \equiv 0 \pmod{15}、すなわち x \equiv 1 \pmod{15}。

結論: 29^{2020} を 15 で割った余りは 1 です。

合同式を用いた余りの問題の解法は、これらの基本戦略（底を小さくする、指数を小さくする、法を分解する）を、問題の状況に応じて柔軟に組み合わせることで成り立っています。この思考法は、整数問題における計算の複雑さを劇的に軽減する、強力な武器となります。

5. 曜日の計算

一見すると複雑に見えるカレンダーの計算、特に「N日後の曜日は何か？」あるいは「特定の年月日の曜日は何か？」という問題は、実は合同式の考え方を応用することで、非常に明快に解決することができます。曜日は、7日経つと元に戻るという、完璧な周期性を持っており、これはまさしく7を法とする剰余（mod 7）の世界そのものなのです。

5.1. 曜日と合同式モデル

モデル化

曜日を、0から6までの整数に以下のように対応させます。（どの曜日を0にするかは任意ですが、ここでは日曜日を0とします）

  • 日曜日 (Sunday): 0
  • 月曜日 (Monday): 1
  • 火曜日 (Tuesday): 2
  • 水曜日 (Wednesday): 3
  • 木曜日 (Thursday): 4
  • 金曜日 (Friday): 5
  • 土曜日 (Saturday): 6

このモデルでは、曜日の計算はすべて mod 7 の合同式の計算に帰着します。

  • 例えば、火曜日(2)の3日後は、2+3 = 5 なので金曜日。
  • 金曜日(5)の4日後は、5+4 = 9。9 \equiv 2 (mod 7) なので、火曜日。

N日後の曜日

今日が D という曜日（に対応する数）であるとき、N 日後の曜日は、

\[

(D + N) \pmod{7}

\]

の計算で求めることができます。N が大きい場合でも、先に N を7で割った余りを計算すればよいため、非常に効率的です。

例題1：100日後の曜日

今日が火曜日であるとき、100日後は何曜日か。

  1. モデル化:火曜日は 2 に対応する。
  2. 日数を mod 7 で考える:100 を 7 で割った余りを求める。100 = 7 \times 14 + 2したがって、100 \equiv 2 \pmod{7}。100日後は、2日後と曜日の進み方は同じです。
  3. 計算:求める曜日は、(今日の曜日 + 日数) (mod 7)(2 + 100) \equiv 2 + 2 = 4 \pmod{7}
  4. 結論:数 4 は木曜日に対応する。よって、100日後は木曜日。

5.2. 各月の日数と「余り」

特定の年月日の曜日を計算するためには、各月の日数と、それが mod 7 でいくつになるかを把握しておく必要があります。

  • 31日の月 (1, 3, 5, 7, 8, 10, 12月):31 = 7 \times 4 + 3 \implies 31 \equiv 3 \pmod{7}（31日の月は、4週間と3日。次の月の同じ日は、曜日が3つ進む）
  • 30日の月 (4, 6, 9, 11月):30 = 7 \times 4 + 2 \implies 30 \equiv 2 \pmod{7}（30日の月は、4週間と2日。曜日が2つ進む）
  • 28日の月 (平年の2月):28 = 7 \times 4 + 0 \implies 28 \equiv 0 \pmod{7}（平年の2月はちょうど4週間。曜日はずれない）
  • 29日の月 (閏年の2月):29 = 7 \times 4 + 1 \implies 29 \equiv 1 \pmod{7}（閏年の2月は4週間と1日。曜日が1つ進む）

閏年のルール

  • 西暦年が4で割り切れる年は閏年。
  • ただし、100で割り切れる年は平年。
  • ただし、400で割り切れる年は閏年。(例: 2000年は閏年、1900年は平年、2024年は閏年)

例題2：特定の日付の曜日

2025年8月18日は月曜日です。では、2025年のクリスマス（12月25日）は何曜日でしょうか。

思考プロセス

8月18日から12月25日までの総日数を計算し、その mod 7 を求めます。

  • 8月: 31 - 18 = 13 日
  • 9月: 30 日
  • 10月: 31 日
  • 11月: 30 日
  • 12月: 25 日
  • 総日数: 13 + 30 + 31 + 30 + 25 = 129 日

mod 7 を計算します。

129 = 7 \times 18 + 3

よって、129 \equiv 3 \pmod{7}。

12月25日は、8月18日の3日後の曜日と同じになります。

  • 8月18日: 月曜日 (1)
  • 求める曜日: (1 + 3) \pmod{7} = 4
  • 数 4 は木曜日に対応します。
  • 結論: 2025年のクリスマスは木曜日です。

別解（各月の余りを利用）

  • 8月18日 → 9月18日: 8月は31日なので、31 \equiv 3 (mod 7)。曜日が3つ進む。
  • 9月18日 → 10月18日: 9月は30日なので、30 \equiv 2 (mod 7)。曜日が2つ進む。
  • 10月18日 → 11月18日: 10月は31日なので、31 \equiv 3 (mod 7)。曜日が3つ進む。
  • 11月18日 → 12月18日: 11月は30日なので、30 \equiv 2 (mod 7)。曜日が2つ進む。
  • 8月18日から12月18日までに、曜日は 3+2+3+2 = 10 日分進む。10 \equiv 3 (mod 7)。
  • 12月18日は、8月18日（月曜）の3日後、つまり木曜日。
  • 12月25日は、12月18日の 25-18=7 日後。7日後はちょうど1週間後なので、同じく木曜日。結果は一致します。

5.3. ツェラーの公式（参考）

任意の日付の曜日を直接計算するための、ツェラーの公式 (Zeller’s congruence) という有名な合同式があります。

西暦 Y 年 M 月 D 日の曜日 h（0:日曜, … , 6:土曜）は、

（ただし、1月と2月は、前年の13月、14月として扱う。例: 2025年2月15日は、2024年14月15日とする）

\[

h \equiv \left( Y + \left\lfloor \frac{Y}{4} \right\rfloor – \left\lfloor \frac{Y}{100} \right\rfloor + \left\lfloor \frac{Y}{400} \right\rfloor + \left\lfloor \frac{13(M+1)}{5} \right\rfloor + D \right) \pmod{7}

\]

（ここで \(\lfloor x \rfloor\) は、x を超えない最大の整数を表す床関数）

この公式は複雑に見えますが、各項は

  • Y: 経過年数による曜日のずれ（1年で1日）
  • ⌊Y/4⌋ - ⌊Y/100⌋ + ⌊Y/400⌋: 閏年による補正
  • ⌊13(M+1)/5⌋: 各月の日数のずれを巧妙に計算する項
  • D: 日によるずれをそれぞれ表しており、合同式の強力な応用例となっています。

曜日の計算は、合同式という数学的ツールが、いかに我々の日常的な周期性を持つ問題に、明快な構造と解法を与えてくれるかを示す、絶好の例と言えるでしょう。

6. 繰り返し模様と合同式

合同式の本質は、「周期性」を扱う数学である、と言えます。法 m を定めると、整数は 0, 1, 2, ..., m-1 という m 個の状態を周期的に繰り返すものとして扱われます。この考え方は、曜日のような時間的な周期だけでなく、空間的な繰り返し模様や、数列に現れる規則的なパターンの繰り返しを分析する際にも、非常に強力なツールとなります。

6.1. 数列の周期性：一の位の数字

整数のべき乗を計算していくと、その一の位の数字は、しばしば周期的に同じパターンを繰り返します。これは、一の位の数字が10で割った余り、すなわち mod 10 の合同式で決まるからです。

例題1：\(3^n\) の一の位

自然数 n に対する 3^n の一の位の数字の列を考える。

  • n=1: 3^1 = 3 → 一の位は 3
  • n=2: 3^2 = 9 → 一の位は 9
  • n=3: 3^3 = 27 → 一の位は 7
  • n=4: 3^4 = 81 → 一の位は 1
  • n=5: 3^5 = 243 → 一の位は 3
  • n=6: 3^6 = 729 → 一の位は 9

一の位の数字は、3, 9, 7, 1 という周期4のパターンを繰り返していることが分かります。

これを合同式で見てみましょう。

  • 3^1 ≡ 3 (mod 10)
  • 3^2 ≡ 9 (mod 10)
  • 3^3 ≡ 27 ≡ 7 (mod 10)
  • 3^4 ≡ 3 \times 3^3 \equiv 3 \times 7 = 21 \equiv 1 (mod 10)
  • 3^5 = 3 \times 3^4 \equiv 3 \times 1 = 3 (mod 10)1 が現れた時点で、次のべき乗は最初の 3 に戻り、サイクルが確定します。

応用：\(3^{2025}\) の一の位は？

この問題は、「周期4のパターンの、2025番目は何か？」という問いと同じです。

これは、指数 2025 を、周期である 4 で割った余りを調べれば分かります。

2025 = 4 \times 506 + 1

2025 \equiv 1 \pmod{4}

したがって、3^{2025} の一の位は、周期の1番目の数字と同じになります。

答え：3

一般化

ある数 a^n の一の位の周期を知るには、a^k ≡ 1 (mod 10) となる最小の k を見つけるか、あるいは a, a^2, a^3, … を mod 10 で計算し、同じ数が現れるまでの周期を見つければよい。

6.2. 空間的な繰り返し模様

合同式の考え方は、空間的に配置されたオブジェクトのパターン分析にも応用できます。

例題2：タイルの色

赤、青、黄、緑、紫の5色のタイルを、この順番で横一列に繰り返し並べていく。

[赤|青|黄|緑|紫|赤|青|黄|…]

左から数えて200番目のタイルの色は何色か。

思考プロセス

  1. モデル化:これは、周期5の繰り返し模様です。色を、0から4までの整数に対応させます。
    • 赤: 0
    • 青: 1
    • 黄: 2
    • 緑: 3
    • 紫: 4k 番目のタイルの色は、(k-1) mod 5 で計算できます。（1番目を0とするため）
  2. 合同式の計算:200番目のタイルの色を求めたい。200-1 = 199199 を 5 で割った余りを求めます。199 = 5 \times 39 + 4199 \equiv 4 \pmod{5}
  3. 結論:数 4 は紫色に対応します。よって、200番目のタイルは紫色です。

別解:

200 を直接5で割ると、200 = 5 \times 40 + 0。余りは0です。

周期の最後に来るものが答えなので、紫…としたいところですが、mod の計算では、0 は最初の要素に対応させることが多いので、注意が必要です。k mod 5 で、余りが 1, 2, 3, 4, 0 となるように対応させると、

  • 1 mod 5 = 1 → 青
  • 5 mod 5 = 0 → 紫となり、200 mod 5 = 0 なので、紫色と正しく求められます。どちらのモデルを使うか、最初に決めておくことが重要です。

6.3. 二次元への拡張

例題3：市松模様の碁石

碁盤の目のような格子状の点に、白と黒の碁石を交互に置いていく（市松模様）。

左下の隅の点の座標を (1, 1) とし、ここに黒石を置く。

x 座標と y 座標がともに奇数、またはともに偶数である点 (x, y) には黒石を、片方が奇数で片方が偶数である点には白石を置く。

点 (57, 88) に置かれる石の色は何か。

思考プロセス

  1. モデル化:石の色は、座標 x, y の偶奇性によって決まります。偶奇性は、mod 2 の合同式で完全に記述できます。
    • x が奇数 ⇔ x ≡ 1 (mod 2)
    • x が偶数 ⇔ x ≡ 0 (mod 2)
    • y が奇数 ⇔ y ≡ 1 (mod 2)
    • y が偶数 ⇔ y ≡ 0 (mod 2)黒石が置かれる条件は、
    • (x, y) = (奇, 奇) → x≡1, y≡1 → x+y ≡ 1+1 = 2 ≡ 0 (mod 2)
    • (x, y) = (偶, 偶) → x≡0, y≡0 → x+y ≡ 0+0 = 0 (mod 2)白石が置かれる条件は、
    • (x, y) = (奇, 偶) → x≡1, y≡0 → x+y ≡ 1+0 = 1 (mod 2)
    • (x, y) = (偶, 奇) → x≡0, y≡1 → x+y ≡ 0+1 = 1 (mod 2)したがって、石の色は、座標の和の偶奇性 (x+y) mod 2 で決定できることが分かります。
    • x+y が偶数 ⇔ (x+y) ≡ 0 (mod 2) → 黒石
    • x+y が奇数 ⇔ (x+y) ≡ 1 (mod 2) → 白石
  2. 合同式の計算:点 (57, 88) について、x+y の偶奇性を調べます。57 + 88 = 145145は奇数です。合同式で書けば、57 \equiv 1 (mod 2), 88 \equiv 0 (mod 2)57+88 \equiv 1+0 = 1 \pmod{2}
  3. 結論:x+y が奇数なので、置かれる石は白石です。

合同式は、このように、時間的・空間的に繰り返されるパターンや構造を、その周期（法）に着目して分析するための、非常に普遍的で強力な数学的言語なのです。

8. ウィルソンの定理

素数が持つ性質を記述する定理は数多くありますが、その中でもウィルソンの定理 (Wilson’s Theorem) は、ある数が素数であるための必要十分条件を、階乗 (!) という意外な形で与える、非常にユニークで美しい定理です。この定理は、実用的な素数判定法としては計算量が多すぎて使えませんが、その理論的な美しさと、証明の巧妙さから、整数論における宝石の一つとされています。

8.1. ウィルソンの定理の主張

【定理】

\(p\) を2以上の整数とする。

このとき、\(p\) が素数であるための必要十分条件は、

\[

(p-1)! \equiv -1 \pmod{p}

\]

が成り立つことである。

定理の解釈

この定理は、二つの方向の主張を含んでいます。

  1. (\(\implies\)) もし p が素数ならば、(p-1)! を p で割った余りは、必ず p-1 (すなわち -1) になる。
  2. (\(\impliedby\)) もし (p-1)! ≡ -1 (mod p) が成り立つならば、p は必ず素数である。

具体例

  • p=2 (素数): (2-1)! = 1! = 1。1 ≡ -1 (mod 2)。成り立つ。
  • p=3 (素数): (3-1)! = 2! = 2。2 ≡ -1 (mod 3)。成り立つ。
  • p=4 (合成数): (4-1)! = 3! = 6。6 \equiv 2 (mod 4)。-1 (mod 4) ではないので、成り立たない。
  • p=5 (素数): (5-1)! = 4! = 24。24 = 5 \times 4 + 4 なので 24 \equiv 4 \equiv -1 (mod 5)。成り立つ。
  • p=6 (合成数): (6-1)! = 5! = 120。120 は 6 の倍数なので 120 \equiv 0 (mod 6)。-1 (mod 6) ではないので、成り立たない。

8.2. ウィルソンの定理の証明

この定理の証明は、素数を法とする合同式の世界における「乗法の逆元」という概念が鍵となります。

証明（pが素数 \(\implies\) (p-1)! ≡ -1 (mod p)）

  1. 準備:p は素数であると仮定する。mod p の世界で、0 を除く剰余類の集合 S = {1, 2, 3, …, p-1} を考える。我々が証明したいのは、この集合のすべての元の積が -1 と合同になることである。1 \cdot 2 \cdot 3 \cdots (p-1) \equiv -1 \pmod{p}
  2. 乗法の逆元のペア:p は素数なので、集合 S の各元 a に対して、ax ≡ 1 (mod p) を満たす x (乗法の逆元) が、S の中にただ一つ存在することが知られている。
    • 例: p=7 の場合
      • 1 \cdot 1 ≡ 1
      • 2 \cdot 4 = 8 ≡ 1
      • 3 \cdot 5 = 15 ≡ 1
      • 6 \cdot 6 = 36 ≡ 1ペアは (2,4) と (3,5)。1 と 6 は自分自身がペア。
  3. 自分自身が逆元となる数（自己逆元）:一般に、a \cdot a \equiv 1 (mod p)、すなわち a^2 – 1 \equiv 0 (mod p) となる a を探す。(a-1)(a+1) \equiv 0 \pmod{p}p は素数なので、p | (a-1) または p | (a+1)。a は 1 から p-1 までの数なので、
    • a-1 = 0 \implies a=1
    • a+1 = p \implies a=p-1したがって、mod p の世界で、自分自身が逆元となるのは 1 と p-1 (\(\equiv -1\)) の2つだけである。
  4. ペアで積を考える:集合 S = {1, 2, …, p-1} の元を考える。
    • 1 と p-1 以外の元は、すべて、積が 1 (mod p) となるような、自分とは異なる相手とペアを作ることができる。
    • (p-1)! = 1 \cdot (p-1) \cdot (\text{残りのすべての元の積})
    • 「残りのすべての元」は、積が1になるようなペアの集まりである。(2 \cdot 4) \cdot (3 \cdot 5) \cdots \equiv 1 \cdot 1 \cdots \equiv 1 \pmod{p}
    • したがって、(p-1)! \equiv 1 \cdot (p-1) \cdot 1 \pmod{p}\equiv p-1 \pmod{p}\equiv -1 \pmod{p}

（証明終）

証明（(p-1)! ≡ -1 (mod p) \(\implies\) pが素数）

これは背理法で証明する。

  1. 仮定:p が素数ではない（つまり、合成数である）と仮定する。(p-1)! ≡ -1 (mod p) は成り立っているとする。
  2. 合成数の性質:p は合成数なので、p=ab となるような、1 < a, b < p を満たす整数 a, b が存在する。
  3. 矛盾の導出:
    • a は 1 < a < p なので、a は {1, 2, ..., p-1} という数のリストの中に含まれている。
    • したがって、a は (p-1)! の因数である。a | (p-1)!
    • 一方、仮定より (p-1)! ≡ -1 (mod p) なので、(p-1)! + 1 = pk (kは整数)。
    • a は p の約数なので、a は pk を割り切る。
    • したがって、a は (p-1)!+1 を割り切る。
    • これまでの結果をまとめると、
      • a | (p-1)!
      • a | ((p-1)! + 1)
    • もし、ある整数 a が、2つの数 X と X+1 を両方割り切るならば、a はその差 (X+1)-X=1 も割り切らなければならない。
    • したがって、a | 1。これは a=1 を意味する。
    • しかし、これは 1 < a という、a が p の約数であるという前提に矛盾する。
  4. 例外ケース:もし p=4 の場合、p=ab で a=b=2 となる。この場合は少し議論が異なるが、(4-1)! = 6 \equiv 2 (mod 4) なので、やはり成り立たない。
  5. 結論:矛盾が生じたので、最初の仮定「pが合成数である」が誤りである。したがって、p は素数でなければならない。

（証明終）

ウィルソンの定理は、階乗という非常に単純な操作が、素数という数の世界の根源的な性質と深く結びついていることを示す、驚くべき結果です。その証明は、合同式の乗法逆元という代数的な構造を巧みに利用しており、初等整数論の美しさと奥深さを凝縮した一例と言えるでしょう。

9. 合同式の応用（暗号理論への導入）

これまで学んできた合同式や整数論の定理は、一見すると純粋数学の抽象的なパズルに見えるかもしれません。しかし、フェルマーの小定理やオイラーの定理といった概念は、現代の情報化社会を根底から支える暗号技術、特に公開鍵暗号 (Public-key Cryptography) の理論的基盤として、極めて重要な役割を果たしています。このセクションでは、その代表例であるRSA暗号の仕組みを簡略化して紹介し、整数論がいかにして我々のデジタル通信の安全性を守っているのか、その一端に触れます。

9.1. 暗号の基本：鍵の受け渡し問題

伝統的な暗号（共通鍵暗号）では、送信者と受信者が、同じ「鍵」を使ってメッセージの暗号化と復号（解読）を行います。

  • 送信者：平文 → (鍵を使って暗号化) → 暗号文
  • 受信者：暗号文 → (同じ鍵を使って復号) → 平文

この方式の最大の問題点は、「どのようにして、安全に鍵を受け渡すか」という点にあります。もし、鍵を配送する途中で第三者に盗まれれば、その後の通信はすべて解読されてしまいます。

9.2. 公開鍵暗号の革命的なアイデア

1970年代に登場した公開鍵暗号は、この鍵配送問題を、驚くべきアイデアで解決しました。

それは、「暗号化に使う鍵」と「復号に使う鍵」を、別のものにするという発想です。

  • 公開鍵 (Public Key): 暗号化に使うための鍵。この鍵は、その名の通り、誰にでも見えるように公開しておきます。世界中の誰でも、この公開鍵を使えば、特定の受信者（鍵の所有者）宛てのメッセージを暗号化できます。
  • 秘密鍵 (Private Key): 復号に使うための鍵。この鍵は、受信者本人だけが厳重に秘密にしておきます。

このシステムが機能するためには、公開鍵と秘密鍵の間に、ある特殊な数学的関係が必要です。

「公開鍵を使って暗号化された暗号文は、対応する秘密鍵を使わなければ、事実上復号することができない」

この関係性を、整数論、特に合同式と素因数分解の困難性を利用して実現したのが、RSA暗号です。

9.3. RSA暗号の仕組み（簡略版）

RSA暗号は、その発明者であるリベスト (Rivest)、シャミア (Shamir)、アドルマン (Adleman) の3人の頭文字をとって名付けられました。そのアルゴリズムの骨子は、以下の通りです。

ステップ1：鍵の生成（受信者が行う）

  1. 非常に大きな2つの素数 p と q を（秘密裏に）選びます。（例: p=61, q=53）
  2. n = p \times q を計算し、この n を公開します。（例: n = 61 \times 53 = 3233）
  3. オイラーのφ関数 φ(n) = (p-1)(q-1) を（秘密裏に）計算します。（例: φ(3233) = (60)(52) = 3120）
  4. φ(n) と互いに素な、適当な整数 e を選び、この e を公開します。e は公開鍵の一部となります。（例: e=17 を選ぶ。G.C.D.(17, 3120)=1）
  5. ed \equiv 1 \pmod{φ(n)} となる整数 d を（秘密裏に）計算します。d は秘密鍵となります。これは、一次合同式 17d \equiv 1 (mod 3120) を解く問題であり、拡張ユークリッド互除法で解くことができます。（例: d=2753 となる）

まとめ

  • 公開鍵: (n, e) = (3233, 17)
  • 秘密鍵: d = 2753
  • （p, q, φ(n) は計算後、安全に破棄する）

ステップ2：暗号化（送信者が行う）

送信者は、受信者の公開鍵 (n, e) を使って、平文のメッセージ M（数値に変換しておく）を暗号化します。

\[

C \equiv M^e \pmod{n}

\]

C が暗号文です。

  • 例: メッセージ M=65 を暗号化する。C \equiv 65^{17} \pmod{3233}（この計算には高速なべき乗剰余アルゴリズムが使われる）計算すると、C = 2790 となります。

ステップ3：復号（受信者が行う）

受信者は、受け取った暗号文 C を、自分の秘密鍵 d を使って復号します。

\[

M \equiv C^d \pmod{n}

\]

  • 例: 暗号文 C=2790 を復号する。M \equiv 2790^{2753} \pmod{3233}これを計算すると、元のメッセージ M=65 が復元されます。

9.4. なぜ復号できるのか？オイラーの定理の威力

この暗号が正しく機能する、すなわち (M^e)^d \equiv M (mod n) となる理由は、まさしくオイラーの定理にあります。

証明のスケッチ

  • 我々が示したいのは C^d \equiv M \pmod n。
  • C^d = (M^e)^d = M^{ed}
  • 鍵生成のステップで、ed \equiv 1 \pmod{φ(n)} となるように d を選びました。
  • これは、ed = k \cdot φ(n) + 1 となる整数 k が存在することを意味します。
  • したがって、M^{ed} = M^{k \cdot φ(n) + 1} = (M^{φ(n)})^k \cdot M^1
  • ここで、もし M と n が互いに素ならば、オイラーの定理より M^{φ(n)} \equiv 1 \pmod n。
  • よって、(M^{φ(n)})^k \cdot M \equiv 1^k \cdot M \equiv M \pmod n
  • （M と n が互いに素でない場合も、中国の剰余定理などを用いて、この式が成り立つことが証明できます）

RSA暗号の安全性

  • 第三者は、公開鍵 (n, e) と暗号文 C を知っています。
  • メッセージ M を復号するには、秘密鍵 d を知る必要があります。
  • d を計算するには、ed \equiv 1 \pmod{φ(n)} という関係から、φ(n) = (p-1)(q-1) を知る必要があります。
  • φ(n) を知るには、n を素因数分解して p と q を見つけ出す必要があります。
  • したがって、RSA暗号の安全性は、「巨大な合成数 n を素因数分解することは、計算機を使っても事実上不可能である」という、計算量的困難性の問題に根差しています。

このように、何世紀にもわたって純粋数学の対象であった整数論の定理が、現代のデジタル社会の安全性を保証するための、不可欠な礎となっているのです。合同式を学ぶことは、単に数学の知識を深めるだけでなく、我々が生きる世界の技術的な基盤を理解することにも繋がっています。

10. 合同式を用いた整数問題の解法

合同式は、それ自体が方程式として解かれたり、巨大な数の余りを計算したりするだけでなく、より広範な整数問題を解くための、非常に強力で汎用的な思考のツールとして機能します。多くの整数問題は、整数の「割り切れる」「割り切れない」という性質、すなわち可除性 (Divisibility) に帰着します。合同式は、この可除性の問題を、代数的な計算が可能な「等式」のような形で扱うことを可能にする、洗練された言語です。

このセクションでは、整数問題を解く際に、合同式をどのように戦略的に利用するか、その思考パターンを整理します。

10.1. 戦略1：解の候補を絞り込む（必要条件によるフィルタリング）

ある方程式の整数解を求める問題において、解の候補は無限に存在するように見えるかもしれません。しかし、その方程式を適当な法 m で考えることで、解が満たすべき「必要条件」を導き出し、候補を劇的に絞り込む、あるいは解が存在しないことを示すことができます。

思考プロセス

  1. 与えられた整数に関する方程式を眺める。
  2. 式中の係数や、べき乗の底などから、考察するのに都合の良い法 m を選択する。
    • 3x + 5y = ... → mod 3 や mod 5 で考えると、項が消えて式が簡単になる。
    • x^2 + y^2 = z^2 → mod 3, mod 4, mod 5 など、平方剰余が特徴的な法が有効。
    • 2^n - 1 = ... → mod 3 などが有効な場合がある。
  3. 方程式の両辺を mod m で考える。
  4. これにより、未知数が満たすべき mod m での条件（余りの条件）を導き出す。
  5. もし、この条件を満たす整数が存在しない場合（例えば、x^2 ≡ 2 (mod 3) のような形）、元の整数方程式には解が存在しないと結論できる。

例題1：解の不存在証明

不定方程式 x^2 – 5y = 3 を満たす整数解 (x, y) は存在しないことを示せ。

思考プロセス

  • 係数に 5 があるので、法を5として考えるのが自然である。
  • 与えられた方程式 x^2 – 5y = 3 の両辺を mod 5 で考える。x^2 – 5y \equiv 3 \pmod{5}
  • 5y \equiv 0 \pmod{5} なので、x^2 \equiv 3 \pmod{5}
  • これは、もし整数解 (x, y) が存在するならば、その x は「2乗して5で割ると3余る」という必要条件を満たさなければならないことを意味する。
  • では、そのような整数 x は存在するだろうか？すべての整数 x は、mod 5 で 0, 1, 2, 3, 4 のいずれかと合同である。これらの2乗を調べてみる。
    • x \equiv 0 \implies x^2 \equiv 0 \pmod{5}
    • x \equiv 1 \implies x^2 \equiv 1 \pmod{5}
    • x \equiv 2 \implies x^2 \equiv 4 \pmod{5}
    • x \equiv 3 \implies x^2 \equiv 9 \equiv 4 \pmod{5}
    • x \equiv 4 \implies x^2 \equiv 16 \equiv 1 \pmod{5}
  • したがって、整数の2乗を5で割った余り（平方剰余）は、0, 1, 4 のいずれかしかあり得ない。
  • 余りが 3 になることは、決してない。
  • よって、x^2 \equiv 3 (mod 5) を満たす整数 x は存在しない。
  • 結論: 必要条件が満たされないので、元の不定方程式 x^2 - 5y = 3 には整数解が存在しない。

10.2. 戦略2：場合分けの簡略化（剰余類による分類）

「すべての整数 n について〜が成り立つことを示せ」といった証明問題では、n を m で割った余りによって場合分けする（剰余類による分類）ことが、非常に有効な戦略となります。

例題2：倍数であることの証明

すべての整数 n について、n^3 + 2n は 3 の倍数であることを証明せよ。

思考プロセス

  • 「3の倍数であること」を証明したいので、法を3として考えるのが自然である。
  • 目標は n^3 + 2n \equiv 0 \pmod{3} を示すこと。
  • すべての整数 n は、mod 3 で 0, 1, 2 のいずれかと合同である。この3つのケースについて、それぞれ証明すれば、すべての整数について証明したことになる。
  • 場合1: n \equiv 0 \pmod{3} のときn^3 + 2n \equiv 0^3 + 2(0) = 0 \pmod{3}（成り立つ）
  • 場合2: n \equiv 1 \pmod{3} のときn^3 + 2n \equiv 1^3 + 2(1) = 1 + 2 = 3 \equiv 0 \pmod{3}（成り立つ）別解（フェルマーの小定理）: nは3で割り切れないので n^2 \equiv 1 (mod 3) …これは使えない。n^3 \equiv n (mod 3) は使える。n^3 + 2n \equiv n + 2n = 3n \equiv 0 (mod 3)。
  • 場合3: n \equiv 2 \pmod{3} のときn \equiv -1 \pmod{3} と考えると計算が楽。n^3 + 2n \equiv (-1)^3 + 2(-1) = -1 – 2 = -3 \equiv 0 \pmod{3}（成り立つ）
  • 結論:いずれの場合においても、n^3 + 2n は mod 3 で 0 と合同になる。したがって、すべての整数 n に対して、n^3 + 2n は 3 の倍数である。

この方法は、数学的帰納法よりも直接的で、計算が簡単な場合が多い。

10.3. 戦略的アプローチのまとめ

整数問題に合同式を応用する際の思考の流れは、以下のようになります。

  1. 問題の翻訳: 問題文の条件（「〜の倍数」「余りが〜」「〜で割り切れない」など）を、合同式の言葉で書き直す。
  2. 法の選択: 問題の構造を最も単純化するような、適切な「法 m」を選択する。これは問題解決の鍵を握る、最も戦略的な部分。
  3. 計算の実行: 合同式の性質（四則演算、フェルマーの小定理など）を用いて、式を簡略化し、計算を進める。
  4. 結論の再翻訳: 得られた合同式の結果を、元の問題の言葉（「〜は〜の倍数である」など）で解釈し直し、結論とする。

合同式は、整数問題を解くための「万能薬」ではありませんが、問題の構造を見通し良くし、複雑な論理を整理し、計算を単純化するための、他に代えがたい強力な「解析ツール」です。このツールを使いこなすことで、これまで手探りで進むしかなかった整数の森に、確かな道筋を見出すことができるようになるでしょう。

Module 10：整数の性質(3) 合同式の総括：剰余の世界から見る数の構造

本モジュールを通じて、我々はカール・フリードリヒ・ガウスによって体系化された、整数論における最も強力な言語の一つ、「合同式」を学びました。その核心は、数をそのものではなく、「法 m で割った余り」という情報に注目し、同じ余りを持つ無限の整数を一つの「仲間（剰余類）」と見なす、という画期的な視点の転換にありました。

この新しい視点から数の世界を眺めると、無限に続く整数の列は、m 個の点を巡る有限のサイクルへと姿を変え、その中で成り立つ新しい算術の法則が明らかになりました。加法、減法、乗法は、驚くほど自然に等式から引き継がれましたが、割り算には「法と互いに素」という整数論特有の制約が伴うこと、そしてその制約こそが合同式の世界の豊かさを生み出していることを見ました。

我々はこの新しい言語を用いて、ax ≡ b (mod m) という一次合同方程式を解き、それが一次不定方程式と表裏一体の関係にあることを確認しました。そして、合同式の真価は、巨大な数の余りを計算する際に発揮されました。底を小さくし、指数を小さくする（フェルマーの小定理、オイラーの定理）という戦略は、計算不可能な問題を、手計算可能な領域へと引き寄せる魔法のようでした。さらに、ウィルソンの定理は、階乗と素数性が (p-1)! ≡ -1 という一つの合同式で結びつく、理論の美しさの極致を示してくれました。

曜日の計算や繰り返す模様の分析は、合同式が我々の日常に潜む周期性をいかに的確に捉えるかを示し、暗号理論への導入は、この純粋数学の理論が、現代社会の安全性を根底から支える、実践的な力となっていることを明らかにしました。

最終的に我々が習得したのは、合同式を、整数問題の「解の存在を判定するフィルター」として、あるいは「証明のケースを限定する分類ツール」として、戦略的に使いこなす思考法です。合同式は、単なる記法や計算テクニックではありません。それは、整数の構造を「剰余」というレンズを通して見つめ、その本質を浮き彫りにするための、強力な認識のフレームワークなのです。このフレームワークを手に、皆様は整数論のさらに広大な世界へと、自信を持って歩みを進めることができるでしょう。

基礎数学 基礎 数学A
目次