JMO予選 2018 第4問(整数の性質)

JMOというのは、「日本数学オリンピック」のことです。
毎年開催されていて、だいたい10問ちょっとの問題が出されます。
後半の問題は正直なところ自分も解けないような問題が並んでいたりするのですが、今回は序盤にある問題を1つ紹介します。

問題

$1111^{2018}$ を $11111$ で割った余りを求めよ。

解答

$11111=1111\cdot10+1$ であることと、「数字が大きければ小さいもので具体例を出す」の法則、この2つを使えば解ける問題です。

具体例を出してみる

2018乗はさすがに大きすぎるので、小さいものからやっていきます。

$1111^1=11111\cdot0+1111$

もう少しやってみます。

$\begin{eqnarray}1111^2&=&1111\cdot1111\\&=&1111\cdot1110+1111\\&=&111(1111\cdot10)+1111\\&=&\{111(1111\cdot10+1)-111\}+1111\\&=&111\cdot11111+1000\end{eqnarray}$

余りが1000と、とてもきれいな数字になりました。
もう少しやってみます。

$\begin{eqnarray}1111^3&=&1111^2\cdot1111\\&=&1111(111\cdot11111+1000)\\&=&11111C_1+1000\cdot1111\\&=&11111C_1+100(1111\cdot10)\\&=&11111C_1+100(1111\cdot10+1)-100\\&=&11111C_2-100\end{eqnarray}$

上の式途中で出てきた $C_1, C_2$ はどちらも整数です。
計算するのが面倒ですし、する必要はないので、文字でまとめてしまって余りだけに注目します。
余りが-100と、またきれいな数字になりました。先ほどよりも桁数が小さく、なんだかいい感じがします。
まだやってみましょう。

$\begin{eqnarray}1111^4&=&1111(11111C_2-100)\\&=&11111C_3-1111\cdot100\\&=&11111C_3-10(1111\cdot10)\\&=&11111C_3-10(1111\cdot10+1)+10\\&=&11111C_4+10\end{eqnarray}$

先ほどと同様、 $C_3, C_4$ は整数です。
まだいけそうなので計算します。

$\begin{eqnarray}1111^5&=&1111(11111C_4+10)\\&=&11111C_5+11110\\&=&11111C_5+(11111-1)\\&=&11111C_6-1\end{eqnarray}$

とてもきれいになりました。もちろん、 $C_5, C_6$ は整数です。ここまでくればほとんどゴール、2018乗を計算するだけです。

$\begin{eqnarray}1111^{2018}&=&(1111^5)^{403}\cdot1111^3\\&=&(11111C_6-1)^{403}(11111C_2-100)\\&=&(11111C_7-1)(11111C_2-100)\\&=&11111C_8+100\end{eqnarray}$
( $C_7, C_8$ は整数)