整数係数多項式とmodp

903

今回は整数係数多項式を考える際に良い感じな素数を探したいみたいな話をします.

Ibero America 2019, 2020第1回通信添削P4

$a_{1}, a_{2}, . . ., a_{2020}$ を正の整数とする. $P (x)$ を整数係数多項式であって, 任意の正の整数 $n$ について $P (n)$ が $\sum_{i = 1}^{2020} a_{i}^{n}$ の約数となるようなものとする. このとき $P (n)$ は定数関数である事を示せ.

純粋な大小比較では上手く行かなさそうなので合同式関係の議論が必要そうである. $p | P (n)$ なる素数 $p$ を取ってみよう. すると $p | \sum_{i = 1}^{2020} a_{i}^{n}$ だがこれだけでは情報が少なすぎる. この $p$ についてもう少しいい話が無いかと探ると $p | P (n + p)$ である事に気付くだろう. よって $p | \sum_{i = 1}^{2020} a_{i}^{n + p}$ . フェルマーの小定理を使えば $p | \sum_{i = 1}^{2020} a_{i}^{n + 1}$ . これを繰り返せば $p | \sum_{i = 1}^{2020} a_{i}^{k (p - 1) + 1}$ , つまり $p | \sum_{i = 1}^{2020} a_{i}$ と出来る. ( $p, a_{i}$ が互いに素である事を仮定していないのでその関係で式が微妙に汚い)ここで $p$ が無限に大きく取れればこれは矛盾である.

解答
$P$ は定数でない多項式であると仮定して矛盾を導く. まず, 一般に次の定理が知られている. これは初等的に示せる上, たまに使うため定理の形で記しておく.

$X$ を整数の部分集合とするとき, $P (X)$ を $X$ のある元を割りきる素数全体の集合とする.

シューアの定理

任意の定数でない整数係数多項式 $P (x)$ に対し $P (P (N))$ は無限集合である.

ここで $P (N) = {P (n) | n \in N}$ である.

素数の無限性の証明のアナロジーである

$P (P (N))$ が有限集合であると仮定し, その総積を $S$ とする. $P$ は非有界より $S > 1$ である.
まず $P$ は定数でないので $| P (k) | > 0$ なる $k \in N$ が存在する. $P (k + S^{| P (k) |} \cdot n) \equiv P (k) (\mod S^{| P (k) |})$ . ここで $P (k + S^{| P (k) |} \cdot n)$ の素因数 $p$ は $S$ を割り切り, $v_{p} (P (k + S^{| P (k) |} \cdot n)) = v_{p} (P (k) + m \cdot S^{| P (k) |}) = v_{p} (P (k))$ なので $| P (k + S^{| P (k) |} \cdot n) | \leq | P (k) |$ (実際には等号)これは $n$ を動かすことを考えると $P$ の非有界性に矛盾. よって定理は示された.

定理により $p | P (n)$ かつ $p > max {2020, a_{1}, . . ., a_{2020}}$ を満たす正整数 $n$ と素数 $p$ が存在する. $n$ 以上の最小の $p - 1$ の倍数を $m$ とする. $p | P (n + (m - n) p)$ だから
このとき $0 \equiv \sum_{i = 1}^{2020} a_{i}^{n + (m - n) p} \equiv \sum_{i = 1}^{2020} a_{i}^{m} \equiv \sum_{i = 1}^{2020} 1 = 2020 (\mod p)$ . これは $p > 2020$ に矛盾. よって題意は示された.

多項式 $mod p$ は周期 $p$ で, 指数関数 $mod p$ は周期 $p - 1$ で変化することはしばしば便利なので多項式と指数関数が絡まる問題においては注意しておこう.(不定方程式とかで無駄な $mod$ を取ることを回避するときとかにも有効)
もう1問見てみる.

ELMO2022P2

以下の条件を満たす最高次係数が $1$ の整数係数多項式 $P$ を全て求めよ:

正整数 $a, m$ が存在して任意の $n \equiv a (\mod m)$ なる正整数 $n$ に対して $2022 \cdot \frac{(n + 1)^{n + 1} - n^{n}}{P (n)}$ が整数となる.

大量の $n$ に対して $2022 \cdot \frac{(n + 1)^{n + 1} - n^{n}}{P (n)}$ が整数にならないと行けないのでこれも $P (n)$ の素因数について考えたい. $p | P (n)$ としてみる. $p$ は十分大きいと出来るので $2022$ は無視出来る. まず, $(n + 1)^{n + 1} \equiv n^{n} (\mod p)$ . 前問と同様な事が出来ないかと考え, $p | P (n + m k p)$ を利用すると, $(n + m k p + 1)^{n + m k p + 1} \equiv (n + m k p)^{n + m k p} (\mod p)$ . よってフェルマーの小定理を考えると( $mod p$ で)
$(n + m k p + 1)^{n + m k p + 1} \equiv (n + 1)^{n + 1 + m k} \equiv (n + m k p)^{n + m k p} \equiv n^{n + m k}$
$(n + 1)^{n + 1} \equiv n^{n}$ だから $n, n + 1$ は $p$ の倍数にはならず,
$(n + 1)^{m k} \equiv n^{m k}$ . 特に $(n + 1)^{m} - n^{m} \equiv 0 (\mod p)$ (別に $k$ を考えなくて良かったですね).
この式を眺めると指数に $m$ という定数しか入ってないことが分かります. つまり $(n + 1)^{m} - n^{m}$ は $n$ の多項式です. $p$ は $P (n)$ の素因数としてほぼ任意に取れるから多項式として $P (n) | (n + 1)^{m} - n^{m}$ が成立してもおかしくなさそうです. ただ, これはキツそうだとすぐ分かって $mod p^{2}$ 系の情報が何もないので $P (n)$ の整数係数多項式としての素因数の情報を知るのが限界でしょう.

$P$ の整数係数多項式としての素因数, つまり整数の範囲で既約な整数係数多項式 $Q (x)$ で $Q (x) | P (x)$ を満たすものは $Q (x) | (x + 1)^{m} - x^{m}$ を満たす.

$Q (x) | (x + 1)^{m} - x^{m}$ でないなら $Q (x), (x + 1)^{m} - x^{m}$ は互いに素なので, ある整数係数多項式 $A, B$ と非零整数 $c$ があって $A (x) Q (x) - B (x) ((x + 1)^{m} - x^{m}) = c$ となる. (整数におけるベズーの定理の多項式版である.)
ここでシューアの定理から $p | Q (n)$ なるとても大きい素因数 $p$ が取れるので(正確には $n = k m + a$ の形なので $Q (k m + a)$ を $k$ の多項式と見なしてシューアの定理を用いている))上の議論から $p | (n + 1)^{m} - n^{m}$ . よって $c | p$ . $p$ は $| c |$ より大きく取れるのでこれは矛盾. よって補題は示された.

というわけで $P$ の多項式としての素因数の情報が分かった. このまま $Q$ について考える. ガウスの補題を考えれば今や $Q (n) | (n + 1)^{m} - n^{m}$ なのだから最初の式に代入してしまって( $n = k m + a$ としよう)
$2022 ((k m + a + 1)^{k m + a + 1} - (k m + a)^{k m + a}) \equiv 2022 (k m + a)^{k m} ((k m + a + 1)^{a + 1} - (k m + a)^{a}) \equiv 0 (\mod Q (n))$ .
$(k m + a)^{k m}$ は $Q (k m + a)$ と互いに素なので, $Q (n) | 2022 ((n + 1)^{a + 1} - n^{a})$ .
さっき(補題2)と同様にすれば多項式として $Q (n) | (n + 1)^{a + 1} - n^{a}$ (最後に補足します).
これと $Q (n) | (n + 1)^{m} - n^{m}$ があれば互除法みたいにして $(x + 1)^{m a + m} \equiv x^{m a} (x + 1)^{a} \equiv x^{m a} mod Q (x)$ . よって $Q (x) | (x + 1)^{m} - 1$ , $Q (x) | x^{m} - 1$ . ここから互除法をしても良いのだが多項式はその零点を考えれば良いので $Q (α) = 0$ なる複素数 $α$ を考えると $| α | = | α + 1 | = 1$ がわかる. これは $α = \frac{- 1 \pm \sqrt{3} i}{2}$ となって, 結局 $Q (x) = x^{2} + x + 1$ が分かりました.
つまり $P (x) = (x^{2} + x + 1)^{t}$ だというわけですね. 流石に十分大きい $t$ ではキツそう. つまり $max t$ が大事そう. まずは $t = 1$ を考えてみる, これが上手く行かないと始まらないので. $x^{2} + x + 1 | (x + 1)^{m} - 1, x^{m} - 1$ だから $6 | m$ が必要. また, $x^{2} + x + 1 | (x + 1)^{a + 1} - x^{a}$ だからこちらは $a \equiv 1 (\mod 6)$ が必要. これから $n \equiv 1 mod 6$ が常に成立してる, 従って $3^{t} | P (n)$ が分かる.
一方オイラーの定理より $(6 s + 2)^{6 s + 2} - (6 s + 1)^{6 s + 1} \equiv (6 s + 2)^{2} - 6 s - 1 \equiv 3 (\mod 9)$ より与式の分子は $v_{3} (2022) = 1$ だから $3$ で $2$ 回しか割り切れない. よって $t \leq 2$ .
あとはひたすら面倒な計算(二項定理とかでゴリ押す)をすれば $t = 0, 1, 2$ は行けている事が分って答えは $P (x) = 1, x^{2} + x + 1, (x^{2} + x + 1)^{2}$ .

最後 $v_{3}$ を考えたのはこれで上手く行ってくれないと計算が地獄になるからこれが回るはずという勘です. あとは $3$ が小さくて楽というのもある.
中盤の多項式と整数の合わせ技(考察の順序を変えたらもう少し簡潔になるかとは思うがあえて自分が思いついた順にしておく)は次の問題でも見られる.

ISL2011N6

$P, Q$ を整数係数多項式とし, 任意の定数でない整数係数多項式は $P, Q$ の両方を割ることはないとする. 任意の正整数 $n$ について $P (n), Q (n)$ は正で, $2^{Q (n)} - 1 | 3^{P (n)} - 1$ が成立するなら $P$ は定数である事を示せ.

以下は前半の手法の類題である.

APMO2021P2

多項式 $P$ と正整数 $n$ に対し $P_{n}$ を $0 < a < b \leq n$ かつ $n | | P (a) | - | P (b) |$ を満たす整数の組 $(a, b)$ の個数とする. 任意の正整数 $n$ に対して $P_{n} \leq 2021$ が成り立つような整数係数多項式 $P$ を全て求めよ.

Iran 3rd 2012

整数係数多項式 $P$ は恒等的には $0$ でないとする. このとき, 以下をみたす素数 $q$ が無限個あることを示せ:
ある正の整数 $n$ が存在して, $2^{n} + P (n)$ が $q$ の倍数となる.

一般に次の定理が知られているらしい. 面白いので載せておく. ( $P (n)$ とか $2^{n} + P (n)$ は定理の条件を満たす) (prime divisor linear recurrence sequenceとか調べるといっぱい出てくる)

$k$ を正整数, $u_{0}, . . ., u_{k - 1}, r_{1}, . . . r_{k}$ を整数とし $u_{n} = r_{1} u_{n - 1} + \dots + r_{k} u_{n - k} (n \geq k)$ として $u_{n}$ を定める. もし $u_{n}$ の特性方程式の根 $α, β (α \neq β)$ であって $\frac{α}{β}$ が $1$ の冪乗根であるようなものが存在しないのならば $P (u_{N}) = P ({u_{n} | n \in N})$ は無限集合である.

また, $u_{n}$ の一般項を $u_{n} = \sum_{i = 1}^{t} f_{i} (n) α_{i}^{n}$ と表示したとき $t \geq 2$ となるのならば $lim_{n \to \infty} max P ({u_{n}}) = \infty$ .

また素因数の大きさについて, 次のような定理が知られているらしい. (証明はベイカーの対数一形式の理論を用いるらしい)

$P (x)$ を $0$ でない $2$ つ以上の根を持つ整数係数多項式とする. このとき $P$ に依存するある正定数 $c, N$ が存在して $N$ 以上の任意の正整数 $n$ について $P (n)$ は $c \log \log n$ 以上の素因数を持つ.

補足
整数における整除関係と多項式における整除関係がある程度は対応しているという定理が存在するのでそれを使えば明らかですね.

$P (x), Q (x)$ を多項式とし $P (x)$ は既約で原始的(係数の最大公約数が $1$ )であるとする. このとき以下は同値:

$P (x) | Q (x)$
十分大きい任意の正整数 $n$ について $rad (P (n)) | Q (n)$

$\Rightarrow$ を示す.
仮定より $P (x) R (x) = Q (x)$ なる有理数係数多項式 $R (x)$ があるが $P (x)$ は原始的なのでガウスの補題より $R (x)$ は整数係数多項式である. よって $n \in N$ を $P (n) \neq 0$ となるように任意にとると(別に $P (n) = 0$ でも悪いことは無いがなんか嫌なので) $R (n) \in Z$ だから $rad (P (n)) | P (n) | Q (n)$ である.