剰余演算

2つの正の整数である、被除数 a および 除数 n が与えられた場合、a の n による剰余（a modulo n、略して a mod n とも表記される）は、ユークリッド除法における a を n で除算した余りである。例えば、「5 mod 2」の結果は 1 である。5を2で除算した場合、商は2となり、余りは1となるからである。また、「9 mod 3」の結果は 0 である。9を3で除算した商は3となり、余りは0となる（つまり9から3を3回引くと残りがなくなる）からである^{[注釈 1]}。

通常の場合、a と n はともに整数であるが、多くのコンピュータシステムでは他の数値型でも処理が可能である。整数 n の剰余の取りうる範囲は、0 から n − 1 までである。「n mod 1」 の場合は常に 0 となる。「n mod 0」は未定義であり、プログラミング言語によっては「ゼロ除算」のエラーを引き起こす。a または n が負数の場合については、単純な定義はなく、プログラミング言語によってどのように定義されるかが異なっている。

数論における古典的な関連事項については合同算術を参照。

数学的には、剰余演算の結果はユークリッド除法における余りのことである。しかし、別の法則に従って算出されることもある。コンピュータやその他の計算機は数値の保持や処理方法がさまざまなので、剰余演算の定義はプログラミング言語や動作するハードウェアによって、それぞれ規定されている。

ほぼすべてのコンピュータシステムにおいて、a を n で除算した商 q および剰余 r は下記の条件を満たす。

${\displaystyle {\begin{aligned}q&\in \mathbb {Z} \\a&=nq+r\\|r|&<|n|\end{aligned}}}$

(1)

ところが、剰余が0でない場合、その符号は不確定なものとなる。数論上は、余りは常に正の数となるが、プログラミング言語によっては a および n の符号によって剰余の符号が正となるか負となるかが定められる。標準的なPascalおよびAlgol68では、除数が負数であっても正の剰余（または0）を出力する。しかし、C89/C90規格以前のC言語やC++03規格以前のC++など、プログラミング言語によっては n または a が負の数の場合の結果の符号は特に言語仕様で規定されておらず、実装定義（処理系依存）とされていることもある^[5]。詳細は後述の表を参照のこと。多くのシステムでは a の 0 での剰余は未定義だが、いくつかは a を出力するように定義されている。

Daan Leijenはこのように記している。

Bouteはユークリッド除法が数学的に一般的で有用なので他の方法よりも優れていることを示した。しかし、クヌースの示した切り下げ除算もまたよい定義である。「0への切捨て除算」は幅広く使われているが、他の定義よりも劣っている。

—Daan Leijen、Division and Modulus for Computer Scientists^[8]

被除数の符号に剰余の結果が依存する場合、失敗を引き起こす場合がある。

例えば、ある整数が奇数であるかどうかを調べたい場合、下記のC++での例のように、2 で除算した余りが 1 であるかどうかを確かめれば良いように見える。

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

しかし、使用するプログラミング言語が、剰余の符号を被除数に依存させている場合、これは正しくない。なぜなら、n が負の奇数の場合、n % 2 は −1 となるので、この関数は false を返すからである。

正しい実装のひとつは、0 でないかどうかをチェックすることである。剰余が 0 であれば符号を気にする必要はない。

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

もちろん、どのような奇数も、剰余は 1 または −1 となるので、下記のような実装も可能である。ただし冗長であり、演算オーバーヘッドも大きくなる。

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

電卓の中には、剰余を算出する mod 関数ボタンを持つものがある。多くのプログラミング言語も類似の関数を持っており、mod(a, n) のように表記する。剰余演算子として "%"、"mod"、"Mod"などを用意しているプログラミング言語もあり、

a % n

または

a mod n

と表記する。

mod 関数または演算子が用意されていないか、正しく機能しない環境^{[注釈 2]}であっても、下記のように算出できる。ここで、int()は小数点以下を切り捨てた値を生成する。

a - (n * int(a / n))

このほか除数 n が2のべき乗である場合に限り、後述のように、除数より1少ない値と論理積を取って算出する方法が有効である。

剰余演算は、除算を行って余りを得る実装となるので、その分の処理時間を必要とする。特殊な場合においては、いくつかのハードウェア上でより高速な計算方法が存在する。

たとえば、数値の内部表現に2進法を用いているコンピュータでは、2のべき乗の剰余を計算する場合に、下記のようにビットごとのAND演算を利用することができる。

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

例を示す（x は正の整数とする）。

x % 2 == x & 1

x % 4 == x & 3

x % 8 == x & 7

剰余演算よりもビット演算のほうが効率よく処理できるデバイスやソフトウェアでは、この変換によってより高速に計算することができる^[9]。

最適化をするコンパイラには、2のべき乗による剰余演算を検出し、自動的にAND演算に変換するものもある。これによって、プログラマは性能を犠牲にすることなく、読みやすいソースコードを記述することができる。ただし、AND演算による場合、出力は常に正の数となるので、C言語のように剰余演算の結果の符号が被除数によって定まる言語では同じ動作はしない。したがって、被除数が負になる場合は、特別な注意が必要である。

他の数学的演算と同様に、剰余演算についてもいくつかの演算を導出、または拡張することができる。そうすることで、ディフィー・ヘルマン鍵交換のような暗号学分野の証明が容易となるだろう。

• 同一性:
  • ${\displaystyle (a{\bmod {n}}){\bmod {n}}=a{\bmod {n}}}$　（冪等）
  • ${\displaystyle n^{x}{\bmod {n}}=0}$ 正の整数 x の場合。
  • ${\displaystyle n}$ が素数であって b の約数でない場合、フェルマーの小定理によって ${\displaystyle ab^{n-1}{\bmod {n}}=a{\bmod {n}}}$ となる。
• 逆数:
  • ${\displaystyle ((-a{\bmod {n}})+(a{\bmod {n}})){\bmod {n}}=0}$
  • ${\displaystyle b^{-1}{\bmod {n}}}$ はモジュラ逆数を表す。これは b と n とが互いに素である場合にだけ、次式で定義される。${\displaystyle ((b^{-1}{\bmod {n}})(b{\bmod {n}})){\bmod {n}}=1}$
• 分配則:
  • ${\displaystyle (a+b){\bmod {n}}=((a{\bmod {n}})+(b{\bmod {n}})){\bmod {n}}}$
  • ${\displaystyle ab{\bmod {n}}=((a{\bmod {n}})(b{\bmod {n}})){\bmod {n}}}$
• 分数（定義）: ${\displaystyle {\frac {a}{b}}{\bmod {n}}=((a{\bmod {n}})(b^{-1}{\bmod {n}})){\bmod {n}}}$ 右辺が定義できる場合。そうでない場合は未定義。
• 逆数の乗算: ${\displaystyle ((ab{\bmod {n}})(b^{-1}{\bmod {n}})){\bmod {n}}=a{\bmod {n}}}$

以下の表では「演算子」と総称されているが、実際には演算子ではなく関数（サブルーチン）による実装となっている言語もあることに注意されたい。

いくつかの言語では浮動小数点数オペランドに対しても剰余演算子が利用できるようになっているが、IEEE 754準拠の剰余ではなく、通例整数オペランドに対する剰余と似た仕様となっている。そのため、IEEE準拠の剰余を求めるライブラリ関数が別途用意されていることも多い。Javaでは、Math.IEEEremainder()メソッドが用意されている。C#やVB.NETのような.NET言語では、Math.IEEERemainder()メソッドが用意されている^[16]。