剰余演算

剰余演算（じょうよえんざん、モジュロとも呼ぶ）は、ある数値を別の数値（法と呼ばれることもある）で除算し、余りを取得する演算である。 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回引くと残りがなくなる）からである。 通常の場合、a と n はともに整数であるが、多くのコンピュータシステムでは他の数値型でも処理が可能である。整数 n の剰余の取りうる範囲は、0 から n − 1 までである。「n mod 1」 の場合は常に 0 となる。「n mod 0」は未定義であり、プログラミング言語によっては「ゼロ除算」エラーを引き起こす。a または n が負数の場合については、単純な定義はなく、プログラミング言語によってどのように定義されるかが異なっている。 数論における古典的な関連事項については合同算術を参照。 数学的には、剰余演算の結果はユークリッド除法における余りのことである。しかし、別の法則に従って算出されることもある。コンピュータやその他の計算機は数値の保持や処理方法がさまざまなので、剰余演算の定義はプログラミング言語や動作するハードウェアによって、それぞれ規定されている。 ほぼすべてのコンピュータシステムにおいて、a を n で除算した商 q および剰余 r は下記の条件を満たす。 q ∈ Z a = n q + r | r | < | n | {\displaystyle {\begin{aligned}q\,&\in \mathbb {Z} \\a\,&=nq+r\\|r|\,&<|n|\end{aligned}}} (1) ところが、剰余が0でない場合、その符号は不確定なものとなる。数論上は、余りは常に正の数となるが、プログラミング言語によっては a および n の符号によって剰余の符号が正となるか負となるかが定められる。標準的なPascalおよびAlgol68では、除数が負数であっても正の剰余（または0）を出力する。しかし、C90のようなプログラミング言語では、n または a が負の数の場合にはそうならないことがある。詳細は右表を参照。多くのシステムでは a の 0 での剰余は未定義だが、いくつかは a を出力するように定義されている。 多くの実装においては「0への切捨て除算」が使用されている。これは商を0への切捨て関数 q = trunc(a/n) によって処理し、(1)の処理における余りは「被除数と同じ符号」となる。この場合の商は0方向に丸められる。つまり、実数での商から0の方向へ向かって直近の整数となる。 ドナルド・クヌースは「切り下げ除算」について言及した。これは商を床関数 q = ⌊ ( a / n ) ⌋ {\displaystyle q=\lfloor (a/n)\rfloor } によって処理し、(1)の処理における余りは「除数と同じ符号」となる。床関数によって、商が負の数であっても常に負の無限大方向に丸められる。 r = a − n ⌊ a n ⌋ {\displaystyle r=a-n\left\lfloor {\frac {a}{n}}\right\rfloor } Raymond T. Bouteはユークリッド除法の手法での定義について言及している。この場合、余りは非負数（0 ≤ r）となる。右表では「常に正」と表記している。この定義は下記のように表すことができる。 n > 0 ⇒ q = ⌊ a n ⌋ {\displaystyle n>0\Rightarrow q=\left\lfloor {\frac {a}{n}}\right\rfloor } n < 0 ⇒ q = ⌈ a n ⌉ {\displaystyle n<0\Rightarrow q=\left\lceil {\frac {a}{n}}\right\rceil } また、符号関数 sgn を使用すると、下記のようにも表せる。 q = sgn ⁡ ( n ) ⌊ a | n | ⌋ {\displaystyle q=\operatorname {sgn}(n)\left\lfloor {\frac {a}{\left|n\right|}}\right\rfloor } r = a − | n | ⌊ a | n | ⌋ {\displaystyle r=a-|n|\left\lfloor {\frac {a}{\left|n\right|}}\right\rfloor } Common Lispでは切り下げ除算、切り上げ除算のそれぞれについてq = round(a/n) と q = ceil(a/n) で商が与えられる。 IEEE 754-1985 の剰余は、近接丸め（英語版）を行った場合の商として定義している。したがって、剰余の符号は「0に近い側」となる。 Daan Leijenはこのように記している。 Bouteはユークリッド除法が数学的に一般的で有用なので他の方法よりも優れていることを示した。しかし、クヌースの示した切り下げ除算もまたよい定義である。「0への切捨て除算」は幅広く使われているが、他の定義よりも劣っている。 —Daan Leijen、Division and Modulus for Computer Scientists 被除数の符号に剰余の結果が依存する場合、失敗を引き起こす場合がある。 例えば、ある整数が奇数であるかどうかを調べたい場合、下記の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( ) 機能がないか、正しく機能しない環境[1]であっても、下記のように算出できる（「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言語のように剰余演算の結果の符号が被除数によって定まる言語では同じ動作はしない。したがって、被除数が負になる場合は、特別な注意が必要である。 他の数学的演算と同様に、剰余演算についてもいくつかの演算を導出、または拡張することができる。そうすることで、ディフィー・ヘルマン鍵交換のような暗号学分野の証明が容易となるだろう。 同一性: ( a mod n ) mod n = a mod n {\displaystyle (a\,{\bmod {\,}}n)\,{\bmod {\,}}n=a\,{\bmod {\,}}n} n x mod n = 0 {\displaystyle n^{x}\,{\bmod {\,}}n=0} 正の整数 x の場合。 n {\displaystyle n} が素数であって b の約数でない場合、フェルマーの小定理によって a b n − 1 mod n = a mod n {\displaystyle ab^{n-1}\,{\bmod {\,}}n=a\,{\bmod {\,}}n} となる。 逆数: ( ( − a mod n ) + ( a mod n ) ) mod n = 0 {\displaystyle ((-a\,{\bmod {\,}}n)+(a\,{\bmod {\,}}n))\,{\bmod {\,}}n=0} b − 1 mod n {\displaystyle b^{-1}\,{\bmod {\,}}n} はモジュラ逆数を表す。これは b と n とが互いに素である場合にだけ、次式で定義される。 ( ( b − 1 mod n ) ( b mod n ) ) mod n = 1 {\displaystyle ((b^{-1}\,{\bmod {\,}}n)\,(b\,{\bmod {\,}}n))\,{\bmod {\,}}n=1} 分配則: ( a + b ) mod n = ( ( a mod n ) + ( b mod n ) ) mod n {\displaystyle (a+b)\,{\bmod {\,}}n=((a\,{\bmod {\,}}n)+(b\,{\bmod {\,}}n))\,{\bmod {\,}}n} a b mod n = ( ( a mod n ) ( b mod n ) ) mod n {\displaystyle ab\,{\bmod {\,}}n=((a\,{\bmod {\,}}n)\,(b\,{\bmod {\,}}n))\,{\bmod {\,}}n} 分数（定義）: a b mod n = ( ( a mod n ) ( b − 1 mod n ) ) mod n {\displaystyle {\frac {a}{b}}\,{\bmod {\,}}n=((a\,{\bmod {\,}}n)(b^{-1}\,{\bmod {\,}}n))\,{\bmod {\,}}n} 右辺が定義できる場合。そうでない場合は未定義。 逆数の乗算: ( ( a b mod n ) ( b − 1 mod n ) ) mod n = a mod n {\displaystyle ((ab\,{\bmod {\,}}n)\,(b^{-1}\,{\bmod {\,}}n))\,{\bmod {\,}}n=a\,{\bmod {\,}}n} Modulo 曖昧さ回避ページ 冪剰余