東大実戦は駿台予備校が年2回実施している東大受験生向けの模擬試験です。今回はシンプルな整数問題を取り上げてみます。
《問題》
$6^{2017}$ を $100$ で割った余りを求めよ。
（2017年第1回東大実戦 文系第1問）
《考え方》
いわゆる一行問題ですね！ 試験場で見たら肝を冷やすタイプの問題ですが、本問は東大レベルの受験生相手に出題される整数問題としては非常に簡単な部類です。
余りを求める計算では大きく分けて
① 合同式（$\text{mod}$）の利用
② 二項定理の利用
という２つの解法があります。「無理やり割り算を実行する」という原始的な方法もあり得ますが、$6^{2017}$ のように大きな数が相手では現実的なアプローチとは言えません。
どちらの方法でも解ける…と言いたいところですが、$6$ という数字が結構厄介で、今回は二項定理を利用する方針はやや不向きです。というのも、二項定理を利用するのであれば $6^n=(10-4)^n$ などと変形したくなりますが、こうしてしまうとその後の処理が上手くいかないのです。
とはいえ、二項定理によるアプローチも不可能という訳ではありません。$100$が $2^2 \cdot 5^2$ と素因数分解できることから「$25$で割った余りと$4$で割った余りを後で上手く合わせる」という方針で余りを絞り込めば良さそうだと気が付くところからがスタートです。この大枠の考え方が頭にあればどの方法でも解答することができます。
しかし実は、余りの周期性に注目すればもっと簡単に解答可能だったりします･･･。
解答例①
小さい自然数$n$について$6^n$の下２桁を調べると、$$\small 06 \to 36 \to 16 \to 96 \to 76 \to 56 \to \color{red}{\underline{36}}$$となり周期5で繰り返すので、$n$を$5$で割った余りが$2$のとき、$6^n$の下２桁は$36$となる。$2017$は$5$で割った余りが$2$となる自然数だから、$6^{2017}$ を $100$ で割った余りは$$\color{red}{36} \quad \cdots (\text{答}) $$である。
解答例②
求める余りを$R$とすると、適当な正の整数$N$を用いて$$6^{2017}=100N+R$$と置ける。ただし$R$は整数で $0 \leqq R <100$ を満たす。
ここで$6^{2017}$は$4$の倍数であり、$100$も$4$の倍数であるから、$R$も$4$の倍数である。･･･①
次に$6^n$（$n$は正の整数）を$25$で割った余りを調べると、$$6^2 \equiv 11 \pmod{25}$$ $$6^3 \equiv 16 \pmod{25}$$ $$6^4 \equiv 21 \pmod{25}$$ $$6^5 \equiv 1 \pmod{25}$$となる。よって$$6^{2017}=6^{2015}\cdot 6^2 \equiv 11 \pmod{25}$$を得るので、$6^{2017}$を$25$で割った余り、すなわち$R$を$25$で割った余りは$11$となる。･･･②
②より、$R$としてあり得るのは$$11,\,36,\,61,\,86$$の４つであるが、このうち$4$の倍数であるものは$36$に限るので、①より $R=36$ と求められる。
よって、$6^{2017}$ を $100$ で割った余りは$$\color{red}{36} \quad \cdots (\text{答}) $$である。
解答例③
二項定理を用いると$$\begin{align}
6^n &= (5+1)^n \\
&=\sum_{k=0}^{n} {}_{n}\mathrm{C}_{k} 5^{k} \\
&={ }_{n} \mathrm{C}_{0} \cdot 5^{0}+{ }_{n} \mathrm{C}_{1} \cdot 5^{1}+25 N \\
&=1+5 n+25 N \\
\end{align}$$となる。ここで$N$は整数であり、$25$の倍数となる項はすべて$25N$に含まれている。
いま、$n=2017$ とすると整数$N^{\prime}$を用いて$$\begin{align}
6^{2017} &= 1+10085+25N \\
&=11+25N^{\prime} \\
\end{align}$$と変形できる。よって$6^{2017}$を$25$で割った余りは$11$である。
よって、$6^{2017}$ を $100$ で割った余りとしてあり得るのは$$11,\,36,\,61,\,86$$の４つに限られるが、このうち$4$の倍数であるものは$36$に限られる。したがって、求める余りは$$\color{red}{36} \quad \cdots (\text{答}) $$である。
（コメント）
解答を３パターン示しましたが、見るからに簡単なのは解答例①の方針ですね。解答例②はいかにも「合同式っぽい」解法ですが、やや回りくどい感があります。解答例③の方針も「$25$で割った余りと$4$で割った余りを求めて上手く組み合わせればよい」という視点を持っていないとスムーズに解答するのは難しいかもしれません（解けることには解けるのですが）。
今回は余りの周期性が早々に判明したので解答例①のやり方でも苦労しませんでしたが、常に上手くいくとは限りません。解答例②や③の方法も必ず理解しておきましょう。巨大な数を合成数で割った余りを求める問題は創作整数問題#1や創作整数問題#53で扱っています。どちらも本問より歯応えのある問題なので是非解いてみて下さい！
ところで、東大･京大向けの模試は、大学別に実施されるいわゆる「冠模試」の中でも予備校各社が威信を懸けて作題しており、問題のレベルは例年安定して高水準です。難関大を目指すのであれば受験しておいて損は無いと思います。