【応用】二項定理と余り

ここでは、二項定理を使って、数の n 乗と余りの関係について見ていきます。

【広告】

n乗の下〇桁

例題1
$99^{99}$ の下4桁を答えなさい。

この問題を見て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}ここで、最後の2つの項以外の和は、10000の倍数であり、下4桁には影響しません。そのため、 $99^{99}$ の下4桁を考えるには、最後の2つの項だけを考えればよく、
\begin{eqnarray}
& &
{}_{99} \mathrm{ C }_{1} 100^{1}
-{}_{99} \mathrm{ C }_{0} 100^{0} \\
&=&
9900-1 \\
&=&
9899 \\
\end{eqnarray}となることがわかります。 $99^{99}$ の下2桁は $99$ になるんですね。

このように、数の n 乗に対して二項定理を使うことで、下〇桁や、ある数で割った余りが求められることがあります。

n乗を割った余り

例題2
$21^{20}$ を $400$ で割った余りを求めなさい。

これも、二項定理を使って
\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$ とします(ap で割った余りが r 、ということ)。文字はすべて整数としておきましょう。このとき、 $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$ です。

このことから何が言えるかというと、 ap で割った余りが r のとき、 $a^n$ を p で割った余りは、 $r^n$ を p で割った余りと等しくなる、ということです。

また、 a, bp で割った余りが等しいなら、 $a^n, b^n$ を p で割った余りも等しくなる、ということもわかります。

この結果は、整数問題を解くときに使われることがあります。

なお、冒頭の例題で「 $99^{99}$ の下2桁は $99$ だ」と書きましたが、 $99$ を $100$ で割った余りを $-1$ だと考えると、 $99^{99}$ を $100$ で割った余りは $(-1)^{99}=-1$ 、つまり、 $99$ になる、とすぐにわかります。

おわりに

ここでは、二項定理を数の n 乗に適用して、いろいろな性質を見てきました。整数問題で使われることもあるので、覚えておきましょう。