モジュロ

コンピュータや数学において、剰余演算は、ある数を別の数で割った後の余り、または符号付き余りを返します。この余りは演算の法則と呼ばれます。

2 つの正の数aとnが与えられたとき、a mod n (しばしばa mod nと略される) は、 a をnで除したユークリッド除法の余りであり、aは被除数、nは除数である。^{[ 1 ]}

例えば、「5 mod 2」という式は、5を2で割ると商が2、余りが1になるため、1と評価されます。一方、「9 mod 3」は、9を3で割ると商が3、余りが0になるため、0と評価されます。

通常はaとn の両方が整数である場合に実行されますが、現在では多くのコンピュータシステムで他の種類の数値オペランドも使用できます。整数のnによる剰余演算の値の範囲は0 からn − 1です。aが整数である場合、 a mod 1 は常に 0 になります。

aまたはnのいずれか一方だけが負の値である場合、基本的な定義は成り立たなくなり、プログラミング言語によってこれらの値の定義方法が異なります。

数学では、剰余演算の結果は同値類であり、その類のどのメンバーも代表として選択できます。ただし、通常の代表は、その類に属する最小の正の剰余、つまり最小の非負の整数（つまり、ユークリッド除算の余り）です。^{[ 2 ]}ただし、他の慣習も可能です。コンピュータや電卓は、数値を保存および表現する方法が多様であるため、剰余演算の定義はプログラミング言語または基盤となるハードウェアに依存します。

ほぼすべてのコンピューティングシステムにおいて、 aを で割った商qと余りrは${\displaystyle n\neq 0}$以下の条件を満たすこと：

剰余がゼロでない場合、符号の曖昧さが残ります。剰余には負と正の 2 つの選択肢があり、その選択によって、式 (1) を満たすために 2 つの連続する商のどちらを使用する必要があるかが決まります。数論では、常に正の剰余が選択されますが、コンピューティングでは、プログラミング言語は言語とaまたはnの符号に応じて選択します。^{[ a ]}たとえば、Standard PascalとALGOL 68 は、負の除数の場合でも正の剰余 (または 0) を与え、C90 などの一部のプログラミング言語は、 nまたはaのいずれかが負の場合にそれを実装に任せます (詳細は§ プログラミング言語の下の表を参照)。一部のシステムでは、aをモジュロ0 で未定義のままにしていますが、他のシステムではaとして定義しています。

被除数と除数がともに正の場合、切り捨て、切り捨て、ユークリッドの定義は一致します。被除数が正で除数が負の場合、切り捨てとユークリッドの定義は一致します。被除数が負で除数が正の場合、切り捨てとユークリッドの定義は一致します。被除数と除数がともに負の場合、切り捨てと切り捨ての定義は一致します。

しかし、切り捨て除算は恒等式を満たす${\displaystyle ({-a})/b={-(a/b)}=a/({-b})}$[ ^{5 ] [ 6 ]​}

電卓にはmod()関数ボタンがあり、多くのプログラミング言語にも同様の関数があり、たとえばmod( a , n )のように表されます。また、一部の言語では、剰余演算子または剰余演算子として「%」、「mod」、「Mod」を使用する式もサポートしています。たとえば、やなどです。a % na mod n

同様の機能を持たない環境においては、上記の3つの定義のいずれも使用できます。

剰余演算の結果が被除数の符号を持つ場合（切り捨て定義）、驚くべき間違いにつながる可能性があります。

例えば、ある整数が奇数かどうかを判定するには、2を引いた余りが1になるかどうかを判定するという方法が考えられるかもしれません。

bool is_odd ( int n ) { return n % 2 == 1 ; }

しかし、剰余演算が被除数の符号を持つ言語では、これは誤りです。なぜなら、 n（被除数）が負で奇数の場合、n mod 2 は −1 を返し、関数は false を返すからです。

正しい代替手段の一つは、余りが0でないことをテストすることです（余り0は符号に関係なく同じであるため）。

bool is_odd ( int n ) { return n % 2 != 0 ; }

または、二進数演算を用いると次のようになります。

bool is_odd ( int n ) { return n & 1 ; }

剰余演算は、毎回剰余を伴う除算を計算するように実装される場合があります。特殊なケースでは、一部のハードウェアでは、より高速な代替手段が存在します。たとえば、2のべき乗の剰余は、ビットごとのAND演算として表現することもできます（ xが正の整数である場合、または切り捨てを行わない定義を使用する場合）。

x % 2n == x & (2n - 1)

例：

x % 2 == x & 1

x % 4 == x & 3

x % 8 == x & 7

モジュロ演算よりも効率的にビット演算を実行するデバイスやソフトウェアでは、これらの代替形式により計算速度が向上する可能性があります。^{[ 7 ]}

コンパイラの最適化では、 が 2 のべき乗である形式の式を認識し、 として自動的に実装することで、プログラマがパフォーマンスを損なうことなく、より明確なコードを記述できるようになります。この単純な最適化は、被除数が符号なし整数型でない限り、剰余演算の結果が被除数の符号と同じになる言語 ( Cを含む) では不可能です。これは、被除数が負の場合、剰余も負になるのに対し、は常に正になるためです。これらの言語では、代わりにビットごとの OR、NOT、AND 演算を使用して表現される等価性を使用する必要があります。expression % constantconstantexpression & (constant-1)expression & (constant-1)x % 2n == x < 0 ? x | ~(2n - 1) : x & (2n - 1)

定数除数最適化を使用して最初に除算を計算することによって、一般的な定数モジュラス演算の最適化も存在します。

一部の剰余演算は、他の数学演算と同様に因数分解または展開できます。これは、ディフィー・ヘルマン鍵交換などの暗号証明において役立つ場合があります。乗算、除算、べき乗に関する性質は、一般的にaとnが整数であることを要求します。

• 身元：
  • ( a mod n ) mod n = a mod n。
  • すべての正の整数xに対してn ^x mod n = 0 が成り立つ。
  • p がbの約数でない素数である場合、フェルマーの小定理によりab ^{p −1} mod p = a mod pとなります。
• 逆:
  • [(− a mod n ) + ( a mod n )] mod n = 0。
  • b ⁻¹ mod nはモジュラー乗法逆元を表し、 bとnが互いに素である場合に 限り定義されます。これは、左辺が[( b ⁻¹ mod n )( b mod n )] mod n = 1と定義されている場合に該当します。
• 分配法則:
  • ( a + b ) mod n = [( a mod n ) + ( b mod n )] mod n。
  • ab mod n = [( a mod n )( b mod n )] mod n。
• 除算（定義）：右辺が定義されている場合（つまり、b と n が互いに素である場合）、a / b mod n = [ ( a mod n ) ( b −1 mod n ) ^] mod nであり、それ以外の場合は定義されません。
• 逆乗算: [( ab mod n )( b ⁻¹ mod n )] mod n = a mod n。

さらに、多くのコンピュータシステムにはdivmod、商と余りを同時に計算する機能が備わっています。例としては、 x86アーキテクチャの`input`命令DIVやIDIV`input`命令、C言語の` div()input`関数、Pythonの` divmod()input`関数などが挙げられます。

• モジュロ（曖昧さ回避） –モジュロという言葉には多くの用法があり、それらはすべて1801年のカール・F・ガウスのモジュラー算術へのアプローチから発展したものです。
• モジュロ（数学）、数学における用語の一般的な用法
• モジュラーべき乗
• 回転（角度）

• Modulorama：九九表の循環表現のアニメーション（フランス語による説明）