剰余類での演算

整数で割った余りの世界での演算のことを剰余演算といいます。重要な性質を紹介します。

剰余演算

整数 a, b を整数 p で割った時に余りが等しい場合に a \equiv b \pmod p と書きます。また abp を法として合同であるといいます。

さて、整数 p を法として a_1, a_2b_1, b_2 がそれぞれ合同である、つまり a_1 \equiv a_2 \pmod pb_1 \equiv b_2 \pmod p であるとき a_1 + b_1 \equiv a_2 + b_2 \pmod p がなりたつでしょうか。言い換えると、適当な整数で割った余りを考える世界で演算が自由に行えるでしょうか。

例えば p = 7a_1 = 3, a_2 = 10, b_1 = 5, b_2 = 19 としたとき a_1 + b_1 = 8 \equiv 1 \pmod 7 であり a_2 + b_2 = 29 \equiv 1 \pmod 7 であるのでよさそうです。

割った余りだけを考える世界、上記の例の p = 7 だと {0, 1, 2, 3, 4, 5, 6} だけからなる世界、のことを剰余類といいます。以降では剰余類で四則演算が (ほぼ) 自由にできることを示します。具体的には、元の間の演算が代表元のとり方によらない (p を法として合同な整数を自由に選んでも演算結果が変わらない) ことを示します。

剰余類での足し算

整数 pa_1 \equiv a_2 \pmod p, b_1 \equiv b_2 \pmod p を満たす任意の整数 a_1, a_2, b_1, b_2 に対して a_1 + b_1 \equiv a_2 + b_2 \pmod p となります。

a_1 \equiv a_2 \pmod p, b_1 \equiv b_2 \pmod p より適当な整数 m, n が存在して a_1 = a_2 + mp, b_1 = b_2 + np と書けます。このとき a_1 + b_1 = a_2 + mp + b_2 + np = a_2 + b_2 + (m + n)p \equiv a_2 + b_2 \pmod p となります。

引き算についても同様に示せます。

剰余類での掛け算

整数 pa_1 \equiv a_2 \pmod p, b_1 \equiv b_2 \pmod p を満たす任意の整数 a_1, a_2, b_1, b_2 に対して a_1 \times b_1 \equiv a_2 \times b_2 \pmod p となります。

a_1 \equiv a_2 \pmod p, b_1 \equiv b_2 \pmod p より適当な整数 m, n が存在して a_1 = a_2 + mp, b_1 = b_2 + np と書けます。このとき a_1 \times b_1 = (a_2 + mp) \times (b_2 + np) = a_2 \times b_2 + (na_2 + mb_2 + mnp)p \equiv a_2 \times b_2 \pmod p となります。

割り算に関しては同様には示せません。

剰余類での割り算

そもそも剰余類での割り算とは何でしょうか。整数の範囲では割り算を行うと結果が整数にならない可能性があります。

p = 7 の場合に掛け算を考えてみます。 3 \times 5 = 15 \equiv 1 \pmod 7 のように 35 を掛けると 1 になりました。従って 35 の逆数と考える、つまり 3 \equiv \frac{1}{5} \pmod 7 と考えてよさそうです。では次の疑問はどの要素についても逆数が存在するか、です。ただし 0 に何をかけても 0 なので 0 は除外します。

1 2 3 4 5 6
1 1 2 3 4 5 6
2 2 4 6 1 3 5
3 3 6 2 5 1 4
4 4 1 5 2 6 3
5 5 3 1 6 4 2
6 6 5 4 3 2 1

どうやら p = 7 の場合は必ず逆数が存在します。割り算は逆数をかけることと定義します。

ではどんな p に対しても逆数が存在するのかが次の疑問になります。

その疑問には次回答えるとして、それとは別に逆数の計算を効率よくできないかという疑問があります。実は ユークリッドの互除法 で紹介した方法が利用できます。

71, 2, 3, 4, 5, 6 は互いに素なので p = 7, a \not \equiv 0 \pmod p としたときに \gcd(a, p) = 1 より xa + yp = 1 となる整数 x, y が求まります。ここで 1 = xa + yp \equiv xa \pmod p より xa の逆数になります。