【応用】二項定理と余り
ここでは、二項定理を使って、数の n 乗と余りの関係について見ていきます。
n乗の下〇桁
この問題を見て99乗を計算する人はいないと思いますが、99乗を計算せずにどうやってこれを求めるんでしょうか。
実は、100が出てくるように二項定理を使うと、いいことが起こります。
\begin{eqnarray}
99^{99}
&=&
(100-1)^{99} \\[5pt]
&=&
{}_{99} \mathrm{ C }_{99} 100^{99}
-{}_{99} \mathrm{ C }_{98} 100^{98}
+\cdots \\[5pt]
& &
\cdots
+(-1)^{99-k} {}_{99} \mathrm{ C }_{k} 100^{k}
+\cdots \\[5pt]
& &
\cdots
-{}_{99} \mathrm{ C }_{2} 100^{2}
+{}_{99} \mathrm{ C }_{1} 100^{1}
-{}_{99} \mathrm{ C }_{0} 100^{0}
\end{eqnarray}今、下4桁を考えたいので、まずは $100^0$ と $100^1$ を含んでいる最後の2項に注目しましょう。この部分は、次のように計算できます。
\begin{eqnarray}
& &
{}_{99} \mathrm{ C }_{1} 100^{1}
-{}_{99} \mathrm{ C }_{0} 100^{0} \\
&=&
9900-1 \\
&=&
9899 \\
\end{eqnarray}残りの各項は、 $100^2$ で割り切れます。また、すべて足すと $99^{99}-9899$ であり、正の整数になることがわかるので、 $99^{99}$ は、「 $9899+10000\times$ (正の整数)」と変形できます。よって、 $99^{99}$ の下4桁は $9899$ となります。
$99$ を $100-1$ と変形し、二項定理を使うことで、 $100^k$ がたくさん出てきます。これをうまく使って、下4桁が求められました。この例題からわかることですが、 $99^{99}$ の下2桁が $99$ になるのはおもしろいですね。
このように、数の n 乗に対して二項定理を使うことで、下〇桁や、ある数で割った余りが求められることがあります。
n乗を割った余り
これも、二項定理を使って
\begin{eqnarray}
21^{20}
&=&
(20+1)^{20} \\[5pt]
&=&
{}_{20} \mathrm{ C }_{20} 20^{20}
+{}_{20} \mathrm{ C }_{19} 20^{19}
+\cdots \\[5pt]
& & \cdots
+{}_{20} \mathrm{ C }_{k} 20^{k}
+\cdots \\[5pt]
& & \cdots
+{}_{20} \mathrm{ C }_{2} 20^{2}
+{}_{20} \mathrm{ C }_{1} 20^{1}
+{}_{20} \mathrm{ C }_{0} 20^{0}
\end{eqnarray}と変形すると、最後の2項以外は $400$ で割り切れることがわかります。最後の2項の和は\[ 20 \times 20 +1 \]なので、 $400$ で割った余りは $1$ であることがわかります。
n乗の余り
最後に、 n 乗の余りに関する、ある性質を見ておきます。
$a=pq+r$ とします（a を p で割った余りが r 、ということ）。文字はすべて整数で、 $p,q$ は0ではないとしておきましょう。このとき、 $a^n$ は次のようになります（n は自然数）。
\begin{eqnarray}
a^n
&=&
(pq+r)^n \\
&=&
{}_{n} \mathrm{ C }_{n} (pq)^{n}
+{}_{n} \mathrm{ C }_{n-1} (pq)^{n-1}\cdot r
+\cdots \\[5pt]
& & \cdots
+{}_{n} \mathrm{ C }_{k} (pq)^{k}\cdot r^{n-k}
+\cdots \\[5pt]
& & \cdots
+{}_{n} \mathrm{ C }_{1} (pq)^{1}\cdot r^{n-1}
+{}_{n} \mathrm{ C }_{0} (pq)^{0}\cdot r^{n}
\end{eqnarray}ここで、最後の項以外は p の倍数になることがわかります。また、最後の項は $r^n$ です。
このことから何が言えるかというと、 a を p で割った余りが r のとき、 $a^n$ を p で割った余りは、 $r^n$ を p で割った余りと等しくなる、ということです。
また、 a, b を p で割った余りが等しいなら、 $a^n, b^n$ を p で割った余りも等しくなる、ということもわかります。
この結果は、整数問題を解くときに使われることがあります。
なお、冒頭の例題で「 $99^{99}$ の下2桁は $99$ だ」と書きましたが、 $99$ を $100$ で割った余りを $-1$ だと考えると、 $99^{99}$ を $100$ で割った余りは $(-1)^{99}=-1$ 、つまり、 $99$ になる、とすぐにわかります。
おわりに
ここでは、二項定理を数の n 乗に適用して、いろいろな性質を見てきました。整数問題で使われることもあるので、覚えておきましょう。
