ファウルハーバーの公式はどこまで因数分解できるのか？

はじめに
$1$ から $n$ までの $m$ 乗和 $S_m(n)=1^m+2^m+\cdots+n^m$ は $m+1$ 次多項式で表せることが知られており、以下の性質を持ちます。
$m=1,3,5,\cdots$ のとき、$S_m(n)$ は $n$, $n+1$ を因数に持つ
$m=2,4,6,\cdots$ のとき、$S_m(n)$ は $n$, $n+1$, $2n+1$ を因数に持つ
$m\geq 1$ のとき$S_m(n)$ がこれ以外に有理係数1次式の因数を持たないことを示します。
内容は、 mathematics や mathoverflow の質問への回答として投稿したものと同じになります。

1. 基本的な性質
   定理1.1
   恒等式 $$S_m(-x)=(-1)^{m+1}S_m(x-1) \quad \cdots(1.1)$$ が成り立つ。
   証明
   $(1.1)$ が解を無数に持つことを示せばよい。
   $S_m(0)=(-1)^{m+1}S_m(-1)=0$ より $x=0$ のとき $(1.1)$ は成り立つ。
   $x=k$ のとき $(1.1)$ が成り立つと仮定する。このとき $$\begin{aligned} S_m(-k-1) &= S_m(-k)-(-k)^m \ &= (-1)^{m+1}S_m(k-1)+(-1)^{m+1}k^m \ &= (-1)^{m+1}S_m(k) \end{aligned}$$
   よって $x=k+1$ のときも $(1.1)$ は成り立つ。 $\square$
   定理1.2
   $k$, $l$, $N$ を整数とし、$k$ は $N$ の倍数とする(ただし $N>0$)。
   合同式 $$S_m(k+l)\equiv S_m(k)+S_m(l) \pmod{N} \quad \cdots(1.2)$$ が成り立つ。
   証明
   $l=0$ のときは自明。$l\geq 1$ とする。 $$\begin{aligned} S_m(k+l)-S_m(k) &= (k+1)^m+(k+2)^m+\cdots+(k+l)^m \ &\equiv 1^m+2^m+\cdots+l^m \pmod{N} \ &\equiv S_m(l) \pmod{N} \end{aligned}$$
   また $(1.1)$ より、 $$\begin{aligned} S_m(k-l)-S_m(k) &= -(k-l+1)^m-(k-l+2)^m-\cdots-(k-l+l)^m \ &\equiv (-1)^{m+1}{(l-1)^m+(l-2)^m+\cdots+0^m} \pmod{N} \ &\equiv (-1)^{m+1}S_m(l-1) \pmod{N} \ &\equiv S_m(-l) \pmod{N} \end{aligned}$$ $\square$
   定理1.3
   合同式 $$S_m(kl)\equiv l\cdot S_m(k) \pmod{N} \quad \cdots(1.3)$$ が成り立つ。
   証明
   まず $k=N$ のときについて示す。
   $l=0$ のときは自明。$l\geq 1$ とすると $(1.2)$ より、 $$\begin{aligned} S_m(Nl) &= S_m(0)+\sum_{j=0}^{l-1}{S_m(N(j+1))-S_m(Nj)} \ &\equiv \sum_{j=0}^{l-1}S_m(N) \pmod{N} \ &\equiv l\cdot S_m(N) \pmod{N} \end{aligned}$$
   これと $(1.1)$ から、 $$\begin{aligned} S_m(N(-l))-(-l)\cdot S_m(N) &= (-1)^{m+1}S_m(Nl-1)+l\cdot S_m(N) \ &\equiv (-1)^{m+1}S_m(Nl)+l\cdot S_m(N) \pmod{N} \ &\equiv {(-1)^{m+1}+1}\cdot l\cdot S_m(N) \pmod{N} \end{aligned}$$
   これより、$m$ が偶数のときは $(1.3)$ が成り立つ。
   $m$ を奇数とする。このとき $N$ が奇数ならば、 $$\begin{aligned} S_m(N) &= 0^m+1^m+2^m+\cdots+\left(\frac{N-1}{2}\right)^m+\left(N-\frac{N-1}{2}\right)^m+\cdots+(N-1)^m+(N-0)^m \ &\equiv 0^m+1^m+2^m+\cdots+\left(\frac{N-1}{2}\right)^m-\left(\frac{N-1}{2}\right)^m-\cdots-1^m-0^m \pmod{N} \ &\equiv 0 \pmod{N} \end{aligned}$$
   よって $S_m(N)\equiv 0 \pmod{N} \quad \cdots(1.3.1)$ だから $N$ が奇数のとき $(1.3)$ は成り立つ。
   $N$ が偶数の時は中心の項が残って $S_m(N)\equiv (N/2)^m \pmod{N}$ だから、 $$\begin{aligned} S_m(N(-l))-(-l)\cdot S_m(N) &\equiv {(-1)^{m+1}+1}\cdot l\cdot S_m(N) \ &\equiv 2l\cdot (N/2)^m \pmod{N} \ &\equiv l\cdot N\cdot (N/2)^{m-1} \pmod{N} \ &\equiv 0 \pmod{N} \end{aligned}$$
   よって $N$ が偶数のときも $(1.3)$ は成り立つ。
   $k$ が一般の場合、$k$ はある整数 $k'$ で $k=Nk'$ と表せるから、 $$S_m(kl)\equiv S_m((Nk')l)\equiv k'\cdot l\cdot S_m(N)\equiv l\cdot S_m(Nk')\equiv l\cdot S_m(k) \pmod{N}$$
   よって $(1.3)$ は成り立つ。 $\square$
   以降 $(1.1)$, $(1.2)$, $(1.3)$ は断りなく用いる。
2. 主要な補題と定理
   整数 $a$, $b$, $c$ ($b>0$) は $S_m(a/b)=0$ をみたし、$a$ と $b$ は互いに素とする。 また整数 $N$ は $a-bc$ の約数とする。
   補題2.1
   $$\frac{a}{b}=\frac{Ns-c}{N^2t-1} \quad \cdots(2.1)$$ をみたす整数 $s$, $t$ が存在する。
   証明
   $a$ と $b$ は互いに素だから、$a-bc$ と $b$ は互いに素。よって $aN$ と $b$ は互いに素。 さらに $(a-bc)/N$ は整数だから、不定方程式 $$aNt-bs=(a-bc)/N \quad \cdots(2.1.1)$$ をみたす整数 $s$, $t$ が存在する。$(2.1.1)$ を変形して $(2.1)$ を得る。 $\square$
   補題2.2
   以下の恒等式が成り立つ(ただし、$y\neq 0$)。 $$y^{2m+1}S_m(x/y)=y^m{S_m(x+y)-S_m(y)}-\sum_{j=0}^{m-1}\binom{m}{j}y^{m-1-j}S_{m-j}(y){y^{2j+1}S_j(x/y)} \quad \cdots(2.2)$$
   証明
   $n$, $y>0$ を整数とすると、 $$\begin{aligned} S_m((n+1)y)-S_m(y) &= \sum_{l=1}^{n}{S_m((l+1)y)-S_m(ly)} \ &= \sum_{l=1}^{n}\sum_{k=1}^{y}(ly+k)^m \ &= \sum_{l=1}^{n}\sum_{k=1}^{y}\sum_{j=0}^{m}\binom{m}{j}l^jy^jk^{m-j} \ &= \sum_{l=1}^{n}\sum_{j=0}^{m}\binom{m}{j}l^jy^jS_{m-j}(y) \ &= \sum_{j=0}^{m}\binom{m}{j}y^jS_{m-j}(y)S_j(n) \end{aligned}$$
   この等式をみたす $n$, $y$ は無数に存在するから、恒等式である。
   よって $y\neq 0$ のとき $n=x/y$ を代入でき、 $$\begin{aligned} S_m(x+y)-S_m(y) &= \sum_{j=0}^{m}\binom{m}{j}y^jS_{m-j}(y)S_j(x/y) \ &= y^{m+1}S_m(x/y)+\sum_{j=0}^{m-1}\binom{m}{j}y^jS_{m-j}(y)S_j(x/y) \ &= y^{m+1}S_m(x/y)+\sum_{j=0}^{m-1}\binom{m}{j}y^{-1-j}S_{m-j}(y){y^{2j+1}S_j(x/y)} \end{aligned}$$
   両辺に $y^m$ をかけて $(2.2)$ を得る。 $\square$
   定理2.3
   合同式 $$S_m(a-bc)\equiv -b\cdot S_m(c) \pmod{N} \quad \cdots(2.3)$$ が成り立つ。
   証明
   $(2.1)$ の整数 $s$, $t$ について、$x=Ns-c$, $y=N^2t-1$ とおく。
   このとき $x/y=a/b$ であるから、$y^{2\cdot 0+1}S_0(x/y)=x=Ns-c$ は整数。
   また $(2.2)$ より $y^{2j+1}S_j(x/y)$ が $j=0,1,\cdots,m-1$ で整数であるとき、$y^{2m+1}S_m(x/y)$ も整数。
   よって $(2.2)$ の左辺と右辺の ${}$ 内は整数とできる。
   さらにこの右辺の $S_m(y)$, $S_{m-j}(y)$ は、$j'=0,1,\cdots,m$ とすると $$S_{j'}(y)=S_{j'}(N^2t-1)\equiv Nt\cdot S_{j'}(N)+S_{j'}(-1) \pmod{N}\equiv 0 \pmod{N}$$
   よって $(2.2)$ の両辺で $\bmod N$ をとると $$\begin{aligned} (N^2t-1)^{2m+1}S_m(a/b) &\equiv (N^2t-1)^mS_m(Ns-c+N^2t-1) \pmod{N} \ &\equiv (-1)^mS_m(N^2t+Ns-c-1) \pmod{N} \ &\equiv -S_m(-N^2t-Ns+c) \pmod{N} \end{aligned}$$
   $S_m(a/b)=0$ より $S_m(-N^2t-Ns+c)\equiv 0 \pmod{N}$。また、 $$\begin{aligned} S_m(-N^2t-Ns+c) &\equiv -Nt\cdot S_m(N)-s\cdot S_m(N)+S_m(c) \pmod{N} \ &\equiv -s\cdot S_m(N)+S_m(c) \pmod{N} \end{aligned}$$
   よって $-bs\cdot S_m(N)\equiv -b\cdot S_m(c) \pmod{N}$。さらに、 $$\begin{aligned} S_m(a-bc) &= S_m((aNt-bs)N) \ &\equiv aNt\cdot S_m(N)-bs\cdot S_m(N) \pmod{N} \ &\equiv -bs\cdot S_m(N) \pmod{N} \end{aligned}$$
   以上より $S_m(a-bc)\equiv -b\cdot S_m(c) \pmod{N}$。 $\square$
   定理2.4
   $m$ が奇数のとき、$S_m(x)$ は $x$, $x+1$ 以外の有理係数1次式の因数を持たない。
   証明
   $m$ が奇数のとき、$a/b=0,-1$ となることを示せばよい。
   $(2.3)$ に $c=1,-2$ を代入すると、
   $c=1$ のとき $S_m(a-b)\equiv -b \pmod{N}$
   $c=-2$ のとき $S_m(a+2b)\equiv -b \pmod{N}$
   $-b$ と $a-bc$ の約数 $N$ は互いに素だから、$d\in{a-b,a+2b}$ とおくと $d$ と $S_m(d)$ は互いに素。
   ここで $d$ がある整数 $d'$ と素数 $p$ で $d=d'p^2$ と表せるとき、 $$S_m(d)=S_m(d'p^2)\equiv d'p\cdot S_m(p)\equiv 0 \pmod{p}$$ だから $d$ と $S_m(d)$ は互いに素にならない。
   また $d$ がある整数 $d'$ と奇素数 $p$ で $d=d'p$ と表せるとき、$(1.3.1)$ から $$S_m(d)=S_m(d'p)\equiv d'\cdot S_m(p)\equiv 0 \pmod{p}$$ となり $d$ と $S_m(d)$ は互いに素にならない。
   よって $d\in{\pm 1,\pm 2}$ であり、これをみたす $a$, $b$ は $(a,b)=(-1,1),(0,1)$ のみ。
   このとき $a/b=0,-1$ であり、これは実際に $S_m(a/b)=0$ をみたす。 $\square$
   定理2.5
   $m$ が偶数のとき、$a/b\neq 0,-1$ ならば $b$ は偶数。
   証明
   $(2.3)$ に $c=0,-1$ を代入すると、
   $c=0$ のとき $S_m(a)\equiv 0 \pmod{N}$
   $c=-1$ のとき $S_m(a+b)\equiv 0 \pmod{N}$
   $b$ は奇数と仮定する。このとき $a$, $a+b$ のどちらかが偶数。
   偶数であるほうを $d=2^jd'$ ($j\geq 1$, $d'$ は奇数)とおく。このとき $a/b\neq 0,-1$ であるから $d$, $d'\neq 0$。
   $S_m(d)$ は $N$ の倍数になるから、$S_m(2^jd')\equiv 0 \pmod{2^j}$。
   また $S_m(2^jd')\equiv d'S_m(2^j) \pmod{2^j}$ であるから、$S_m(2^j)\equiv 0 \pmod{2^j}$。
   ここで $S_m(2^1)\equiv 1^m+2^m\equiv 1 \pmod{2^1}$。また $j\geq 2$ のとき $S_m(2^{j-1})\equiv 2^{j-2} \pmod{2^{j-1}}$ と仮定する。
   $m$ が偶数であるから、整数 $k$ について $(k+2^{j-1})^m\equiv k^m+m\cdot 2^{j-1}k^{m-1}\equiv k^m \pmod{2^j}$。
   したがって、 $$\begin{aligned} S_m(2^j) &= \sum_{k=1}^{2^{j-1}}k^m+\sum_{k=1}^{2^{j-1}}(k+2^{j-1})^m \ &\equiv \sum_{k=1}^{2^{j-1}}k^m+\sum_{k=1}^{2^{j-1}}k^m \ &\equiv 2S_m(2^{j-1})\equiv 2^{j-1} \pmod{2^j} \end{aligned}$$
   よって $S_m(2^j)\not\equiv 0 \pmod{2^j}$ となり矛盾。 $\square$
3. 偶数乗の場合
   補題3.1
   整数 $l\geq 2$ に対し、ある整数 $a_1,a_2,\cdots,a_{l-1}$ が存在して $S_{2l}(x)=\frac{1}{2l+1}\left\{\frac{x^l(x+1)^l(2x+1)}{2}-\sum_{j=1}^{l-1}a_jS_{2j}(x)\right\} \quad \cdots(3.1)$
   証明
   $f(x)=x^l(x+1)^l(2x+1)$ は、ある整数 $a_1',a_2',\cdots,a_{2l-1}'$ で以下のように表せる。 $$f(x)=2x^{2l+1}+(2l+1)x^{2l}+\sum_{j=1}^{2l-1}a_j'x^j$$
   また $f(-x)=(-x)^l(-x+1)^l(-2x+1)=(-1)^{2l+1}x^l(x-1)^l(2x-1)=-f(x-1)$ より、 $$\frac{f(x)-f(x-1)}{2}=\frac{f(x)+f(-x)}{2}=(2l+1)x^{2l}+\sum_{j=1}^{l-1}a_{2j}'x^{2j}$$
   両辺 $x=1,2,\cdots,n$ の和を取ると、 $$\frac{f(n)}{2}=(2l+1)S_{2l}(n)+\sum_{j=1}^{l-1}a_{2j}'S_{2j}(n)$$
   $n$ を $x$ に置き換え、$a_j=a_{2j}'$ として整理すれば、 $S_{2l}(x)=\frac{1}{2l+1}\left\{\frac{x^l(x+1)^l(2x+1)}{2}-\sum_{j=1}^{l-1}a_jS_{2j}(x)\right\}$ $\square$
   ここで $l\geq 1$ に対し、整数 $A_l>0$ と整数係数多項式 $T_l(x)=\sum_{j=0}^{2l-2}C_{l,j}x^j$ (ただし、$C_{l,j}$ は整数)は $$S_{2l}(x)=\frac{x(x+1)(2x+1)T_l(x)}{A_l}$$ をみたすとする。
   ここで $A_l$ は、各 $C_{l,j}$ の最大公約数と互いに素とする。
   補題3.3
   $l\geq 1$ に対し、$C_{l,2l-2}$ は奇数である。
   証明
   整数 $N>0$ が $2$ で最大 $k$ 回割り切れるとき、$V_2(N)=k$ と表すとする。
   $l=1$ のとき $C_{1,0}=1$ より奇数。また $A_1=6$ より $V_2(A_1)=1$。
   $l\geq 2$ のとき、$V_2(A_1),V_2(A_2),\cdots,V_2(A_{l-1})\leq 1$ と仮定する。$(3.1)$ より、 $S_{2l}(x)=\frac{x(x+1)(2x+1)}{2l+1}\left\{\frac{x^{l-1}(x+1)^{l-1}}{2}-\sum_{j=1}^{l-1}\frac{a_jT_j(x)}{A_j}\right\} \quad \cdots(3.1.1)$
   $(3.1.1)$ より、$A_l$ は $(2l+1)\cdot\mathrm{lcm}(2,A_1,A_2,\cdots,A_{l-1})$ の約数であるから、 $$V_2(A_l)\leq V_2(2l+1)+V_2(\mathrm{lcm}(2,A_1,A_2,\cdots,A_{l-1}))=0+1=1$$
   よって $V_2(A_l)\leq 1$。
   また $(3.1.1)$ より $S_{2l}(x)$ の最高次の係数は $\frac{1}{2l+1}$ であるから、 $$\frac{1}{2l+1}=\frac{2C_{l,2l-2}}{A_l}\iff A_l=2(2l+1)C_{l,2l-2}$$
   これにより $1\leq V_2(A_l)$ だから、 $$1\leq V_2(A_l)=V_2(2(2l+1)C_{l,2l-2})\leq 1+0+V_2(C_{l,2l-2})\leq 1\implies V_2(C_{l,2l-2})=0$$
   よって $C_{l,2l-2}$ は奇数。 $\square$
   定理3.4
   $l\geq 1$ に対し、$S_{2l}(x)$ は $x$, $x+1$, $2x+1$ 以外の有理係数1次式の因数を持たない。
   証明
   $a/b=0,-1,-1/2$ となることを示す。
   $a/b\neq 0,-1,-1/2$ ならば、$a/b$ は $T_l(x)$ の根である。
   このとき定理2.5より $b$ は偶数であるから、$T_l(x)$ の最高次の係数 $C_{l,2l-2}$ は偶数でなければならない。
   しかし、これは補題3.3と矛盾する。 $\square$
   おわりに
   はじめてこの問題に興味を持ったのはたしか中学２年生ぐらいでした。
   以来、たまに思い出しては考えてを繰り返し、14年が経ってしまいました。最終的にできた回答は7年前くらいにはもう作れたはずのもので拍子抜けでしたが、自分の中にあった呪いのようななにかも一緒に解けたのかなと思います。
   最後にこれがどこかの天才のお目に触れ、より洗練されて広がっていき、後世に何らかの形で残るのなら、もう思い残すことはないかな。