🕒 2020/04/14 🔄 2024/10/16

商と剰余演算の具体例

🌏

ここでは、余りの計算について振り返った後、商の剰余演算の具体例を見ていくことにします。

📘 目次

剰余演算の具体例
商の剰余演算の具体例
おわりに

剰余演算の具体例

余りの計算では、剰余演算について見ました。剰余演算とは、ある正の整数 $p$ で割った余りの世界で計算を行うことです。この世界では、余りが等しいなら "同じもの" とみなします。例えば、次の式が成り立ちます。 $10 \equiv 3 (\mod 7)$ これは、 $10$ も $3$ も、 $7$ で割った余りが等しい、ということを表しています。

剰余演算では、和・差・積について、便利な性質があります。少し抽象的に書くと、
$\begin{array}{r} a \equiv m (\mod p) \\ b \equiv n (\mod p) \end{array}$ のとき、次の式が成り立ちます。
$\begin{array}{r} a + b \equiv m + n (\mod p) \\ a - b \equiv m - n (\mod p) \\ a b \equiv m n (\mod p) \end{array}$

例えば、 $10 \equiv 3 (\mod 7)$ であることから、 $10 + 2 \equiv 3 + 2 (\mod 7)$ , $10 - 2 \equiv 3 - 2 (\mod 7)$ , $10 \cdot 2 \equiv 3 \cdot 2 (\mod 7)$ などが成り立つ、ということです。もちろん、計算すれば成り立つことが確かめられます。この性質は、余りの計算と、和・差・積の計算は、どちらを先にやってもいい、と考えることもできます。

ところが、商ではこういう性質は成り立ちません。例えば、先ほどの文字を使って書けば、 $a \div b$ と $m \div n$ は $p$ で割った余りが等しくなるとは限りません。 $10 \div 2 = 5$ ですが、 $3 \div 2$ はそもそも整数ではないですし、 $5$ に関する数字がでてくる気配はありません。

このように、商に関しては、同じような性質は成り立たないのですが、それだと少し不便です。例えば、競プロでは、場合の数を求めることがあり、 $_{n} C_{k}$ を $10^{9} + 7$ で割った余りを求める、という場面がよくあります。パスカルの三角形と組合せで見たように、 $n, k$ が $10^{3}$ や $10^{4}$ くらいであれば計算できるので問題ないのですが、もっと大きい場合は、パスカルの三角形を使う方法は無理です。また、分母にある $k!$ , $(n - k)!$ は、値が大きすぎて直接値を計算することはできません。しかも、先ほど見たように、余りを計算してから商を計算する、ということはできないんですね。不便です。

ただ、この問題は、ある条件のもとではクリアできます。具体的な例で計算をしてみます。

商の剰余演算の具体例

先ほどの $10 \div 2 (\mod 7)$ について考えてみましょう。この割り算の部分をなんとかして計算できるようにしましょう。

ここで、天下り的ですが、 $8$ を掛けることを考えてみます。 $8 \equiv 1 (\mod 7)$ なので、 $7$ で割った余りを考える世界では、 $8$ を掛けることは $1$ を掛けることと同じであり、掛けたとしても余りには影響しません。しかも、これは2の倍数なので、次のようにうまく計算することができます。なお、 $mod 7$ で計算しています。
$\begin{array}{rcl} 10 \div 2 \\ \equiv & 10 \div 2 \times 8 \\ \equiv & 10 \times 4 \\ \equiv & 3 \times 4 \end{array}$
$\times 8$ は、 $mod 7$ の世界では $\times 1$ と同じ結果になるので、答えは変わりません。しかも、 $\div 2$ と相殺して、 $\times 4$ という積の形になります。こうなれば、余りの積を考えればよく、元の式は $5$ と合同だと計算できます。

つまり、 $a \div b (\mod p)$ を計算するには、 $b^{x} \equiv 1 (\mod p)$ となるような $x$ が見つかればうれしいことがわかります。 $b^{x}$ を掛けても答えは変わらないので、掛けてから計算していけばいいですね。商の部分が消えるので、計算が進んでいきます。

ではどうやってこんな数を求めるのか、という新しい問題が出てきます。これについては、数学の世界で良い性質が見つかっているので、それを利用することにします。「フェルマーの小定理」というものを使うのですが、これについては次の機会に見ることにしましょう。

おわりに

ここでは、商と剰余演算について、具体的な例を見てきました。商は和・差・積と同じようには計算できないこと、そして、工夫することで商の剰余演算もできる可能性があることを、具体的な例を通じてみてきました。フェルマーの小定理を使えば、さらに計算することができるので、次回で詳しく見ていくことにします。