東大07文系第3問を改めてみると - 日々の暮らしと時々の数学

今日本屋に行ったら、
『東大の入試問題で「数学的センス」が身につく』とかいう
胡散臭い感じのタイトルの本があったから手に取ってみた。

ぱっと開いたときに目に入った問題が
07文系第３問だった。
問題の細かいところははしょっている。

◆問題◆
自然数 ${m}$ に対し、 ${5m^4}$ の下2桁として出てくるもの全部列挙せよ。

まず、mod 100を考えれば十分であることはだれしもが
気付くことだろう。

解答を見てみると、
「m=10a+b（aは非負整数、b=0,1,...,9）とおく」
と書いてあった。
確かにmod 100じゃなくていいのか！と高校生の時分に
感じた記憶がある。

今日、その本を開いて、その当時より
髪の毛一本分数学が深く見えるようになった
目を通して見ると、初等整数論の基礎をうまく
利用することで非常に段階的に解決することができた。

＜解答の概略＞
${5m^4}$ の下2桁は、 ${m^4}$ のmod 20の値にのみ依存する
ことは容易にわかる。

さて、mod 20は中国式剰余の定理からmod 4とmod 5の
値により決定する。

いま、フェルマーの小定理から、
${m \neq 0(\mod 5)}$ ならば ${m^4 = 1(\mod 5)}$
である。

また、mod 4の平方剰余の経験があれば、
${m = 0,2 (\mod 4)}$ ならば ${m^4 = 0 (\mod 4)}$
${m = 1,3 (\mod 4)}$ ならば ${m^4 = 1 (\mod 4)}$
であると知っているだろう。
要は前者が偶数、後者が奇数のときである。

だから、すでに答えは4種類だとこの時点で
わかってしまう。

このとき、l=0,1(mod 4)とl=0,1(mod 5)の
組からlの(mod 20)を決定しよう。

(mod 20だから総当たりでよいが、
きちんとアルゴリズム的に求めてみよう）

中国式剰余定理の証明を思い出そう。
${\mathbb{Z}/20\mathbb{Z}\to\mathbb{Z}/4\mathbb{Z}\times\mathbb{Z}/5\mathbb{Z}}$
は単純に大氷原・・・じゃなくて代表元を
そのまま送ればよかった。

いま問題になっているのはその逆写像。
これは、 ${k\mapsto (0,1),l\mapsto (1,0)}$ となるkとlを
互除法から得るのだった。

互除法を考えると、
5+(-4)=1
という見るからに明らかな結果が出てくるので、
(5c+4d=1で、5cと4dを採用するのだった）
${ \mathbb{Z}/4\mathbb{Z}\times\mathbb{Z}/5\mathbb{Z}\to\mathbb{Z}/20\mathbb{Z}}$ は
${(a,b)\longmapsto 5a-4b}$ により生成できる。

だから、
${m}$ が偶数で5の倍数なら ${m^4 = 0(\mod 20)}$
${m}$ が奇数で5の倍数なら ${m^4 = 5(\mod 20)}$
${m}$ が偶数で5の倍数でないなら ${m^4 = -4 = 16(\mod 20)}$
${m}$ が奇数で5の倍数でないなら ${m^4 = 5-4 =1(\mod 20)}$
と計算できる。

∴
${m}$ が偶数で5の倍数なら ${5m^4 = 0(\mod 100)}$
${m}$ が奇数で5の倍数なら ${5m^4 = 25(\mod 100)}$
${m}$ が偶数で5の倍数でないなら ${5m^4 = 80(\mod 100)}$
${m}$ が奇数で5の倍数でないなら ${m^4 = 5(\mod 100)}$
が得られる。