モジュラー算術

モジュラー算術は数論に深く根ざした概念であり、暗号学、コンピュータサイエンス、さらには日常生活のさまざまな分野で使用されています。初等的な言葉で言えば、モジュラー算術は整数の除算から得られる余りを扱います。これはある値に達したときに数が循環する世界、すなわちモジュラスとして知られる値を導入します。

概念の理解

モジュラー算術を理解するためには、時計を想像してください。時計には1から12までの12の数字があり、12に達すると再び回り始めます。10時に5時間を加えると、15時ではなく3時になります。これは15を12で割った余りが3であるからです。そのため、モジュラスが12である場合、時計はモジュラー算術における加算の完璧な例です。

 10 + 5 = 15
15 % 12 = 3

モジュラー算術では、a ≡ b (mod m)という表記がよく使われ、「aはmをモジュラスに持つbと等価である」と読みます。これは、aをmで割ったとき、余りがbであることを意味します。

基本原則

モジュラー算術の基本的なルールや特性を学びましょう。これらのルールは、モジュラスを操作するために重要であり、複雑な計算を簡単にします。

合同

モジュラー算術の鍵となる概念は、合同です。二つの整数aとbがmを基として合同である場合、それらはmで割ったときに同じ余りを持っています。数学的には次のようになります:

 a ≡ b (mod m) の条件は (a - b) が m で割り切れることです

例: 38が14と合同であるかどうかを確認するには、次の計算を行います:

 38 % 12 = 2
14 % 12 = 2

どちらも余りが2であるため、38 ≡ 14 (mod 12) であると結論付けます。

加算と減算

モジュラスの下では、通常の算術と同様に加算と減算を行うことができます。また、結果が「巻き戻される」ことがあるという概念が残ります。

 (a + b) % m = [(a % m) + (b % m)] % m
(a - b) % m = [(a % m) - (b % m)] % m

例: (7 + 6) mod 5を計算します。

 7 % 5 = 2
6 % 5 = 1
(7 + 6) % 5 = (2 + 1) % 5 = 3

減算も同様の原理に基づきます。(15 - 8) mod 4 を計算してみましょう。

 15 % 4 = 3
8 % 4 = 0
(15 – 8) % 4 = (3 – 0) % 4 = 3

乗算と除算

乗算

加算や減算と同様に、モジュラー算術では乗算も同じルールに従います。数を乗算し、その後モジュラスを取ります:

 (a * b) % m = [(a % m) * (b % m)] % m

例: (10 * 3) mod 7を計算します。

 10 % 7 = 3
3 % 7 = 3
(10 * 3) % 7 = (3 * 3) % 7 = 9 % 7 = 2

除算

モジュラー算術における除算は複雑で、直接的な除算は一般に定義されません。代わりに、モジュラー逆元の概念を使用します。aモジュラスmの逆元は、次の式を満たすbという数です:

 (a * b) % m = 1

この逆元が存在する場合、aで割ることは逆元を掛けることと等価です。

例: 3の逆元を7を基として求めるには、次のように計算します。3 * b ≡ 1 (mod 7)。値を試しに計算すると:

 3 * 5 = 15
15 % 7 = 1

したがって、5は3に関する7の逆元です。

視覚的表現

モジュラー算術をより理解しやすくするために、数直線とモジュラスを使って視覚的に表現してみましょう:

上記の数直線をモジュラー算術の数値と見立ててみます（ここでは0、1、2などのモジュラスを考えています）。これらの数は、例えば12 ≡ 0 (mod 12)、13 ≡ 1 (mod 12)などのように、モジュラスに応じてパターンが繰り返されます。