二項定理の応用

例題

\((1+x)^n\) の展開式を利用して、3117を900で割ったときの余りを求めなさい。

解答

まずは二項定理の復習

二項定理

\(n\) が正の整数のとき
\(\displaystyle (a+b)^n=\sum_{k=0}^{n} {}_n C_{k} a^{n-k}b^k\)

\(31=1+30\) として二項定理を適用していきます。
\(31^{17}=(1+31)^{17}\)
\(=\displaystyle \sum _{k=0} ^{17} {}_{17} C_{k} 30^k\)
\(=\displaystyle \sum _{k=0} ^{17} {}_{17}C_{k} 900\cdot 30^{k-2}\)
\(=\displaystyle 900 \sum _{k=0} ^{17} {}_{17}C_{k} 30^{k-2}\)
\(=900(_{17}C_{0}30^{-2} + _{17}C_{1}30^{-1} + _{17}C_{2}30^0 + _{17}C_{3}30^1 + \cdots + _{17}C_{17}30^{15})\cdots (a)\)
ここで
\(_{17}C_{2}30^0 + _{17}C_{3}30^1 + \cdots + _{17}C_{17}30^{15}\)
は整数となるので \(N\) とおくと
\((a)=1+510+900N\)
\(=900N+511\)
よって、余りは511・・・(答)

別解

合同式を利用する。
\(31^2 \equiv 961 \equiv 61 \pmod {900}\)
\(31^4 \equiv 61^2 \equiv 3721 \equiv 121 \pmod {900}\)
\(31^8 \equiv 121 \equiv 14641 \equiv 241 \pmod {900}\)
\(31^{16} \equiv 241^2 \equiv 58081 \equiv 481 \pmod {900}\)
\(31^{17} \equiv 31^{16}\cdot 31 \equiv 481\cdot 31 \equiv 14911 \equiv 511 \pmod {900}\)
よって、余りは511・・・(答)