IMO2011 5番

今更解けた。悲しい

問題

f: Z → Z⁺ がある。∀n,m f(m-n) | f(n)-f(m) であるとき、f(m)<=f(n) ⇒ f(m) | f(n) を示せ。

解答

k, n を整数とすると、与式の(m,n)に((k-1)n, kn) を代入して、f((k-1)n) ≡ f(kn) mod f(n) を得る。これを用いると、0 ≡ f(kn) mod f(n) を得る。ゆえに、f(kn) は f(n) の倍数である。さらに、f(0) は f(n) の倍数であることも従う。
すると、与式の(m, n) に (0, m) と (0, -m) を代入して比較することで、f(m) = f(-m) を得る。
すると、f(k) は f(1) の倍数である。よって、f(1) = 1 としても一般性を失わない( g(x) = f(x) / f(1) とすると、f(x) が題意を満たすことと g(x) が題意を満たすことは同値である)。

∀x f(x) = 1 のときは明らかに題意を満たすので、そうではないと仮定する。p を f(p) > 1 なる最小の正整数とする。ここで、x が p の倍数でないとき、f(x) = 1 を示す。
背理法によって示す。q を f(q) > 1 かつ、p で割り切れないような最小の正整数とする。すると、題意より
f(p) ≡ f(p-q) (mod f(q) ) …①
f(q) ≡ f(q-p) (mod f(p) ) …②
が成り立つ。ここで、p < q であるから、0 < q-p < q である。q が p で割り切れないので、q-p は p で割り切れない。ゆえに、q のとり方に注意すると、f(q-p) = 1 である。ゆえに、f(p-q) = f(q-p) = 1 である。
さらに、f(p) > 1, f(q) > 1 より、①と②から、それぞれ f(p) > f(q), f(q) > f(p) を得る。これは矛盾。ゆえにそのような q は存在しない。

以上より、x, y のうち少なくとも片方が p の倍数ではないときについては題意が成り立つことが示された。両方が p の倍数のときについては、g(x) = f(px) / f(p) なる g(x) を考えることによって、より小さい (x, y) の組についての議論に帰着できるから、帰納的に示される。よって示された。Q.E.D.