第5問

f

を整数全体の集合から正の整数全体の集合への関数とする。任意の二つの整数

m

と

n

に対し、差

f(m)-f(n)

が

f(m-n)

で割り切れると仮定する。

f(m)\le f(n)

を満たすすべての整数

m

と

n

に対して、

f(n)

が

f(m)

で割り切れることを証明せよ。

ステップ 5/5: f(m), f(n), f(n-m) に補題を適用する

前のステップ次のステップ

ざっくり言うと

三つの値のうちどれが最大になっても、補題は常に小さい二つを同一視し、仮定より f(m) はその小さい二つの一方なので、あらゆる並び方において f(n) を割り切ることになる。

f(m)\mid f(n)

詳しい解説

$f(m)\le f(n)$ とする。 $x=n,y=m$ として手順3を三つ組 $a'=f(n),b'=f(m),c'=f(n-m)$ に適用すると、手順3の三つの関係を満たすので（大きさで並べ替えれば）手順4の補題が適用できる。 $f(m)\le f(n)$ なので $f(m)$ は三つのうち最大になることは決してなく、常に補題が等しいと同定する二つの値の一方である。補題はその共通の値が最大の値を割り切ると述べる。 $f(n)$ が最大なら、補題から直ちに $f(m)\mid f(n)$ が得られる。 $f(n-m)$ が最大の場合、補題は $f(m)$ が $f(n),f(n-m)$ のうち最大でない方に等しいことを強制し、この場合 $f(m)\le f(n)\le f(n-m)$ なので $f(m)=f(n)$ が強制され、これもまた $f(m)\mid f(n)$ を与える。いずれにせよ $f(m)\mid f(n)$ である。