問題
0以上の整数に対して，での下2桁を表すことにする．たとえば，，である．を2でも5でも割り切れない正の整数とする．
(1) ，が0以上の整数のとき，ならば，であることを示せ．
(2) となる0以上の整数が存在することを示せ．
出典：京都大学 1999年度 前期日程 第2次学力試験 文系 第3問
方針
は を100で割った余り、すなわち下2桁を表すと読む。 は2でも5でも割り切れないので と互いに素であり、 なら が従う。(2)は の100個の余りに対して を考えると、(1)により単射になり、有限集合なので全射になる。別法として、互いに素性から を満たす整数 を取り、 の下2桁を使って直接作ることもできる。
解答
(1)
は を100で割った余りを表している。したがって であることは、 と の下2桁が等しいこと、すなわち であることと同値である。
いま は2でも5でも割り切れないので、 と は互いに素である。よって から が従う。したがって と は100で割った余りが等しく、 である。
(2)
に対して を考える。もし で となったとすると、(1)より である。しかし では下2桁がその数自身なので、 は を意味する。これは に反する。
したがって、100個の数 は互いにすべて異なる。これらはいずれも のいずれかであり、個数も100個であるから、 をちょうど1回ずつ取る。よって、その中に1も現れる。すなわち、ある が存在して となる。
別解。 と100は互いに素なので、整数 が存在して を満たす。このとき である。 が負であっても、 と同じ下2桁をもつ0以上の整数 を取れば であるから となる。したがって を満たす0以上の整数 が存在する。