【競プロ】商と剰余演算の具体例
ここでは、余りの計算について振り返った後、商の剰余演算の具体例を見ていくことにします。競プロ 記事の一覧はこちら。
剰余演算の具体例
【競プロ】余りの計算では、剰余演算について見ました。剰余演算とは、ある正の整数 $p$ で割った余りの世界で計算を行うことです。この世界では、余りが等しいなら "同じもの" とみなします。例えば、次の式が成り立ちます。\[ 10\equiv 3 \pmod 7 \]これは、 $10$ も $3$ も、 $7$ で割った余りが等しい、ということを表しています。
剰余演算では、和・差・積について、便利な性質があります。少し抽象的に書くと、
\begin{eqnarray}
a\equiv m \pmod p \\[5pt]
b\equiv n \pmod p
\end{eqnarray}のとき、次の式が成り立ちます。
\begin{eqnarray}
a+b\equiv m+n \pmod p \\[5pt]
a-b\equiv m-n \pmod p \\[5pt]
ab\equiv mn \pmod p
\end{eqnarray}
例えば、 $10\equiv 3 \pmod 7$ であることから、 $10+2\equiv 3+2 \pmod 7$, $10-2\equiv 3-2 \pmod 7$, $10\cdot2\equiv 3\cdot2 \pmod 7$ などが成り立つ、ということです。もちろん、計算すれば成り立つことが確かめられます。この性質は、余りの計算と、和・差・積の計算は、どちらを先にやってもいい、と考えることもできます。
ところが、商ではこういう性質は成り立ちません。例えば、先ほどの文字を使って書けば、 $a\div b$ と $m\div n$ は $p$ で割った余りが等しくなるとは限りません。 $10\div 2=5$ ですが、 $3\div 2$ はそもそも整数ではないですし、 $5$ に関する数字がでてくる気配はありません。
このように、商に関しては、同じような性質は成り立たないのですが、それだと少し不便です。例えば、競プロでは、場合の数を求めることがあり、 ${}_n\mathrm{C}_k$ を $10^9+7$ で割った余りを求める、という場面がよくあります。【競プロ】パスカルの三角形と組合せで見たように、 $n,k$ が $10^3$ や $10^4$ くらいであれば計算できるので問題ないのですが、もっと大きい場合は、パスカルの三角形を使う方法は無理です。また、分母にある $k!$, $(n-k)!$ は、値が大きすぎて直接値を計算することはできません。しかも、先ほど見たように、余りを計算してから商を計算する、ということはできないんですね。不便です。
ただ、この問題は、ある条件のもとではクリアできます。具体的な例で計算をしてみます。
商の剰余演算の具体例
先ほどの $10\div 2 \pmod 7$ について考えてみましょう。この割り算の部分をなんとかして計算できるようにしましょう。
ここで、天下り的ですが、 $8$ を掛けることを考えてみます。 $8\equiv 1 \pmod 7$ なので、 $7$ で割った余りを考える世界では、 $8$ を掛けることは $1$ を掛けることと同じであり、掛けたとしても余りには影響しません。しかも、これは2の倍数なので、次のようにうまく計算することができます。なお、 $\bmod 7$ で計算しています。
\begin{eqnarray}
& &
10\div 2 \\[5pt]
& \equiv &
10\div 2 \times 8 \\[5pt]
& \equiv &
10 \times 4 \\[5pt]
& \equiv &
3 \times 4 \\[5pt]
\end{eqnarray}
$\times 8$ は、 $\bmod 7$ の世界では $\times 1$ と同じ結果になるので、答えは変わりません。しかも、 $\div 2$ と相殺して、 $\times 4$ という積の形になります。こうなれば、余りの積を考えればよく、元の式は $5$ と合同だと計算できます。
つまり、 $a\div b \pmod p$ を計算するには、 $b^x\equiv 1 \pmod p$ となるような $x$ が見つかればうれしいことがわかります。 $b^x$ を掛けても答えは変わらないので、掛けてから計算していけばいいですね。商の部分が消えるので、計算が進んでいきます。
ではどうやってこんな数を求めるのか、という新しい問題が出てきます。これについては、数学の世界で良い性質が見つかっているので、それを利用することにします。「フェルマーの小定理」というものを使うのですが、これについては次の機会に見ることにしましょう。
おわりに
ここでは、商と剰余演算について、具体的な例を見てきました。商は和・差・積と同じようには計算できないこと、そして、工夫することで商の剰余演算もできる可能性があることを、具体的な例を通じてみてきました。フェルマーの小定理を使えば、さらに計算することができるので、次回で詳しく見ていくことにします。
