\(\require{cancel}\)
二項定理を利用して、整数問題を解いていきます。
(例題1)
(1)\(1997^{1997}\)を\(9\)で割ったときの余りを求めよ。
(2)整数\(101^{100}\)の下\(8\)桁を求めよ。
(解答)
(1)
よって、\((9×222-1)^{1997}\)を二項定理を用いて展開すると
ほとんどの項は\(9\)の倍数です。
\(1997=9×222-1=9N-1\) とすると
\(1997^{1997}=(9N-1)^{1997}\)
\(={}_{1997}\mathrm{C}_0(9N)^{1997}+{}_{1997}\mathrm{C}_1(9N)^{1996}(-1)+\)
\(・・・\)\(+{}_{1997}\mathrm{C}_{1996}(9N)(-1)^{1996}\)\(+{}_{1997}\mathrm{C}_{1997}(-1)^{1997}\)
\(=9L+(-1)\) (\(L\)は整数)
よって\(1997^{1997}\)は \(9\)の倍数から\(1\)を引いた数なので
余りは \(8\)
\(9\)で割った余りは\(0～8\)です。
なお、合同式を用いると
\(1997^{1997}≡(-1)^{1997}≡-1≡8\) (\(\mathrm{mod}\) \(9\))
と一瞬で求まります。
(2)
展開すると、ほとんど項は求める下\(8\)桁には関係ありません。
\(101^{100}=(10^2+1)^{100}\)
\(={}_{100}\mathrm{C}_0(10^2)^{100}\)\(+{}_{100}\mathrm{C}_1(10^2)^{99}+・・・\)
\(+{}_{100}\mathrm{C}_{96}(10^2)^{4}\)\(+{}_{100}\mathrm{C}_{97}(10^2)^{3}\)\(+{}_{100}\mathrm{C}_{98}(10^2)^{2}\)\(+{}_{100}\mathrm{C}_{99}(10^2)^{1}\)\(+{}_{100}\mathrm{C}_{100}\)
\(=M・10^8\)\(+{}_{100}\mathrm{C}_{97}(10^2)^{3}\)\(+{}_{100}\mathrm{C}_{98}(10^2)^{2}\)\(+{}_{100}\mathrm{C}_{99}(10^2)^{1}\)\(+{}_{100}\mathrm{C}_{100}\) (\(M\)は自然数)
\(M・10^8\)の部分は下\(8\)桁に関係ないので、下\(8\)桁を求めるには赤字の部分を計算すればよい。
\({}_{100}\mathrm{C}_{97}(10^2)^{3}\)\(+{}_{100}\mathrm{C}_{98}(10^2)^{2}\)\(+{}_{100}\mathrm{C}_{99}(10^2)^{1}\)\(+{}_{100}\mathrm{C}_{100}\)
\(=33・49・10^8+49500000\)\(+10000+1\)
\(=33・49・10^8+49510001\)
\(33・49・10^8\)は下\(8\)桁には関係ないので求める値は
\(49510001\)
(例題2)
(1)素数\(p\)と \(1≦r≦p-1\) なる整数\(r\)に対して、二項係数についての等式
\(r{}_p\mathrm{C}_r=p{}_{p-1}\mathrm{C}_{r-1}\)
を証明し、\({}_p\mathrm{C}_r\)は\(p\)の倍数であることを示せ。
(2)素数\(p\)に対して、\(2^p\)を\(p\)で割った余りを求めよ。
(解答)
(1)
\(r{}_p\mathrm{C}_r\)
\(=\cancel{r}\displaystyle\frac{p!}{\cancelto{(r-1)!}{r!}(p-r)!}\)
\(=\displaystyle\frac{p(p-1)!}{(r-1)!(p-r)!}\)
\(=p\displaystyle\frac{(p-1)!}{(r-1)!\{(p-1)-(r-1)\}!}\)
\(=p・{}_{p-1}\mathrm{C}_{r-1}\) (証明終)
また、\(r{}_p\mathrm{C}_r=p{}_{p-1}\mathrm{C}_{r-1}\)より
右辺は\(p\)の倍数で、\(p\)は素数であることと、\(1≦r≦p-1\) であることから
\(r\)と\(p\)は互いに素となる。
よって、\({}_p\mathrm{C}_r\)は\(p\)の倍数である。
\({}_p\mathrm{C}_r\)は\(p\)の倍数
であることは覚えてもよいと思います。
(2)
二項定理を使って
\(2^p=(1+1)^p\)
\(={}_p\mathrm{C}_0+{}_p\mathrm{C}_1+{}_p\mathrm{C}_2+・・・\)\(+{}_p\mathrm{C}_{p-1}\)\(+{}_p\mathrm{C}_p\)
\(=1+{}_p\mathrm{C}_1+{}_p\mathrm{C}_2+・・・\)\(+{}_p\mathrm{C}_{p-1}\)\(+1\)
\(=({}_p\mathrm{C}_1+{}_p\mathrm{C}_2+・・・\)\(+{}_p\mathrm{C}_{p-1})\)\(+2\)
(1)より \(({}_p\mathrm{C}_1+{}_p\mathrm{C}_2+・・・\)\(+{}_p\mathrm{C}_{p-1})\) の部分は\(p\)の倍数である。
よって、\(2^p\)を\(p\)で割った余りは、\(2\)を\(p\)で割った余りで
(i)\(p=2\)のときは、余りは\(0\)
(ii)\(p>2\)のときは、余りは\(2\)
以上になります。お疲れさまでした。
ここまで見て頂きありがとうございました。