9.7 剰余算術

補題 9.6.1 からは、二つの整数は剰余が等しいとき合同だと分かる。つまり合同関係は剰余を計算すれば判定できる。整数に対する加算・乗算の結果を \(n\) で割った剰余を求めるときは、各ステップで剰余を取るようにすれば \([0..n)\) に属する整数に対する演算だけで全体の結果の剰余を計算できる。

剰余算術の一般原理 (general principle of remainder arithmetic)

整数を加算・乗算で組み合わせた式の値を \(n\) で割った剰余は、次のように計算できる:

式に含まれる整数を \(n\) で割った剰余に置き換える。
部分式の加算と乗算の値を計算するたびに、その結果を \(n\) で割った剰余で置き換えてから計算を進める。

例えば、次の値を計算したいとする:

\[ \operatorname{rem}((44427^{3456789} + 15555858^{5555}) \cdot 403^{6666666}, 36) \tag{9.9}\]

それぞれの冪乗を実際に計算して最後に剰余を計算するとしたら大変なことになる。例えば \(44427^{3456789}\) の十進表記は約 \(2000\) 万桁なので、とても計算できない。しかし、整数乗は乗算の繰り返しを意味することを思い出せば、上記の剰余算術の一般原理を使って冪乗の底を剰余に置き換えられる。\(\operatorname{rem}(44427, 36) = 3\), \(\operatorname{rem}(15555858, 36) = 6\), \(\operatorname{rem}(403, 36) = 7\) なので、式 \(\text{(9.9)}\) は次の式を \(36\) で割った剰余に等しいと分かる:

\[ (3^{3456789} + 6^{5555}) \cdot 7^{6666666} \tag{9.10}\]

これで問題は少し簡単になった。しかし \(3^{3456789}\) の十進表記は約百万桁なので、これも計算できない。そこで \(3\) の冪を \(36\) で割ったときのパターンに注目する:

\[ \begin{aligned} \operatorname{rem}(3^{1}, 36) &= 3 \\ \operatorname{rem}(3^{2}, 36) &= 9 \\ \operatorname{rem}(3^{3}, 36) &= 27 \\ \operatorname{rem}(3^{4}, 36) &= 9 \end{aligned} \]

二つ目のステップ \(\operatorname{rem}(3^{2}, 36)\) と同じ値がわずか \(2\) ステップ後に得られた。よって、\(3\) の冪を \(36\) で割った余りは \(3^{2}\) 以降 \(9\), \(27\), \(9\), \(\ldots\) となる。言い換えれば \(3\) の \(3\) 以上の奇数乗を \(36\) で割った余りは常に \(27\) であり、次の等式が分かる:

\[ \operatorname{rem}(3^{3456789}, 36) = \operatorname{rem}(3^{3}, 36) = 27 \]

素晴らしい単純化だ！

\(6\) の冪はさらに簡単になる: \(\operatorname{rem}(6^{2}, 36) = 0\) であり、その後は \(0\) だけが続く。\(7\) の冪は \(6\) ステップごとに同じ値を繰り返す。ただ、ここでは \(6\) ステップ目で \(\operatorname{rem}(7^{6}, 36) = 1\) となる事実を利用できる。以上より、式 \(\text{(9.10)}\) は次のように単純化できる:

\[ \begin{aligned} (3^{3456789} + 6^{5555}) \cdot 7^{6666666} & \equiv (3^{3} + 6^{2} \cdot 6^{5553}) \cdot (7^{6})^{1111111} \\ & \equiv (3^{3} + 0 \cdot 6^{5553}) \cdot 1^{1111111} \\ & \equiv 27 \quad (\text{mod } 36) \end{aligned} \]

この例からも分かるように、冪乗の指数を剰余で置き換えてはいけない。剰余の一般原理を適用できるのは加算と乗算のオペランドだけであり、冪乗の指数は乗算を実行する回数を表す。この点には注意してほしい。

9.7.1 整数環

続いて剰余の一般原理をさらに詳しく説明し、それが正しい理由を示す。まず、「加算の結果を \(n\) で割ったときの剰余を取る」という剰余の一般原理で用いられる操作を二項演算として記号 \(+_{n}\) で表すと定める。乗算についても同様とする:

\[ \begin{aligned} i +_{n} j &::= \operatorname{rem}(i + j, n) \\ i \cdot_{n} j &::= \operatorname{rem}(ij, n) \end{aligned} \]

これらの記号を使うと、剰余の一般原理は次の補題を繰り返し適用できる事実を言っていると理解できる:

補題 9.7.1

\[ \operatorname{rem}(i + j, n) = \operatorname{rem}(i, n) +_{n} \operatorname{rem}(j, n) \tag{9.11}\]

\[ \operatorname{rem}(ij, n) = \operatorname{rem}(i, n) \cdot_{n} \operatorname{rem}(j, n) \tag{9.12}\]

証明系 9.6.3 より \(i \equiv \operatorname{rem}(i, n)\) と \(j \equiv \operatorname{rem}(j, n)\) が分かる。よって補題 9.6.4 より次を得る:

\[ i + j \equiv \operatorname{rem}(i, n) + \operatorname{rem}(j, n) \quad (\text{mod } n) \]

またしても系 9.6.3 より、この合同関係の両辺は \(n\) で割ったときの剰余が等しい。よって一つ目の等式 \(\text{(9.11)}\) は成り立つ。等式 \(\text{(9.12)}\) も同様に示せる。 ■

集合 \([0..n)\) と二つの演算 \(+_{n}\), \(\cdot_{n}\) を合わせたものを法 \(n\) の整数環 (ring of integers modulo \(n\)) と呼び、\(\mathbb{Z}_{n}\) と表記する。補題 9.7.1 から、\(\mathbb{Z}_{n}\) では通常の算術と同様に次の規則が成り立つと分かる:

\[ (i \cdot_{n} j) \cdot_{n} k = i \cdot_{n} (j \cdot_{n} k) \]

二項演算子に添え字の \(n\) を付けると数式が非常に読みにくいので、これからは次のように \((\mathbb{Z}_{n})\) を数式の末尾に付けることにする:

\[ (i \cdot j) \cdot k = i \cdot (j \cdot k) \quad (\mathbb{Z}_{n}) \]

また、文脈から明らかな場合は \((\mathbb{Z}_{n})\) も省略する。

\(\mathbb{Z}_{n}\) で成り立つ等式¹とその名称を次に示す:

\[ \begin{aligned} (i + j) + k &= i + (j + k) && (+ \text{ の結合性}) \\ (i \cdot j) \cdot k &= i \cdot (j \cdot k) && (\cdot \text{ の結合性}) \\ i + j &= j + i && (+ \text{ の可換性}) \\ i \cdot j &= j \cdot i && (\cdot \text{ の可換性}) \\ 0 + k &= k && (+ \text{ の単位元}) \\ 1 \cdot k &= k && (\cdot \text{ の単位元}) \\ k + (-k) &= 0 && (+ \text{ の逆元}) \\ i \cdot (j + k) &= (i \cdot j) + (i \cdot k) && (\cdot \text{ の分配律}) \\ \end{aligned} \]

\(\cdot\) の結合律からは、積を書くとき括弧が必要ないというよく知られた事実が得られる:

\[ k_{1} \cdot k_{2} \cdots k_{m} \]

\(\mathbb{Z}_{n}\) においても、この積の値はどのように括弧が付けても変化しない。

まとめると、剰余算術は通常の算術によく似ている。ただ、これから見るように例外もいくつかある。

加算演算と乗算演算を持つ集合がここに示す等式を満たすとき、それを可換環 (commutative ring) と呼ぶ。\(\mathbb{Z}_{n}\) の他にも、整数全体の集合、有理数全体の集合、実数全体の集合、整数係数多項式全体の集合は全て可換環である。一方、真理値全体の集合 \(\left\{ \textbf{T}, \textbf{F} \right\}\) で \(\operatorname{\text{\footnotesize OR}}\) を加算、\(\operatorname{\text{\footnotesize AND}}\) を乗算としたものは可換環でない。また、\(n \times n\) の整数行列全体の集合も可換環ではない (二つの例が満たさない等式は異なる)。 ↩︎