合同式(モジュラー演算)計算機とは?
モジュラー演算は、よく「時計算」にたとえられます。数値は法(モジュラス)n に達するとリセットされ、ぐるりと一周して戻ってくる仕組みです。この計算機は \((\text{a} \text{ op } \text{b}) \bmod \text{n}\) という形の式を計算します。演算には加算・減算・乗算のほか、単一の値 a を法 n で割った余りを求めるだけのモードも選べます。結果は常に 0 以上で最小の剰余、つまり 0 から n − 1 までの範囲の数値で返されます。
使い方
まず a に値を入力し、演算を選び、b を指定します(「mod のみ」の場合 b は無視されます)。最後に法 n を設定してください。計算機はまず式そのものを計算し、その結果を n で割った剰余に変換します。負の結果は 0…n−1 の標準的な範囲に折り返されるため、たとえば \(-1 \bmod 12\) は −1 ではなく 11 を返します。
計算式の解説
基本となる関係式は \(r = (\text{a} \text{ op } \text{b}) \bmod \text{n}\) です。プログラミングで使われる剰余演算は負の値を返すことがあるため、ここでは次の「ユークリッド型」の形を用い、必ず 0 以上の答えになるようにしています。
$$r = ((x \bmod \text{n}) + \text{n}) \bmod \text{n}$$これは整数論・暗号理論・ハッシュ計算などで標準的に使われる数学的な約束ごとと一致します。
具体例
たとえば a = 17、演算は加算、b = 25、n = 12 とします。まず $$17 + 25 = 42$$ を計算します。次に \(42 \bmod 12\) を求めると、\(42 = 3 \times 12 + 6\) なので剰余は 6 です。12 時間制の時計でいえば、17 時から 25「時間」進むと、ちょうど 6 の位置に来るということです。
負の数と掛け算を含むその他の計算例
いずれの場合も、計算機は最小の非負の剰余 \(r\) を返します。これは \(0 \le r < n\) を満たす唯一の値で、ある整数 \(q\) に対して \(\text{生の値} = n\cdot q + r\) が成り立ちます。法 \(n\) は正の整数でなければなりません。
例1:生の結果が負になる引き算
\((5 - 23) \bmod 7\) を計算します。
- 生の結果:\(5 - 23 = -18\)。
- 割り算:\(-18 = 7 \cdot (-3) + 3\)。商は \(-3\)、余りは \(3\) です。確認:\(-18 + 21 = 3\)。
- 最終的な剰余:3。
例2:掛け算
\((47 \times 19) \bmod 10\) を計算します。
- 生の結果:\(47 \times 19 = 893\)。
- 割り算:\(893 = 10 \cdot 89 + 3\)。商は \(89\)、余りは \(3\) です。
- 最終的な剰余:3。(近道:mod 10 では末尾の桁だけが重要で、\(7 \times 9 = 63\) の末尾は 3 です。)
例3:負の数の単純な剰余
\(-29 \bmod 6\) を計算します。
- 生の値:\(-29\)(単純な剰余では2つ目の数は不要です)。
- 割り算:\(-29 = 6 \cdot (-5) + 1\)。商は \(-5\)、余りは \(1\) です。確認:\(-29 + 30 = 1\)。
- 最終的な剰余:\(1\)。
商は0に向かって切り捨てるのではなく、負の無限大の方向へ切り捨てられる(丸められる)点に注意してください。これによって、余りが 0 から \(n-1\) の間に保たれます。
シナリオ比較:同じ入力、異なる演算
| a | b | n | 演算 | 生の結果 | 最終的な剰余 |
|---|---|---|---|---|---|
| 17 | 25 | 12 | 足し算 | 42 = 12·3 + 6 | 6 |
| 17 | 25 | 12 | 引き算 | −8 = 12·(−1) + 4 | 4 |
| 17 | 25 | 12 | 掛け算 | 425 = 12·35 + 5 | 5 |
| −7 | 使用しない | 5 | 単純な剰余 | −7 = 5·(−2) + 3 | 3 |
| 17 | 25 | 1 | 掛け算 | 425 = 1·425 + 0 | 0 |
\(n = 1\) のとき、すべての整数は 0 と合同になるため、結果は常に 0 になります。
注:ユークリッド法(最小の非負の剰余)による結果は、一部のプログラミング言語が返す符号付きの余りとは異なる場合があります。C、C++、Java、JavaScript では % 演算子は 0 に向かって切り捨てるため、-7 % 5 は \(-2\) になりますが、この計算機では \(3\) になります。正の法を使う Python の % は \(3\) を返し、ユークリッド法の結果と一致します。符号付きの余りが負の場合、両者の値は必ず \(n\) だけ異なります。
よくある質問
「mod」とは何ですか? 割り算をした後の「余り」を返す演算です。\(13 \bmod 5 = 3\) となるのは、\(13 = 2 \times 5 + 3\) だからです。
なぜ負の数が正の数に変わるのですか? この計算機は 0 以上で最小の剰余を返すためです。たとえば \(-7 \bmod 5 = 3\) となります。これは 5 を 2 回足すと(\(-7 + 10 = 3\))、ちょうど 0…4 の範囲に収まるからです。
n = 1 のときはどうなりますか? すべての整数は法 1 において 0 と合同なので、結果は常に 0 になります。