合同とモジュラー算術

モジュラー算術は、固定された法による可除性に関して整数を研究し、整数を有限環 Z/nZ に変換することで、数論に最も柔軟な計算ツールを提供します。

Definition

2つの整数が法 n に関して合同であるとは、それらの差が n で割り切れることを指します。モジュラー算術は、結果として生じる剰余類の算術であり、これらは可換環 Z/nZ を形成します。

Scope

このトピックでは、合同関係と剰余類、Z/nZ における算術、線形および多項式の合同、中国剰余定理、フェルマーの小定理とオイラーの定理、単数群の構造、原始根、および元の位数について扱います。これは、初等数論および計算数論のほとんどが表現される言語です。

Core questions

• 線形合同式 ax ≡ b (mod n) はいつ解を持ち、いくつ解を持つのか？
• 中国剰余定理はどのように Z/nZ を素数べき乗の法に関する積に分解するのか？
• フェルマーの小定理とオイラーの定理はなぜ成り立つのか、そしてそれらは単数の位数について何を述べているのか？
• どの法に対して原始根が存在し、単数群を巡回群にするのか？

Key theories

中国剰余定理

法が互いに素である場合、連立合同式系は積を法として一意の解を持ちます。これは、Z/nZ がその素数べき乗因子に関する Z の積と同型であることと同等です。

フェルマーの小定理とオイラーの定理

n と互いに素な a について、a の n のトーシェント関数乗は n を法として 1 に合同です。素数の場合（フェルマー）は素数判定の基礎となり、一般の場合（オイラー）は RSA の基礎となります。

原始根と群構造

法 n に関する乗法群は、n が 1、2、4、奇素数のべき乗、またはその2倍である場合に限り巡回群となります。生成元は原始根であり、離散対数を与えます。

Clinical relevance

モジュラー算術は、暗号（RSA、Diffie-Hellman、楕円曲線スキーム）、チェックサムと誤り検出（ISBN、ハッシュ関数）、および擬似乱数生成の計算エンジンであり、数論の中で最も広く展開されている部分となっています。

History

古代中国およびインドの数学（前者にちなんで名付けられた剰余問題）には特殊なケースが見られますが、合同の体系的な理論はガウスが『Disquisitiones Arithmeticae』（1801年）で導入しました。彼はそこで記法を確立し、中心的な構造的結果を証明しました。

Key figures

• Carl Friedrich Gauss
• Pierre de Fermat
• Leonhard Euler

Seminal works

• irelandRosen1990

Frequently asked questions

記法 a ≡ b (mod n) は何を意味しますか？

これは、n が差 a - b を割り切ることを意味し、同等に a と b を n で割ったときに同じ剰余を残すことを意味します。

RSA はなぜオイラーの定理に依存するのですか？

RSA の暗号化と復号はモジュラーべき乗であり、その合成が元のメッセージを返すのは、オイラーの定理が関連する指数が鍵を法として恒等元として作用することを保証するためです。