トップ› 京都大学› 1999年› 文系第3問

京都大学 1999年文系第3問解説

方針・初手

「下2桁」という条件から、$100$ で割った余りに着目し、合同式 $\pmod{100}$ を用いて定式化するのが有効です。 $n$ が $2$ でも $5$ でも割り切れないということは、$100$（素因数分解すると $2^2 \cdot 5^2$）と互いに素であることを意味します。

(1) は合同式の性質（あるいは整数の除除の性質）から直接示せます。 (2) は (1) の結果を利用して「鳩の巣原理（部屋割り論法）」を用いるか、互除法に関連する「一次不定方程式の整数解の存在」を用いることで証明できます。

解法1

$C(x)$ は $x$ を $100$ で割った余りであるため、$C(x) = C(y)$ は合同式を用いて $x \equiv y \pmod{100}$ と表せる。以下、法を $100$ とする合同式で考える。

(1)

$n$ は $2$ でも $5$ でも割り切れない正の整数であり、$100 = 2^2 \cdot 5^2$ であるから、$n$ と $100$ は互いに素である。

$C(nx) = C(ny)$ とすると、定義より

$$ nx \equiv ny \pmod{100} $$

$$ n(x - y) \equiv 0 \pmod{100} $$

が成り立つ。これは $n(x - y)$ が $100$ の倍数であることを意味する。ここで、$n$ と $100$ は互いに素であるから、$x - y$ は $100$ の倍数でなければならない。すなわち、

$$ x \equiv y \pmod{100} $$

となる。よって、$x$ と $y$ の下2桁は等しくなり、$C(x) = C(y)$ であることが示された。

(2)

$0$ 以上の整数 $x$ のうち、$0 \leqq x \leqq 99$ を満たす $100$ 個の整数

$$ 0, 1, 2, \cdots, 99 $$

を考える。これらに $n$ を掛けた数の下2桁、すなわち

$$ C(0), C(n), C(2n), \cdots, C(99n) $$

の $100$ 個の値を考える。

ここで、(1) の対偶「$C(x) \neq C(y)$ ならば $C(nx) \neq C(ny)$」が成り立つ。選んだ $100$ 個の整数 $x$ はすべて異なるため、どの異なる2つを選んでも $C(x) \neq C(y)$ が満たされる。したがって、対応する $C(nx)$ の値もすべて互いに異なる。

$C(nx)$ がとりうる値は $0$ 以上 $99$ 以下の整数の $100$ 通りしかない。上記で考えた $100$ 個の値はすべて異なるため、これらの値の集合は $\{0, 1, 2, \cdots, 99\}$ と完全に一致する。したがって、この $100$ 個の値の中に、値が $1$ となるものがただ $1$ つ存在する。

ゆえに、$C(nx) = 1$ となる $0$ 以上の整数 $x$ が存在することが示された。

解法2

(1)

$C(nx) = C(ny)$ より、$nx$ と $ny$ は $100$ で割った余りが等しいので、$nx - ny$ は $100$ の倍数である。よって、ある整数 $k$ を用いて以下のように表せる。

$$ n(x - y) = 100k $$

ここで、$100$ の素因数は $2$ と $5$ のみであるが、仮定より $n$ は $2$ でも $5$ でも割り切れないため、$n$ と $100$ は互いに素である。したがって、$x - y$ が $100$ の倍数でなければならない。よって、ある整数 $m$ を用いて $x - y = 100m$ と表せるため、$x$ と $y$ は $100$ で割った余りが等しい。ゆえに、$C(x) = C(y)$ が成り立つ。

(2)

(1) の議論より、$n$ と $100$ は互いに素である。したがって、ベズーの等式（一次不定方程式の整数解の存在定理）より、

$$ nx + 100y = 1 $$

を満たす整数 $x, y$ が存在する。この式を以下のように変形する。

$$ nx = -100y + 1 $$

これにより、$nx$ を $100$ で割った余りが $1$ になる、すなわち $C(nx) = 1$ となる整数 $x$ の存在が言えるが、$x$ が負の整数である可能性がある。もし $x < 0$ であれば、さらに $x' = x + 100|x|$ という整数を考える。$|x| > 0$ であるから $x' \geqq 0$ である。このとき、

$$ nx' = n(x + 100|x|) = nx + 100n|x| = (-100y + 1) + 100n|x| = 100(n|x| - y) + 1 $$

となるため、$nx'$ を $100$ で割った余りも $1$ である。したがって、$C(nx') = 1$ となる $0$ 以上の整数 $x'$ が存在することが示された。

解説

整数分野における「合同式」と「互いに素な整数の性質」に関する標準的な証明問題です。

(1) は合同式の割り算の定理「$ac \equiv bc \pmod m$ かつ $\gcd(c, m) = 1 \implies a \equiv b \pmod m$」そのものです。この定理の証明の要領で論述すれば問題ありません。

(2) は解法1のように「余りの個数が法と一致すること（鳩の巣原理）」を利用するアプローチが鮮やかですが、整数の存在を示す手法として、解法2のように互除法を背景とする「一次不定方程式の整数解の存在定理（ベズーの等式）」を利用するアプローチも非常に重要です。問題文の「$0$ 以上の」という細かい条件に適合させるための微調整を忘れないようにしましょう。