n⁵+5 と (n+1)⁵+5 の最大公約数 - 現実と数学の区別が付かない

Twitterで見かけた答えが意外過ぎる問題．

多項式の公約数と言えば、昔どこかに投稿したんだけど、nが自然数の時の n^5+5 と (n+1)^5+5 の正の公約数としてあり得る整数が、おそらく見た目からは予想できない結果で、面白い。
— nishimura (@icqk3) 2020年8月10日

自然数 $a,b$ の最大公約数 (greatest common divisor) を $\mathrm{gcd}(a,b)$ で表します．

$n$ を自然数とする． $\mathrm{gcd}(n^5+5,(n+1)^5+5)$ を求めよ．

この手の問題は，小さい $n$ で試してみるのが常套手段です． $n\le 100$ くらいまで試してみると，すべて $\mathrm{gcd}(n^5+5,(n+1)^5+5)=1$ となります．その後， $n$ を 1万，10万と増やしていっても，ずっと gcd は $1$ のままです．こうなると，はいはいパターン見えてきたよと $\mathrm{gcd}(n^5+5,(n+1)^5+5)=1$ であると予想を立て，数学的帰納法で証明しようという気になります．しかしこれはうまくいきません．実は $n<533360$ のときは $\mathrm{gcd}(n^5+5,(n+1)^5+5)=1$ なのに， $n=533360$ で急に\begin{align}\mathrm{gcd}(533360^5+5,533361^5+5)= 1968751\end{align}となります．こんなことが起こることも面白いですし，これに気が付いたことも凄いと思います．この $n$ が約53万でフリーザの戦闘力とほぼ同じなことも芸術点が高いです．

Why Japanese people?

なぜこのようなことが起こるのか考えてみましょう．

$a_1,\dots,a_k \in \mathbb{Z}$ で生成される $\mathbb{Z}$ のイデアルを $\langle a_1,\dots,a_k \rangle$ で表すことにします．すると次が成り立ちます．

\begin{align}\langle a, b\rangle=\langle \mathrm{gcd}(a,b)\rangle\end{align}

最大公約数をこの等式で理解することは結構大切です．例えばユークリッドの互除法はイデアルの生成系の取り換えをしているだけと見ることがでいます．また， $\langle a, b\rangle$ の要素は $\mathrm{gcd}(a,b)$ の倍数になっているので，具体的な整数 $m\in \langle a, b\rangle$ を $1$ つ見つけることができると， $\mathrm{gcd}(a,b)$ の候補が有限個に絞られます．

$\mathrm{gcd}(n^5+5,(n+1)^5+5)$ がどうなるか考えていきましょう．
\begin{align}
f_0(n):=&~(n+1)^5+5\\
f_1(n):=&~n^5+5\\
f_2(n):=&~f_0(n)-f_1(n)=5n^4+10n^3+10n^2+5n+1\\
f_3(n):=&~5f_1(n)-(n-2)f_2(n)=10n^3+15n^2+9n+27\\
f_4(n):=&~4f_2(n)-(2n+1)f_3(n)=7n^2-43n-23\\
f_5(n):=&~49f_3(n)-(70n+535)f_4(n)=25056n+13628\\
f_6(n):=&~156950784 f_4(n)-(43848n-293201)f_5(n)=385875196
\end{align} なので， $385875196\in \langle n^5+5,(n+1)^5+5\rangle$ となります．ちょっと注意をしておくと，この計算はユークリッドの互除法そのものではありませんので，最後に出てきた $385875196$ は最大公約数とは限りません．しかし，定義から $k\ge 2$ のとき $f_k(n) \in \langle f_{k-1}(n), f_{k-2}(n) \rangle$ であるので，\begin{align} 385875196&=f_6(n)\in \langle f_{5}(n), f_{4}(n) \rangle \subset\langle f_{4}(n), f_{3}(n) \rangle \subset\langle f_{3}(n), f_{2}(n) \rangle \\
& \subset\langle f_{2}(n), f_{1}(n) \rangle \subset\langle f_{1}(n), f_{0}(n) \rangle = \langle n^5+5,(n+1)^5+5\rangle \end{align} が言えるのです．

つまり $\mathrm{gcd}(n^5+5,(n+1)^5+5)$ は $385875196$ の約数です． $385875196$ を素因数分解してみると\begin{align}
385875196=2^2\times 7^2\times 1968751
\end{align}となります．

素因数 $p=2,7,1968751$ ごとに， $p$ が $\mathrm{gcd}(n^5+5,(n+1)^5+5)$ を割り切るかどうか考えてみます．

$p$ が $\mathrm{gcd}(n^5+5,(n+1)^5+5)$ を割り切ることは $x^5+5\in \mathbb{F}_p[x]$ が $n, n+1$ の両方を根に持つことと同値です．

$p=2$ のとき．

$x^5+5=x^5+1 \in \mathbb{F}_2[x]$ は $x=1$ しか根を持ちません．
よって $\mathrm{gcd}(n^5+5,(n+1)^5+5)$ は $2$ で割り切れません．

$p=7$ のとき．

$x^5+5 \in \mathbb{F}_7[x]$ は $x=4$ しか根を持ちません．
よって $\mathrm{gcd}(n^5+5,(n+1)^5+5)$ は $7$ で割り切れません．

$p=1968751$ のとき．

\begin{align} x^5+5=(x-1066696)(x-1707583)(x-96502)(x-533360)(x-533361) \end{align} という因数分解が $\mathbb{F}_{1968751}[x]$ で成り立ちます．つまり $n^5+5$ は \begin{align} n\equiv 1066696, 1707583, 96502, 533360, 533361 \mod 1968751\end{align} のときに $1968751$ の倍数となります． $n^5+5, (n+1)^5+5$ が共に $1968751$ の倍数となるのは $n\equiv 533360 \mod 1968751$ のときのみです．

よって，冒頭の問題の答えは \begin{align} \mathrm{gcd}(n^5+5, (n+1)^5+5)= \begin{cases}
1968751 & (n\equiv 533360 \mod 1968751)\\
1 & (\mbox{otherwise})
\end{cases}\end{align} となります．

以上．

追記

世の中には整数係数グレブナー基底という超便利な道具があり，Sage などに実装されているそうです．
doc.sagemath.org
$\langle x^5+5,(x+1)^5+5\rangle \subset \mathbb{Z}[x]$ の整数係数グレブナー基底を計算すると $\{x + 1435391, 1968751\}$ となります（下記リンクで計算結果を見ることができます）．
sagecell.sagemath.org
これは $\mathbb{Z}[x]$ のイデアルとして \begin{align}\langle x^5+5,(x+1)^5+5\rangle =\langle x + 1435391, 1968751 \rangle\end{align} であることを示しています．このことから，自然数 $n$ に対して \begin{align} \mathrm{gcd}(n^5+5, (n+1)^5+5)=\mathrm{gcd}(n + 1435391, 1968751) \end{align} が成り立つことが分かります． $1968751$ が素数であることも計算機で確かめることができるので， $\mathrm{gcd}(n^5+5, (n+1)^5+5)$ は $1$ まはた $1968751$ であり， $\mathrm{gcd}(n^5+5, (n+1)^5+5)=1968751$ となるのは \begin{align} n\equiv - 1435391 \equiv 533360 \mod 1968751\end{align} のときということが分かります．

$x^{17}+9, (x+1)^{17}+9$ でも類似の現象が起こるそうです．
sagecell.sagemath.org
このグレブナー基底の計算によると \begin{align} &\langle x^{17}+9, (x+1)^{17}+9\rangle \\
&= \left\langle\begin{array}{r} x + 512149312322827330662764931050044963334032796143126, \\
8936582237915716659950962253358945635793453256935559~ \end{array} \right\rangle\end{align}が成り立ちます．この2番目の生成元である自然数が素数になっています．

さらに追記

くさだんごさんが記事を書いてくれました．
mochi-mochi61.hatenablog.com
イデアル $I=\langle f(x), g(x) \rangle \subset \mathbb{Z}[x]$ に対して， $I\cap \mathbb{Z}$ に含まれる元を得るために終結式を使っています．
終結式 - Wikipedia
私の記事ではなんちゃってユークリッドの互除法を使いましたが，余計な素因数 $2,7$ が出ていました．終結式を使う方法では余分な因子が出ません．