剰余演算

剰余演算（じょうよえんざん、モジュロとも呼ぶ）は、ある数値を別の数値（法と呼ばれることもある）で除算し、余りを取得する演算である。

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

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

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

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

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

ところが、剰余が0でない場合、その符号は不確定なものとなる。数論上は、余りは常に正の数となるが、プログラミング言語によっては  および  の符号によって剰余の符号が正となるか負となるかが定められる。標準的なPascalおよびAlgol68では、除数が負数であっても正の剰余（または0）を出力する。しかし、C90のようなプログラミング言語では、 または  が負の数の場合にはそうならないことがある。詳細は右表を参照。多くのシステムでは  の 0 での剰余は未定義だが、いくつかは  を出力するように定義されている。

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

ありがちなミス 

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

例えば、ある整数が奇数であるかどうかを調べたい場合、下記の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( ) 機能を実装し、mod(a, n) のように表記する。剰余演算子として "%"、"mod"、"Mod"などを用意しているプログラミング言語もあり、
a % n
または
a mod n
と表記する。

剰余算出の代替手段 
また、mod( ) 機能がないか、正しく機能しない環境であっても、下記のように算出できる（「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

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

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

剰余演算の等価性 
他の数学的演算と同様に、剰余演算についてもいくつかの演算を導出、または拡張することができる。そうすることで、ディフィー・ヘルマン鍵交換のような暗号学分野の証明が容易となるだろう。
 同一性:
 
  正の整数  の場合。
  が素数であって  の約数でない場合、フェルマーの小定理によって  となる。
逆数:
 
  はモジュラ逆数を表す。これは  と  とが互いに素である場合にだけ、次式で定義される。
 分配則:
 
 
 分数（定義）:  右辺が定義できる場合。そうでない場合は未定義。
 逆数の乗算:

実際のプログラミング言語の挙動

関連項目 
Modulo 曖昧さ回避ページ
冪剰余

脚注

注釈 
  Perlでは剰余の算術演算子は機種依存となる。例示とその例外についてはPerl documentationを参照。
  右項は正の数でなければならない。左項は定義されていない。
  ACUCOBOL、Micro Focus COBOLなどの実装。
  たとえばファミリーベーシックのROMバージョン2.0Aでは、除数と被除数が等しい場合にMODの演算が正しく行われない。

出典 

プログラミング言語の構文
合同算術
二項演算