Evolton

京都大学 1999年度 前期日程 第2次学力試験文系数学 第3問

0以上の整数xに対して,C(x)でxの下2桁を表すことにする.
たとえば,C(12578)=78,C(6)=6である.
nを2でも5でも割り切れない正の整数とする.

(1) x,yが0以上の整数のとき,C(nx)=C(ny)ならば,C(x)=C(y)であることを示せ.

(2) C(nx)=1となる0以上の整数xが存在することを示せ.

難易度4/ 10計算量3/ 10目安10分

整数 合同式、存在証明、剰余分類

方針

C(x) は x を100で割った余り、すなわち下2桁を表すと読む。n は2でも5でも割り切れないので 100 と互いに素であり、100∣n(x−y) なら 100∣x−y が従う。(2)は 0,1,…,99 の100個の余りに対して x↦C(nx) を考えると、(1)により単射になり、有限集合なので全射になる。別法として、互いに素性から nu+100v=1 を満たす整数 u,v を取り、u の下2桁を使って直接作ることもできる。

解答

(1) C(x) は x を100で割った余りを表している。したがって C(nx)=C(ny) であることは、nx と ny の下2桁が等しいこと、すなわち 100∣n(x−y) であることと同値である。

いま n は2でも5でも割り切れないので、n と 100=22⋅52 は互いに素である。よって 100∣n(x−y) から 100∣x−y が従う。したがって x と y は100で割った余りが等しく、C(x)=C(y) である。

(2) x=0,1,2,…,99 に対して x⟼C(nx) を考える。もし 0≦x<y≦99 で C(nx)=C(ny) となったとすると、(1)より C(x)=C(y) である。しかし 0≦x,y≦99 では下2桁がその数自身なので、C(x)=C(y) は x=y を意味する。これは x<y に反する。

したがって、100個の数 C(n⋅0), C(n⋅1), …, C(n⋅99) は互いにすべて異なる。これらはいずれも 0,1,2,…,99 のいずれかであり、個数も100個であるから、0,1,2,…,99 をちょうど1回ずつ取る。よって、その中に1も現れる。すなわち、ある 0≦x≦99 が存在して C(nx)=1 となる。

別解

解法2

方針

gcd⁡(n,100)=1 から Bézout の等式 rn+100s=1 を用意する。(1)では合同式へ逆数 r を掛け、(2)では同じ r の100を法とする代表元をそのまま構成する。

解答

(1)
gcd⁡(n,100)=1 なので、ある整数 r,s が存在してrn+100s=1を満たす。C(nx)=C(ny) ならnx≡ny(mod100).両辺へ r を掛けると rn≡1(mod100) だからx≡y(mod100).従って C(x)=C(y) である。

(2)
上の整数 r と同じ100を法とする剰余をもつx∈{0,1,…,99}を取る。このときnx≡nr≡1(mod100)であるから C(nx)=1 である。これは条件を満たす非負整数 x の具体的な構成になっている。

総評

難度4、計算量3。下2桁を100で割った余りとして扱えるかを見る整数問題である。想定時間は10分程度。(1)では n が2でも5でも割り切れないことを、n と100が互いに素であることに言い換えるのが中心である。(2)は100個の余りへの写像が単射なら全射になる、という有限集合の考え方を使う。別解のように互除法型の整数 u,v を使うと存在が直接見えるが、いずれの場合も「下2桁が等しい」と「100で割った余りが等しい」を明確に結びつけたい。 主解法と第2解法を別々に再計算し、条件範囲、端点、等号成立条件まで照合した。

Evolton Pro

月額
2,480円(税込)
保存・印刷
公開過去問PDF・オーダーメイド問題集PDF
プランを確認・登録

冊子PDFで見る京大の整数の問題で問題集を作る

出典: 京都大学 1999年度 前期 文系 第3問(大学公式の問題PDF)。問題文はHTML表示のために再入力・数式組版しています。