Evolton
方針
(1) は平方数の下2桁だけの問題なので、 で割った余りを見る。平方数の での余りは に限られる。一方、 が偶数なら十の位 と一の位 は同じ偶奇であり、下2桁 の での余りを偶奇別に絞れる。(2)は下4桁を と置き、(1)で または まで絞る。 は平方数の での余りに反するので排除し、下4桁が であることを示す。
解答
(1)
任意の整数を で割った余りは のいずれかである。これらを2乗して で割った余りを調べると、平方数の余りは のいずれかに限られる。
平方数の下2桁を とする。 が偶数であるから、 と は同じ偶奇である。
まず がともに奇数であるとする。このとき は で割ると 余り、 は奇数であるから、 を で割った余りは のいずれかである。しかし、これらは上で求めた平方数の余りに含まれない。したがってこの場合は起こらない。
次に がともに偶数であるとする。このとき は で割り切れるので、 を で割った余りは のいずれかである。このうち平方数の余りになり得るのは だけである。したがって一の位 は である。
(2)
下4桁の数字がすべて同じであるとし、その数字を とする。すると下2桁は であり、十の位と一の位の和は で偶数である。よって(1)より である。
もし なら、下4桁は である。ところが であるから である。一方、整数を で割った余りを2乗して調べると、平方数の での余りは のいずれかであり、 にはならない。したがって は不可能である。
よって でなければならない。つまり下4桁は である。したがって、その平方数は で割り切れる。
条件・検算
平方剰余は実際に および に限られる。末尾4桁が0000なら、元の数の桁数にかかわらず10000の倍数である。
総評
難度6、計算量4。目安時間は18〜24分。末尾の数字だけを問う平方数の問題なので、実際の平方根を考えるより剰余で処理するのが自然である。(1)では が偶数という条件を「十の位と一の位が同じ偶奇」と読み替え、 での平方剰余と照合する。 ではなく を使うのは、十の位の偶奇と一の位を同時に扱いやすいためである。(2)は(1)をそのまま下2桁に適用し、残った を で排除する。よくある誤りは、下2桁が であり得ないことだけを示して下4桁 の確認を省くこと、または から直ちに の倍数であることを言い忘れることである。