🏠 Home / 数学II / 式と証明 / 二項定理

【応用】二項定理と余り

ここでは、二項定理を使って、数の 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}今、下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乗を割った余り

例題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 、ということ)。文字はすべて整数で、 $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$ です。

このことから何が言えるかというと、 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 乗に適用して、いろいろな性質を見てきました。整数問題で使われることもあるので、覚えておきましょう。

関連するページ