モジュラー算術

数学において、モジュラー算術は整数の算術演算体系であり、数値が特定の値（法と呼ばれる）に達したり超えたりすると「一周する」という点で通常の演算体系とは異なります。モジュラー算術を用いた現代の数論のアプローチは、カール・フリードリヒ・ガウスが1801年に出版した著書『算術研究』の中で開発しました。 ^{[ 1 ]}

mを法とするモジュラー演算は、加算、乗算、減算の結果を、 mによる除算の余りで体系的に置き換えることから成ります。モジュラー演算の注目すべき特性は、 mによる除算が各演算の後に行われるか、計算の最後に一度だけ行われるか、あるいは計算の最後にいくつかの中間結果の後に行われるか（通常は中間結果が大きくなりすぎた場合）によって、計算結果が変わらないことです。

モジュラー算術を示す身近な例として、12時間時計の時針が挙げられます。時針が現在7を指している場合、8時間後には3を指します。通常の足し算では7 + 8 = 15となりますが、時計の文字盤では15は3と表示されます。これは、時針が12時間ごとに1回転し、時針が12を通過すると時間の数字がリセットされるためです。15は3と12を法として合同であるといい、15 ≡ 3 (mod 12)と表記します。したがって、7 + 8 ≡ 3 (mod 12)となります。

同様に、8時間待ってからさらに8時間待つ（合計16時間待つ）と、時計は4時間待った場合と同じ時刻変化を示します。これは、2 × 8 ≡ 4 (mod 12) という恒等式で表されます。ちょうど12時間待つと、時針は元の位置に戻るので、12は0として扱われます。したがって、12 ≡ 0 (mod 12) と書きます。

整数m ≥ 1を法と呼び、2 つの整数aとbは、その差a − bがmの整数倍である場合、法mに関して合同であると言います。つまり、ある整数kが存在し、

a − b = km。

mを法とする合同は合同関係であり、加算、減算、乗算と互換性のある同値関係であることを意味します。mを法とする合同は次のように表されます。

${\displaystyle a\equiv b{\pmod {m}}.}$

括弧は、(mod m ) が右辺 (ここではb ) だけでなく、方程式全体に適用されることを意味します。

この表記は、 b mod mまたは( b mod m ) (「mod」の直前に括弧がない場合) という表記と混同してはいけません。これは、 bをmで割ったときの余り、つまり剰余演算を表します。つまり、b mod m は、 0 ≤ r < mかつr ≡ b (mod m )となる一意の整数rを表します。したがって、関係式は次のようになります。$${\displaystyle a\equiv b{\pmod {m}}}$$必ず読むべき$${\displaystyle (a\equiv b){\bmod {m}},}$$ そして、$${\displaystyle a{\bmod {m}}=b{\bmod {m}}.}$$

合同関係a ≡ b (mod m )は次のように書き換えることができる。 $${\displaystyle \exists k\in \mathbb {Z} \quad a=km+b,}$$ユークリッド除法 との関係を明確に示している。ただし、ここでのbは、 aをmで割ったときの余りである必要はない。むしろ、a ≡ b (mod m )は、 aとb をmで割ったときの余りが同じであることを主張している。つまり、

a = pm + r、

b = qm + r、

ここで、0 ≤ r < mは共通剰余です。これら 2 つの式を減算し、k = p − qと設定することで、以前の関係 ( a − b = km ) を復元します。

mを法とする合同式はmによる割り算によって定義され、−1は整数環の単元であるため、ある数が−mで割り切れるのは、その数がmで割り切れる場合のみです。これは、すべてのゼロでない整数m を法として用いることができることを意味します。

合同関係は同値関係 のすべての条件を満たしている。

• 反射律: a ≡ a (mod m )
• 対称性: a ≡ b (mod m )は、 b ≡ a (mod m )の場合に限り成り立つ。
• 推移性：a ≡ b (mod m )かつb ≡ c (mod m )ならば、a ≡ c (mod m )である。

a ₁ ≡ b ₁ (mod m )かつa ₂ ≡ b ₂ (mod m )、またはa ≡ b (mod m )の場合、次のようになります。^{[ 2 ]}

• 任意の整数kに対してa + k ≡ b + k (mod m )が成り立つ（翻訳との互換性のため）
• ka ≡ kb (mod m )は任意の整数kに対して成り立つ（スケーリングとの互換性のため）
• 任意の整数kに対してka ≡ kb (mod km )が成り立つ。
• a ₁ + a ₂ ≡ b ₁ + b ₂ (mod m ) (加算との互換性)
• a ₁ − a ₂ ≡ b ₁ − b ₂ (mod m ) (減算との互換性)
• a ₁ a ₂ ≡ b ₁ b ₂ (mod m ) (乗算との互換性)
• 任意の非負整数kに対してa ^k ≡ b ^k (mod m )が成り立つ（べき乗との互換性）
• p ( a )≡p ( b ) (mod m )は、整数係数を持つ任意の多項式p ( x )に対して成り立つ（多項式評価との互換性）。

a ≡ b (mod m )の場合、一般にk ^a ≡ k ^b (mod m )は偽である。しかし、以下は真である。

• c ≡ d (mod φ ( m ))の場合、 φはオイラーのトーシェント関数であり、a ^c ≡ a ^d (mod m )となる。ただし、 aはmと互いに素である。

a ≡ b (mod mn )ならば、a ≡ b (mod m )およびa ≡ b (mod n )が成り立つ。

一般的な契約条件の解除については、以下の規定があります。

• a + k ≡ b + k (mod m ) （ただしkは任意の整数）ならば、 a ≡ b (mod m )である。
• ka ≡ kb (mod m )であり、 k がmと互いに素である場合、a ≡ b (mod m )が成り立つ。
• ka ≡ kb (mod km )かつk ≠ 0の場合、a ≡ b (mod m )となります。

最後のルールは、モジュラー演算を除算に移行するために使用できます。b が a を割り切る場合、( a / b ) mod m = ( a mod ( bm )) / bとなります。

モジュラー乗法逆元は、以下の規則によって定義されます。

• 存在条件： aとmが互いに素である場合に限り、aa ⁻¹ ≡ 1 (mod m )となるような整数a ⁻¹が存在する。この整数a ^−1は、 mを法とするaのモジュラー乗法逆元と呼ばれる。
• a ≡ b (mod m )かつa ⁻¹が存在する場合、a ⁻¹ ≡ b ⁻¹ (mod m )が成り立つ（乗法逆元との互換性、およびa = bの場合、mを法とする一意性）。
• ax ≡ b (mod m )でa がmと互いに素である場合、この線形合同式の解はx ≡ a ⁻¹ b (mod m )で与えられます。

乗法逆元x ≡ a ⁻¹ (mod m )は、拡張ユークリッドアルゴリズムを使用して、ベズー方程式a x + my = 1をx、yについて 解くことにより効率的に計算できます。

特に、pが素数である場合、0 < a < pを満たすすべてのaに対してaはpと互いに素である。したがって、 pを法として 0 と合同でないすべてのaに対して乗法逆元が存在する。

合同関係のより高度な性質には、次のようなものがあります。

• フェルマーの小定理：pが素数でaを割り切らないならば、a ^{p −1} ≡ 1 (mod p )である。
• オイラーの定理：aとmが互いに素である場合、a ^{φ ( m )} ≡ 1 (mod m )が成り立つ。ただし、φはオイラーのトーシェント関数である。
• フェルマーの小定理の単純な帰結として、pが素数であれば、a ⁻¹ ≡ a ^{p −2} (mod p )は0 < a < pの乗法逆元である。より一般的には、オイラーの定理から、aとmが互いに素であれば、a ⁻¹ ≡ a ^{φ ( m )−1} (mod m )となる。したがって、ax ≡ 1 (mod m )であれば、x ≡ a ^{φ ( m )−1} (mod m )となる。
• もう一つの単純な帰結は、φがオイラーのトーシェント関数である場合、 a ≡ b (mod φ ( m ))ならば、kがmと互いに素である限り、 k ^a ≡ k ^b (mod m )が成り立つということである。
• ウィルソンの定理：pが素数であるのは、 ( p − 1)! ≡ −1 (mod p )が成り立つ場合のみである。
• 中国剰余定理：任意のa、b と互いに素なm、nに対して、 x ≡ a (mod m )かつx ≡ b (mod n )となるようなx (mod mn )が一意に存在する。実際、 x ≡ bm _n ⁻¹ m + an _m ⁻¹ n (mod mn )であり、 m _n ^−1はmの法nに関する逆元、n _m ^−1はn の法mに関する逆元である。
• ラグランジュの定理：pが素数であり、f ( x ) = a₀xᵈ ⁺ ... + aᵈ_が整数係数の多項式であり、 p_がa₀の約数でない場合、合同式f ( x )≡0(mod p )は 最大でd個の_非合同解を持つ。
• mを法とする原始根: 数gがmを法とする原始根であるとは、 mと互いに素な任意の整数a に対して、 g ^k ≡ a (mod m )となる整数kが存在する場合をいう。 mを法とする原始根が存在するのは、 mが2、4、p ^kまたは2 p ^kに等しい場合のみである。ここで、pは奇素数、kは正の整数である。 m を法とする原始根が存在する場合、そのような原始根はちょうどφ ( φ ( m ))個存在する。ここで、φはオイラーのトーシェント関数である。
• 平方剰余: 整数a が法m の平方剰余であるとは、 x ² ≡ a (mod m )となる整数x が存在する場合をいう。オイラーの判定法によれば、p が奇素数であり、aがpの倍数でない場合、a が法pの平方剰余であるのは、次の場合に限る。

  a ^{( p −1)/2} ≡ 1 (mod p )。

合同関係は同値関係の一種です。整数aの法mに関する同値類は、任意の整数kに対してa + kmの形のすべての整数の集合です。これは、法mに関するaの合同類または剰余類と呼ばれ、 ( a mod m )と表記することも、法m が文脈からわかっている場合はaまたは[ a ]と表記することもできます。 

mを法とする各剰余類には、次の範囲内の整数がちょうど 1 つ含まれる。 ${\displaystyle 0,...,|m|-1}$したがって、これらは${\displaystyle |m|}$整数は、それぞれの剰余類の代表値である。

一般的に、整数の集合よりも整数そのものを扱う方が容易です。つまり、剰余類ではなく、代表元を扱う方がはるかに容易です。

したがって、( a mod m )は一般に0 ≤ r < mかつr ≡ a (mod m )を満たす唯一の整数rを表し、これはa の法mの剰余と呼ばれます。 

特に、( a mod m ) = ( b mod m )はa ≡ b (mod m )と同等であり、このことから、この文脈では " ≡ "の代わりに" = " がよく使われる理由が説明できます。

mを法とする各剰余類は、そのメンバーのいずれか 1 つで表すことができますが、通常は各剰余類をそのクラスに属する最小の非負整数で表します^{[ 3 ]} (これは除算の結果として得られる真の剰余であるため) 。mを法とする異なる剰余類の任意の 2 つのメンバーは、mを法として合同ではありません。さらに、すべての整数は、 mを法とする 1 つの剰余類にのみ属します。^{[ 4 ]}

整数の集合{0, 1, 2, ..., m − 1}は、法mの最小剰余系と呼ばれます。m個の整数の集合で、 mを法として合同でない2つの整数の集合は、法m の完全剰余系と呼ばれます。

最小剰余系は完全剰余系であり、完全剰余系とは、mを法とする各剰余類の代表元をちょうど 1 つ含む集合のことである。^{[ 5 ]}例えば、4 を法とする最小剰余系は{0, 1, 2, 3}である。4 を法とするその他の完全剰余系には、以下のようなものがある。

• {1, 2, 3, 4}
• {13, 14, 15, 16}
• {−2, −1, 0, 1}
• {−13, 4, 17, 18}
• {−5, 0, 6, 21}
• {27, 32, 37, 42}

4を法とする剰余系として完全ではない集合の例をいくつか挙げる。

• {−5, 0, 6, 22}、なぜなら6 は4を法として22と合同だからである。
• {5, 15}、なぜなら4 を法とする完全な剰余系は、ちょうど4 つの不一致な剰余類を持たなければならないからである。

この段落の文脈では、絶対値mはほぼ常に正の値として扱われます。

mを法とするすべての合同類の集合は、 mを法とする整数環と呼ばれる環であり、次のように表される。${\textstyle \mathbb {Z} /m\mathbb {Z} }$、${\displaystyle \mathbb {Z} /(m)}$、${\displaystyle \mathbb {Z} /m}$、 または${\displaystyle \mathbb {Z} _{m}}$[ ^{7 ]}指輪^​${\displaystyle \mathbb {Z} /m\mathbb {Z} }$は、数学のさまざまな分野の基礎となるものです（下記の§ 応用を参照）。(数論の一部では、表記法は${\displaystyle \mathbb {Z} _{m}}$（m進整数の集合と混同される可能性があるため、避ける。）

m > 0の場合、次のようになります。

${\displaystyle \mathbb {Z} /m\mathbb {Z} =\left\{{\overline {a}}_{m}\mid a\in \mathbb {Z} \right\}=\left\{{\overline {0}}_{m},{\overline {1}}_{m},{\overline {2}}_{m},\ldots ,{\overline {m{-}1}}_{m}\right\}.}$

m = 1 の場合、${\displaystyle \mathbb {Z} /m\mathbb {Z} }$はゼロリングです。m = 0の場合、${\displaystyle \mathbb {Z} /m\mathbb {Z} }$は空集合ではなく、むしろ と同型である。${\displaystyle \mathbb {Z} }$なぜなら、a ₀ = { a }だからです。

加算、減算、乗算は以下のように定義されます。${\displaystyle \mathbb {Z} /m\mathbb {Z} }$以下の規則に従う：

• ${\displaystyle {\overline {a}}_{m}+{\overline {b}}_{m}={\overline {(a+b)}}_{m}}$
• ${\displaystyle {\overline {a}}_{m}-{\overline {b}}_{m}={\overline {(a-b)}}_{m}}$
• ${\displaystyle {\overline {a}}_{m}{\overline {b}}_{m}={\overline {(ab)}}_{m}.}$

前述の性質から、これらの操作では、${\displaystyle \mathbb {Z} /m\mathbb {Z} }$は可換環である。例えば、環では${\displaystyle \mathbb {Z} /24\mathbb {Z} }$1つは

${\displaystyle {\overline {12}}_{24}+{\overline {21}}_{24}={\overline {33}}_{24}={\overline {9}}_{24}}$

24時間制の時計の計算のように。

表記法${\displaystyle \mathbb {Z} /m\mathbb {Z} }$この環はの剰余環であるため、が使用される。${\displaystyle \mathbb {Z} }$理想によって${\displaystyle m\mathbb {Z} }$mのすべての倍数で構成される集合、つまり、すべての数kmで${\displaystyle k\in \mathbb {Z} .}$

さらに、${\displaystyle \mathbb {Z} /m\mathbb {Z} }$は巡回群である。すべての有限巡回群は と同型である。${\displaystyle \mathbb {Z} /m\mathbb {Z} }$あるmに対して。^{[ 8 ]}

mを法とする整数環は体である。すなわち、m が素数である場合に限り、すべての非零元は乗法逆元を持つ。m = p ^{k が}k > 1 の素数のべき乗である場合、同型を除いて一意な有限体が存在する。${\displaystyle \mathrm {GF} (m)=\mathbb {F} _{m}}$m個の要素を持つが、同型ではない${\displaystyle \mathbb {Z} /m\mathbb {Z} }$これは零因子を持つため、体ではありません。

m > 1 の場合、${\displaystyle (\mathbb {Z} /m\mathbb {Z} )^{\times }}$は、 mを法とする整数の乗法群で、可逆なものを表します。これは、aがmと互いに素である合同類a _mから構成されます。これらはまさに乗法逆元を持つ類です。これらは乗法に関してアーベル群を形成し、その位数はφ ( m )です。ここでφはオイラーのトーシェント関数です。

純粋数学において、モジュラー算術は数論の基礎の一つであり、その研究のほぼあらゆる側面に関わっています。また、群論、環論、結び目理論、抽象代数学においても幅広く用いられています。応用数学においては、数式処理、暗号理論、コンピュータ科学、化学、そして視覚芸術や音楽芸術などで活用されています。

非常に実用的な応用例として、シリアル番号識別子内のチェックサムを計算することが挙げられます。たとえば、国際標準図書番号（ISBN）は、エラー検出のためにモジュロ11（10桁のISBNの場合）またはモジュロ10（13桁のISBNの場合）の演算を使用します。同様に、国際銀行口座番号（IBAN）は、銀行口座番号へのユーザー入力エラーを検出するためにモジュロ97の演算を使用します。化学では、CAS登録番号（各化学化合物の固有の識別番号）の最後の桁はチェックデジットであり、CAS登録番号の最初の2つの部分の最後の桁に1を掛け、その前の桁に2を掛け、さらにその前の桁に3を掛けるなどして、これらをすべて足し合わせ、その合計をモジュロ10で計算することによって算出されます。

暗号学において、モジュラー演算はRSAやDiffie-Hellmanなどの公開鍵システムを直接支え、楕円曲線の基礎となる有限体を提供し、 Advanced Encryption Standard (AES)、International Data Encryption Algorithm (IDEA)、RC4などのさまざまな対称鍵アルゴリズムで使用されています。RSAとDiffie-Hellmanはモジュラーべき乗を使用します。

コンピュータ代数では、モジュラー演算は中間計算やデータにおける整数係数のサイズを制限するためによく使用されます。これは、既知の効率的なアルゴリズムがすべてモジュラー演算を使用する問題である多項式の因数分解で使用されます。これは、整数と有理数上の多項式の最大公約数、厳密線形代数、およびグロブナー基底アルゴリズムの最も効率的な実装で使用されます。 1980年代にFidonetに投稿され、 Rosetta Codeにアーカイブされているように、モジュラー演算は、20年前に総当たり探索によってそれを否定するために使用されたCDC 6600スーパーコンピュータで使用された整数精度のわずか4分の1を使用して、Sinclair QLマイクロコンピュータでオイラーのべき乗和予想を否定するために使用されました。^{[ 9 ]}

コンピュータサイエンスにおいて、モジュラ演算は、ビット演算や、固定幅の循環データ構造を含むその他の演算によく用いられます。多くのプログラミング言語や電卓に実装されている剰余演算は、この文脈でよく使われるモジュラ演算の応用例です。論理演算子XORは、2ビットを2で割った余りを計算します。

任意の基数bにおいて、分数を循環小数に変換する長除法は、分母を法とするbの剰余乗算と同等です。例えば、10 の場合、b = 10 となります。

音楽では、12 を法とする算術は、 12 音律平均律の体系を考える際に使用され、オクターブと異名同音の等価性が生じます (つまり、1:2 または 2:1 の比率の音高は等価であり、Cシャープは Dフラットと同じとみなされます)。

9の倍数を取る方法は、手計算で行った10進数の計算を素早く確認できる方法です。これは、9を法とする剰余演算、特に10≡1（mod 9）という重要な性質に基づいています。

7を法とする演算は、特定の日付の曜日を決定するアルゴリズムで使用されます。特に、ツェラーの合同式やドゥームズデイ・アルゴリズムは、7を法とする演算を多用しています。

より一般的に言えば、モジュラー算術は、政治（例えば、議席配分）、経済学（例えば、ゲーム理論）、その他の社会科学分野など、比例配分や資源配分が分析の中心となる分野にも応用されている。

モジュラー算術は幅広い応用分野を持つため、合同式の連立方程式を解くのがどれほど難しいかを知っておくことは重要です。線形合同式は、ガウス消去法の一種を用いて多項式時間で解くことができます（詳細は線形合同定理を参照）。また、モンゴメリー還元法などのアルゴリズムを用いることで、乗算や法mのべき乗といった単純な算術演算を大きな数に対して効率的に実行することも可能です。 

離散対数や二次合同式を求めるといった演算は、整数因数分解と同じくらい難しいように思われ、暗号アルゴリズムや暗号化の出発点となる。これらの問題はNP中間レベルである可能性がある。

非線形モジュラー算術方程式系の解法はNP完全である。^{[ 10 ]}

• 「合同」、数学百科事典、EMS Press、2001年 [1994年]
• このモジュラーアートに関する記事では、モジュラー算術のアートにおける応用について詳しく学ぶことができます。
• GIMPS wiki のモジュラー算術に関する記事
• モジュラー算術と加算・乗算表のパターン