問題74：EMC 2017

#74

整数論

★★★★☆

EMC 2017 Senior 問4

整数係数多項式 $P$ であって, $P (0) \neq 0$ かつ任意の非負整数 $n, m$ に対して $P^{n} (m) P^{m} (n)$ が平方数となるものをすべて求めよ. ここで, $P^{k}$ で $P$ の $k$ 回合成を表すものとする.

解いてみた

平山：解は？ $n + 1$ くらい？
宿田：たぶん？
平山： $m P^{m} (0)$ が平方数くらいから始めるかな
馬杉： $0$ いいんだ
平山：割と本質っぽい、 $P^{m} (0) = c_{m}$ とおきますか
馬杉： $c_{平方数}$ は平方数
平山：定数項は平方数か
兒玉： $P^{m} (n + 1) P^{P (m)} (n)$ は平方数
(※編注：実際には $P (m)$ 非負を要請する必要あり)
馬杉： $P^{m} (n)$ の素因数ってどんな感じ？オーダーとか知りたい
平山：思ったより情報が得られんなあ
兒玉：定数項が $1$ なの言えそう
平石：兒玉さんのやつ $m = 0$ 入れたら $(n + 1) P^{P (0)} (n)$ が平方数
兒玉：これめっちゃ重要じゃね？
馬杉：頑張ったらなんかすでに出来そう
平山：定数項が非負だとちょっと微妙じゃない？
兒玉：平方数なのでOK
平山：は？自分で言ったのに忘れてた
馬杉： $P^{P (0)}$ を $Q$ とおくと $Q (p - 1)$ は $p$ の倍数
馬杉：よって $Q (- 1)$ は任意の素数の倍数で、 $0$
平石： $- 1$ 入れちゃっていいの
平山：多項式一般の性質として
馬杉：というか $Q (n) = n + 1$ 言えばいいわけじゃん
平山：あー多項式だとそんなこともできるのか
馬杉：っていうか $1$ ずらすとか？
平山： $Q$ だけじゃ情報減ってて全然無理なんだよね
兒玉：方針的に微妙な気がする
平山：定数項とりあえず決めないとダメかな..
宿田： $(c_{m} + n) (c_{n} + m)$ が平方数
馬杉：有用そう、どうやるの
宿田： $(m, n) = (c_{m}, c_{n})$ を代表
馬杉：なるほどね
馬杉： $n$ の素数 $p$ でのオーダーがべらぼうに大きければ
馬杉： $P (n)$ と定数項のオーダーが一致するねっていう
平山：でも合成とオーダーって相性微妙じゃない？
兒玉：宿田の式で定数項を $a^{2}$ とすると、 $c_{n}$ は $a^{2}$ の倍数で
兒玉： $m$ に $a$ の素因数、 $n$ に $1$ 代入して $a = 1$
馬杉：おっ
宿田：おっ
平山：上の $Q$ が $P$ 自身になったのか
馬杉： $m c_{m}$ 平方数なんだっけ
平山： $(m + 1) (c_{m} + 1)$ も平方数で、だいぶヤバそう
平石：その二つだけなら $(1, 49)$ とか反例あるけど
平山：ダメじゃん！
宿田： $(n + 1) P (n)$ が平方数なんだよな
(※※※ここから本質的に変わらない式変形が続く※※※)
兒玉：宿田の式が本質だと思ってる
馬杉： $(c_{m} + n) (c_{n} + m)$ は平方数です、 ${c_{n}}$ は？
馬杉：なんかいけそうじゃーん
兒玉：これIMOで出なかった？
宿田：あっwwww
平石：3番級とかだったような
平山：あったわwwww
兒玉：2010年の3番ですね
平山： $0$ 入る可能性あるけど流石にごまかせるやろ
宿田：絶対オーバーキルで草
平山：本質的な作業、宿田の代入一つだけ…
馬杉：多項式すらいらんねやん、草
平山：流石にオーバーキルせず解き切るか…
宿田：もし $m o d p$ で $c_{n} \equiv c_{n + 1}$ ならずっと一定
宿田：これ $P (x) - x$ とか見てみると良さそうじゃないですか
馬杉：確かに？
平山： $c_{p}$ が $p$ の倍数だから $m o d p$ の観察は本質っぽいけど
馬杉：たしかに
平山：というか $c_{0}, \dots, c_{p - 1}$ って $m o d p$ で重複ないのか
平石：それいつの間に言った
平山：周期を考えればそれはそう
平山：ということは $n, P (n), \dots, P^{p - 1} (n)$ も完全剰余系か
平山： $P (n) - n$ が定数じゃなければ適当に素因数取って終わりじゃん
兒玉：ああなるほど
平石：あーそうか
平山：答案にしたら短くて虚無感の募るタイプですな～

解説・感想

解答を書くと元の条件はほとんど使っておらず, 多項式の性質で多くの議論ができることがわかる.

解答

$c_{i} = P^{i} (0)$ とおく. $p$ を素数とすると, $m = p, n = 0$ とした代入より $p c_{p}$ は平方数であり, $c_{p}$ は $p$ の倍数である. また, $l$ を正の整数とすると $c_{i} \equiv c_{j} (\mod p)$ ならば $c_{i + l} = P^{l} (c_{i}) \equiv P^{l} (c_{j}) = c_{j + l} (\mod p)$ である. 次の補題を示す.

補題.

任意の整数 $n$ について, $P (n) - n$ の任意の素因数は $P (0)$ の素因数である.

証明.

$q$ を $P (0)$ を割り切らない素数とする. 以下合同式は $mod q$ で考える. $c_{i}$ が $q$ の倍数になる最小の正の整数 $i$ を $k$ とすると, 帰納的に考えて, $c_{i}$ が $q$ の倍数であることは $i$ が $k$ の倍数であることと同値であり, $c_{q}$ は $q$ の倍数であることとあわせて $k$ は $q$ の約数である. $P (0) = c_{1}$ は $q$ の倍数でないことから, $k \neq 1$ であり, $k = q$ である. よって $c_{1}, c_{2}, \dots, c_{q - 1}$ はすべて $q$ の倍数でない. また, $1 \leq i < j \leq q - 1$ かつ $c_{i} \equiv c_{j}$ をみたす整数の組 $(i, j)$ が存在すると仮定すると, 帰納的に $n \geq i$ ならば $c_{n} ≢ 0$ が成り立ち, $c_{q}$ が $q$ の倍数であることに矛盾する. 以上より $c_{0}, c_{1}, \dots, c_{q - 1}$ を $q$ で割った余りはすべて異なり, $0, 1, \dots, q - 1$ のすべてが現れる. よって $n \equiv c_{i}$ をみたす非負整数 $0 \leq i \leq q - 1$ が存在し, $P (n) - n \equiv P (c_{i}) - c_{i} = c_{i + 1} - c_{i} ≢ 0$ である. 以上より示された.

整数係数多項式 $R$ を用いて $P (n) - n = P (0) + n R (n)$ とおくと, 補題より, 任意の $3$ 以上の整数 $a$ について, $P (0) + a P (0)^{2} R (a P (0)^{2}) = P (0) (1 + a P (0) R (a P (0)^{2})$ の任意の素因数は $P (0)$ の素因数である. $1 + a P (0) R (a P (0)^{2})$ は $P (0)$ と互いに素であることから, $| 1 + a P (0) R (a P (0)^{2}) | = 1$ であり, $| a P (0) | > 2$ とあわせて $R (a P (0)^{2}) = 0$ が必要である. ここで, $P (0) \neq 0$ より, $R$ は無限個の零点をもち, $R = 0$ である.

よって $P (n) = n + P (0)$ が必要である. $b = P (0)$ とおくと, 与式で $n = 1, m = 0$ とすることで $b$ は平方数である. また, $n = 4, m = 1$ とすることで $4 b^{2} + 17 b + 4$ は平方数であり, $(2 b + 2)^{2} < 4 b^{2} + 17 b + 4 < (2 b + 5)^{2}$ より, $4 b^{2} + 17 b + 4 = (2 b + 3)^{2}$ または $4 b^{2} + 17 b + 4 = (2 b + 4)^{2}$ が成り立ち, $b = 1$ または $b = 12$ である. $b$ は平方数であったから $b = 1$ が必要である. 逆に $P (n) = n + 1$ が条件をみたすことは容易にわかるため, 求める $P$ は $P (n) = n + 1$ のみである.