この問いでは,$0$ 以上の整数の $2$ 乗になる数を平方数と呼ぶ。$a$ を正の整数とし,$f_a(x)=x^2+x-a$ とおく。
(1) $n$ を正の整数とする。$f_a(n)$ が平方数ならば,$n\leqq a$ であることを示せ。
(2) $f_a(n)$ が平方数となる正の整数 $n$ の個数を $N_a$ とおく。次の条件 (i),(ii) が同値であることを示せ。
(i) $N_a=1$ である。
(ii) $4a+1$ は素数である。
本稿では次の記号を用いる。
正の整数 $n$ について $f_a(n)$ が平方数であることは,非負整数 $m$ を補助変数とする不定方程式
$$
n^2+n-m^2=a \tag{1.1}
$$
が解をもつことと同値である。$a\geqq1$ より
$$
m^2=n^2+n-a < n^2+2n+1=(n+1)^2
$$
であり,$m$ と $n+1$ はともに非負であるから $m < n+1$,整数性より
$$
0\leqq m\leqq n \tag{1.2}
$$
を得る。平方数は隣り合う平方数 $n^2$ と $(n+1)^2$ の間に存在しえない。この離散性が平方根 $m$ を $n$ 以下に抑える。さらに (1.1) は
$$
a-n=n^2-m^2=(n-m)(n+m) \tag{1.3}
$$
と書き直せる。$n+m\geqq n\geqq1$ であるから,(1.2) と (1.3) から次が従う。
$f_a$ を平方完成すると
$$
4f_a(x)=(2x+1)^2-(4a+1)=(2x+1)^2-M
$$
となる。すなわち $M=4a+1$ は二次式 $f_a(x)=x^2+x-a$ の判別式である。これにより (1.1) は
$$
(2n+1)^2-(2m)^2=M,\qquad\text{すなわち}\qquad uv=M\quad(u=2n+1-2m,\ v=2n+1+2m) \tag{1.4}
$$
と同値になる。ここで $u,v$ は奇数であり,$u+v=2(2n+1)$,$v-u=4m$ を満たす。二次の不定方程式が,一次因子の積が定数に等しいという約数の問題に変換された。逆に $(u,v)$ から
$$
n=\frac{u+v-2}{4},\qquad m=\frac{v-u}{4}
$$
を復元するとき,右辺が整数となることは $M\equiv1\pmod{4}$ から次の補題によって保証される。
奇数 $u,v$ が $uv\equiv1\pmod{4}$ を満たすならば $u\equiv v\pmod{4}$ である。特に $v-u\equiv0\pmod{4}$,$u+v\equiv2\pmod{4}$ が成り立つ。
奇数は法 $4$ で $1$ または $-1$ に合同である。$u\not\equiv v\pmod{4}$ ならば $uv\equiv1\cdot(-1)=-1\pmod{4}$ となり,仮定に反する。よって $u\equiv v\equiv\varepsilon\pmod{4}$($\varepsilon=\pm1$)であり,$v-u\equiv0$,$u+v\equiv2\varepsilon\equiv2\pmod{4}$ を得る。
(1.4) と 補題1 により,本問の核心は次の対応に要約される。
$n\in S_a$ に対し
$$
\Phi(n)=(2n+1-2m,\ 2n+1+2m)
$$
とおく。$\Phi$ は $S_a$ から $D_M$ への全単射であり,逆写像は $(u,v)\mapsto\dfrac{u+v-2}{4}$ で与えられる。$\Phi(n)=(u,v)$ のとき
$$
m=\frac{v-u}{4},\qquad a-n=\frac{(u-1)(v-1)}{4}
$$
が成り立つ。特に $N_a=\lvert D_M\rvert$ であり,自明解 $n=a$ は自明な因子対 $(1,M)$ に対応する。
証明は本解(2.2 節)で与える。$M > 1$ であるから,$D_M=\lbrace (1,M)\rbrace$ であることと $M$ が素数であることは同値である。したがって 定理2 により,設問 (2) は「自明解しかない $\iff$ 自明な因子対しかない」という同型の主張に読み替えられる。なお $a-n=\frac{(u-1)(v-1)}{4}$ は,$v > 0$ と $uv=M > 0$ から従う $u\geqq1$ だけで設問 (1) を再現する(3.1 節 (e))。
$f_a(-1-x)=f_a(x)$ であり,$f_a$ のグラフは直線 $x=-\frac12$ に関して対称である。$X=2n+1$,$Y=2m$ とおくと (1.4) は $X^2-Y^2=M$ となる。$M\equiv1\pmod{4}$ であるから,この方程式の整数解では $X$ は奇数,$Y$ は偶数であり,整数解は $(u,v)=(X-Y,\ X+Y)$ によって $uv=M$ を満たす整数の順序対と一対一に対応し(逆は $X=\frac{u+v}{2}$,$Y=\frac{v-u}{2}$),その個数は $2\tau(M)$ である。解の全体には二つの符号反転が作用する。
$$
X\mapsto-X\ \ (n\mapsto-1-n):\ (u,v)\mapsto(-v,-u),\qquad Y\mapsto-Y\ \ (m\mapsto-m):\ (u,v)\mapsto(v,u).
$$
設問 (1) の評価 $n\leqq a$ は自明解で等号が成り立つので改良できない。しかし非自明な解に限れば,隣接平方数の議論を一段精密化するだけで大幅に改良される。
$n\in S_a$ とする。
(a) $\dfrac{\sqrt{M}-1}{2}\leqq n\leqq a$ であり,左の等号は $m=0$ のとき,右の等号は $m=n$ のときに限る。
(b) $n\neq a$ ならば $n\leqq\dfrac{a+1}{3}$ であり,等号は $m=n-1$ のときに限る。
(c) $\dfrac{a+1}{3}\in S_a$ となるための必要十分条件は $a\equiv2\pmod{3}$,すなわち $3\mid M$ である。
(a) $(2n+1)^2=4f_a(n)+M=4m^2+M\geqq M$ であり,等号は $m=0$ のときに限る。右側は 1.2 節で示した。
(b) $n\neq a$ ならば 1.2 節より $m\neq n$ であり,(1.2) と合わせて $0\leqq m\leqq n-1$。よって $m^2\leqq(n-1)^2$ であり,
$$
a=n^2+n-m^2\geqq n^2+n-(n-1)^2=3n-1.
$$
等号は $m=n-1$ のときに限る。
(c) $\frac{a+1}{3}\in S_a$ ならば $\frac{a+1}{3}$ は整数であるから $a\equiv2\pmod{3}$。逆に $a\equiv2\pmod{3}$ ならば $n=\frac{a+1}{3}$ は正の整数で,$f_a(n)=n^2+n-(3n-1)=(n-1)^2$ は平方数である。最後に $M=4a+1\equiv a+1\pmod{3}$ である。
命題3 により,区間 $\frac{a+1}{3} < n < a$ には解が存在しない。$S_a$ は孤立した自明解 $a$ と,区間 $\left[\frac{\sqrt{M}-1}{2},\ \frac{a+1}{3}\right]$ に含まれる非自明解とに分かれる。(b) の上界に到達するか否かが $3\mid M$ で決まることは,非自明解の位置が $M$ の素因数を記録していることの最初の現れであり,一般には最大の非自明解が $M$ の最小素因数で決まる(5.5 節)。
以下は数値設定と設問構成からの分析であり,出題者の意図についての推定を含む。
| 着目する構造 | 数学的翻訳 | 対応する解法 |
|---|---|---|
| 隣接平方数の間隔 | $m\leqq n$ | 本解 (1),3.1 節 |
| 判別式・平方完成 | $uv=M$(因子対の全単射) | 本解 (2),3.2 節 |
| 平方根との差 | $(2k+1)n=a+k^2$ | 別解1(3.3 節) |
| 面積と周長 | $UV=M$,$U+V=4n+2$ | 参考解1(3.4 節) |
| 素数の素元性 | $M\mid (X-Y)(X+Y)$ | 参考解2(3.5 節) |
| 平方数は連続奇数の和 | $M=\sum_{j=2m}^{2n}(2j+1)$ | 参考解3(3.6 節) |
| 和と差の変数,双曲線 | $4a+1=(2x+1)(2y+1)$ | 3.7 節 |
$f_a(n)$ は平方数であるから,ある非負整数 $m$ により $n^2+n-a=m^2$ と表せる。$a\geqq1$ より
$$
m^2=n^2+n-a < n^2+2n+1=(n+1)^2.
$$
$m\geqq0$,$n+1 > 0$ であるから $m < n+1$ であり,$m,n$ は整数なので $m\leqq n$。よって
$$
n^2+n-a=m^2\leqq n^2
$$
となり,$n\leqq a$ である。
$M=4a+1$ とおく。$M\geqq5$,$M\equiv1\pmod{4}$ である。$n\in S_a$ に付随する $m$ は,(1) の証明により $0\leqq m\leqq n$ を満たす。また $f_a(a)=a^2$ であるから $a\in S_a$ である。
(a) $S_a$ から $D_M$ への写像。$n\in S_a$ に対し $u=2n+1-2m$,$v=2n+1+2m$ とおき,$\Phi(n)=(u,v)$ と書く。
$$
uv=(2n+1)^2-4m^2=4(n^2+n-m^2)+1=4a+1=M
$$
であり,$u=2(n-m)+1\geqq1$,$v-u=4m\geqq0$ である。よって $\Phi(n)\in D_M$。さらに $u+v=2(2n+1)$ から $n=\frac{u+v-2}{4}$ が復元されるので,$\Phi$ は単射である。
(b) $D_M$ から $S_a$ への写像。$(u,v)\in D_M$ とする。$M$ は奇数であるから $u,v$ は奇数であり,$uv=M\equiv1\pmod{4}$ と
補題1
より $u+v\equiv2$,$v-u\equiv0\pmod{4}$ である。そこで
$$
n=\frac{u+v-2}{4},\qquad m=\frac{v-u}{4}
$$
とおくと,$n,m$ は整数であり,$u\leqq v$ より $m\geqq0$ である。また $u+v-2\geqq0$ の等号は $u=v=1$,すなわち $M=1$ のときに限るので $u+v-2 > 0$ であり,これは $4$ の倍数だから $n\geqq1$ である。さらに $n-m=\frac{u-1}{2}$,$n+m=\frac{v-1}{2}$ より
$$
n^2+n-m^2=(n-m)(n+m)+n=\frac{(u-1)(v-1)+(u+v-2)}{4}=\frac{uv-1}{4}=a.
$$
よって $f_a(n)=m^2$ は平方数であり,$n\in S_a$。$m\geqq0$ であるからこの $m$ は $n$ に付随する平方根に一致し,
$$
2n+1-2m=\frac{u+v}{2}-\frac{v-u}{2}=u,\qquad 2n+1+2m=\frac{u+v}{2}+\frac{v-u}{2}=v
$$
より $\Phi(n)=(u,v)$。ゆえに $\Phi$ は全射である。
以上で
定理2
が示され,$N_a=\lvert D_M\rvert$ である。(b) の $n$ について
$$
a-n=\frac{uv-1}{4}-\frac{u+v-2}{4}=\frac{(u-1)(v-1)}{4} \tag{2.1}
$$
も成り立つ。
(c) 同値性。
(ii) $\Rightarrow$ (i):$M$ が素数ならば,$M$ の正の約数は $1$ と $M$ のみであるから $D_M=\lbrace (1,M)\rbrace$ であり,$N_a=1$。
(i) $\Rightarrow$ (ii):対偶を示す。$M$ が素数でないとすると,$M\geqq5$ より $M$ は合成数であり,$1 < u < M$ を満たす約数 $u$ が存在する。必要なら $u$ を $M/u$ に取り替えて $u\leqq\sqrt{M}$ としてよい。$v=M/u$ とおくと $(u,v)\in D_M$ であり,$u > 1$ より $(u,v)\neq(1,M)$。よって $N_a=\lvert D_M\rvert\geqq2$。対応する解は (2.1) より $a-n > 0$ を満たし,自明解と異なることが直接確かめられる。
以上より,(i) と (ii) は同値である。
| $a$ | $M$ | $D_M$ | $(n,m)$ | $N_a$ |
|---|---|---|---|---|
| $1$ | $5$ | $(1,5)$ | $(1,1)$ | $1$ |
| $2$ | $9=3^2$ | $(1,9),\ (3,3)$ | $(2,2),\ (1,0)$ | $2$ |
| $3$ | $13$ | $(1,13)$ | $(3,3)$ | $1$ |
| $4$ | $17$ | $(1,17)$ | $(4,4)$ | $1$ |
| $5$ | $21=3\cdot7$ | $(1,21),\ (3,7)$ | $(5,5),\ (2,1)$ | $2$ |
| $6$ | $25=5^2$ | $(1,25),\ (5,5)$ | $(6,6),\ (2,0)$ | $2$ |
| $7$ | $29$ | $(1,29)$ | $(7,7)$ | $1$ |
| $8$ | $33=3\cdot11$ | $(1,33),\ (3,11)$ | $(8,8),\ (3,2)$ | $2$ |
| $9$ | $37$ | $(1,37)$ | $(9,9)$ | $1$ |
| $10$ | $41$ | $(1,41)$ | $(10,10)$ | $1$ |
| $11$ | $45=3^2\cdot5$ | $(1,45),\ (3,15),\ (5,9)$ | $(11,11),\ (4,3),\ (3,1)$ | $3$ |
| $12$ | $49=7^2$ | $(1,49),\ (7,7)$ | $(12,12),\ (3,0)$ | $2$ |
次が成り立つ。
$$
S_a=\left\lbrace \frac{d+M/d-2}{4}\ \middle|\ d\in\mathbb{Z}_{>0},\ d\mid M,\ d\leqq\sqrt{M}\right\rbrace
$$
ここで $d$ に対応する解に付随する平方根は $m=\frac{M/d-d}{4}$ であり,相異なる $d$ は相異なる解を与える。したがって,$4a+1=\prod_{j=1}^{r}p_j^{e_j}$ と素因数分解するとき
$$
N_a=\left\lceil\frac{\tau(4a+1)}{2}\right\rceil=\left\lceil\frac12\prod_{j=1}^{r}(e_j+1)\right\rceil
$$
である。また,$f_a(n)=0$ となる $n\in S_a$ が存在することと,$M$ が平方数であることは同値である。
$u\leqq v$ と $u^2\leqq uv=M$ は同値であるから $D_M=\lbrace (d,M/d)\mid d\mid M,\ d\leqq\sqrt{M}\rbrace$ であり, 定理2 の逆写像を適用すれば前半を得る。約数は $d\leftrightarrow M/d$ により組になり,自分自身と組になるのは $M$ が平方数で $d=\sqrt{M}$ の場合に限る。$\tau(M)=\prod(e_j+1)$ が奇数であることとすべての $e_j$ が偶数であること,すなわち $M$ が平方数であることは同値であるから,$\sqrt{M}$ 以下の約数の個数は,$M$ が平方数でなければ $\frac{\tau(M)}{2}$,平方数ならば $\frac{\tau(M)+1}{2}$ であり,いずれも $\left\lceil\frac{\tau(M)}{2}\right\rceil$ に等しい。最後の主張は $m=0\iff u=v\iff M=u^2$ による。
系4 のもとで,(2) は「$\left\lceil\frac{\tau(M)}{2}\right\rceil=1\iff\tau(M)=2\iff M$ は素数」($M > 1$ より $\tau(M)\geqq2$)と読める。問題の結論は,解の個数が $4a+1$ の素因数分解の指数だけで決まるというより強い事実の,最も単純な場合である。
以下では $f_a(n)=m^2$($m\in\mathbb{Z}_{\geqq0}$)とする。いずれの証明も「隣り合う整数の間に整数は存在しない」という離散性の異なる現れ方である。
$n\geqq a+1$ と仮定すると
$$
f_a(n)-n^2=n-a\geqq1 > 0,\qquad (n+1)^2-f_a(n)=n+a+1 > 0
$$
より $n^2 < m^2 < (n+1)^2$,すなわち $n < m < n+1$ となり,このような整数 $m$ は存在しない。
(1.1) を $a=n^2+n-m^2$ と読み,$a$ の側を評価する。$n > a$ と仮定すると $n > n^2+n-m^2$,すなわち $m^2 > n^2$ であり,整数性より $m\geqq n+1$。よって
$$
a=n^2+n-m^2\leqq n^2+n-(n+1)^2=-n-1 < 0
$$
となり,$a\geqq1$ に反する。
$n > a$ と仮定すると $m^2-n^2=n-a > 0$ より $m > n$,よって $m-n\geqq1$。一方,$0 < n-a < n$ と $m+n > n$ より
$$
0 < m-n=\frac{m^2-n^2}{m+n}=\frac{n-a}{m+n} < 1
$$
となり矛盾する。実際には $X > a$ において $0 < \sqrt{X^2+X-a}-X < \frac12$ であり,曲線 $Y=\sqrt{X^2+X-a}$ は漸近線 $Y=X+\frac12$ に下から近づく。$X=a$ で $Y=X$ となり,$X > a$ では $Y-X$ が整数になりえない。上界 $n\leqq a$ はこの現象が始まる位置を正確に与えている。
(1.2) のもとで,$m=n$ ならば (1.3) より $n=a$ である。$m\leqq n-1$ ならば 命題3 (b) より $n\leqq\frac{a+1}{3} < a$ である。いずれの場合も $n\leqq a$ であり,結論より強い情報(解の空白区間)が同時に得られる。
$u=2n+1-2m$,$v=2n+1+2m$ とおく。$v\geqq1$ と $uv=M > 0$ から $u > 0$ であり,$u$ は整数なので $u\geqq1$。$uv=M$,$u+v=4n+2$ から (2.1) と同じ計算により
$$
a-n=\frac{(u-1)(v-1)}{4}\geqq0.
$$
隣接平方数を直接用いず,離散性は「正の整数は $1$ 以上である」という形でのみ使われる。等号 $u=1$ は自明解に対応する。
$4f_a(n)=(2n+1)^2-M < (2n+1)^2$ は常に成り立ち,$n > a$ ならば
$$
4f_a(n)-(2n)^2=4n+1-M=4(n-a) > 0
$$
であるから $(2n)^2 < 4f_a(n) < (2n+1)^2$。よって $4f_a(n)$ は平方数でない。$f_a(n)=m^2$ ならば $4f_a(n)=(2m)^2$ であるから,$f_a(n)$ も平方数でない。これは 5.9 節で述べる一般的方法の最も簡単な場合である。
同値性の証明に全単射の全体は要らない。自明解 $n=a$ の存在を前提に,(ii) $\Rightarrow$ (i) の対偶は追加解から非自明な因子分解を作り,(i) $\Rightarrow$ (ii) の対偶は非自明な因子対から追加解を構成すればよい。前者は順方向の因数分解だけで済み,逆向きの整数性の議論は後者でのみ必要になる。
$f_a(a)=a^2$ より $a\in S_a$ であるから,$N_a=1$ は $a$ 以外の解が存在しないことと同値である。
(ii) $\Rightarrow$ (i):対偶を示す。$N_a\geqq2$ とし,$n\in S_a$,$n\neq a$ をとる。(1) より $n < a$ であり,1.2 節より $m\neq n$,よって $0\leqq m\leqq n-1$。このとき
$$
M=(2n+1-2m)(2n+1+2m),\qquad 2n+1+2m\geqq2n+1-2m\geqq3
$$
であるから,$M$ は $3$ 以上の二つの整数の積であり,合成数である。
(i) $\Rightarrow$ (ii):対偶を示す。$M$ が合成数ならば $M=uv$,$1 < u\leqq v$ と書ける。$M$ は奇数であるから $u,v$ は奇数で,
補題1
より $u\equiv v\pmod{4}$。よって $n=\frac{u+v-2}{4}$,$m=\frac{v-u}{4}$ は整数で,$m\geqq0$,また $u,v\geqq3$ より $n\geqq1$。2.2 節 (b) と同じ計算により $n^2+n-m^2=\frac{uv-1}{4}=a$ であるから $n\in S_a$ であり,
$$
a-n=\frac{(u-1)(v-1)}{4} > 0
$$
より $n\neq a$。よって $N_a\geqq2$。
$m\leqq n$ であるから $k=n-m\geqq0$ とおける。$k$ を固定すると (1.1) は $n$ の一次方程式になり,整数性は整除条件に変わる。平方完成を予見しなくても,整除条件を整理する過程で $4a+1$ が自然に現れる。
$n\in S_a$ とし,$k=n-m$ とおく。(1) より $k\geqq0$ である。$m=n-k$ を (1.1) に代入すると $n^2+n-(n-k)^2=a$,すなわち
$$
(2k+1)n=a+k^2 \tag{3.1}
$$
を得る。$n$ は $k$ により $n=\frac{a+k^2}{2k+1}$ と定まるので,対応 $n\mapsto k$ は単射である。$d=2k+1$ とおき,$k\in\mathbb{Z}_{\geqq0}$ がある $n\in S_a$ に対応するための条件を求める。
整数性:$4(a+k^2)=4a+(d-1)^2=M+d(d-2)$ であるから $4(a+k^2)\equiv M\pmod{d}$。$d$ は奇数で $\gcd(d,4)=1$ であるから
$$
d\mid a+k^2\iff d\mid4(a+k^2)\iff d\mid M.
$$
非負性:$m=n-k\geqq0$ は (3.1) により
$$
n\geqq k\iff a+k^2\geqq k(2k+1)\iff a\geqq k^2+k\iff4a+1\geqq(2k+1)^2\iff d\leqq\sqrt{M}.
$$
正値性:$k\geqq1$ ならば $n\geqq k\geqq1$,$k=0$ ならば $n=a\geqq1$ であり,自動的に満たされる。
逆に,$d=2k+1$ が $d\mid M$ と $d\leqq\sqrt{M}$ を満たせば,$n=\frac{a+k^2}{d}$ は正の整数,$m=n-k\geqq0$ であり,$n^2+n-a-(n-k)^2=(2k+1)n-a-k^2=0$ より $f_a(n)=m^2$ である。$M$ の約数はすべて奇数であるから,以上より
$$
S_a\ \longleftrightarrow\ \lbrace d\in\mathbb{Z}_{>0}\mid d\mid M,\ d\leqq\sqrt{M}\rbrace,\qquad n=\frac{a+k^2}{2k+1}\quad\left(k=\frac{d-1}{2}\right)
$$
は全単射である。
$M$ が素数ならば,$M > \sqrt{M}$ より条件を満たす約数は $d=1$ のみであり,$N_a=1$。$M$ が合成数ならば,その最小素因数 $p$ は $p\leqq\sqrt{M}$ を満たし,$d=p$ が $d=1$ とは別の解を与えるので $N_a\geqq2$。ゆえに (i) と (ii) は同値である。
(1.4) の $U=2n+1-2m$,$V=2n+1+2m$ を長方形の辺とみなす。面積 $UV=M$ は $a$ だけで,半周長 $U+V=4n+2$ は $n$ だけで,辺の差 $V-U=4m$ は $m$ だけで決まる。設問 (1) は「面積一定の整数辺長方形の半周長の上限」,設問 (2) は「面積 $M$ の整数辺長方形の種類数」になる。
$n\in S_a$ とし,$U=2n+1-2m$,$V=2n+1+2m$ とおくと,$UV=M$,$U+V=4n+2$,$V-U=4m\geqq0$ である。
(1):$V\geqq1$ と $UV=M > 0$ から $U > 0$ であり,$U$ は整数なので $U\geqq1$。よって $(U-1)(V-1)\geqq0$,すなわち $U+V\leqq UV+1$ であり,
$$
4n+2=U+V\leqq UV+1=4a+2.
$$
ゆえに $n\leqq a$ であり,等号は $U=1$,すなわち $m=n$ のときに限る。面積が一定のとき,整数辺の長方形のうち半周長が最大となるのは最も細長い $1\times M$ であり,これが自明解である。
(2):辺の長さが正の整数 $U\leqq V$ で面積が $M$ の長方形(回転で重なるものは同一視する)の全体は $D_M$ と一致する。上の対応により各 $n\in S_a$ からこのような長方形が定まり,$n$ は半周長から $n=\frac{U+V-2}{4}$ と復元される。逆に,このような長方形 $U\times V$ が与えられたとする。$M$ は奇数だから $U,V$ は奇数であり,
補題1
より $n=\frac{U+V-2}{4}$,$m=\frac{V-U}{4}$ は整数で $m\geqq0$。$U+V\geqq2\sqrt{UV}=2\sqrt{M} > 4$ より $U+V-2$ は正の $4$ の倍数であり,$n\geqq1$。さらに和と差の恒等式 $(U+V)^2-(V-U)^2=4UV$ より
$$
(4n+2)^2-(4m)^2=4M,\qquad\text{すなわち}\qquad(2n+1)^2-(2m)^2=M
$$
であり,$f_a(n)=m^2$ となる。よって $N_a$ は面積 $M$ の整数辺長方形の種類数に等しい。$M$ が素数ならばそれは $1\times M$ のみで $N_a=1$,合成数ならば $1 < U\leqq V$ を満たす長方形 $U\times V$ が存在して $N_a\geqq2$ である。
平方差から長方形への変形は図形的に実現できる。一辺 $X=2n+1$ の正方形の一つの角から一辺 $Y=2m$ の正方形を取り除くと,面積 $M$ の L 字形(グノモン)が残る。これは $(X-Y)\times X$ の長方形と $Y\times(X-Y)$ の長方形に切り分けられ,後者を回転して前者の端に継ぐと $(X-Y)\times(X+Y)=U\times V$ の長方形になる。素数とは,この組み替えで自明な $1\times M$ 以外の長方形を作れない数である。
本解は素数の「正の約数が $1$ と自分自身のみ」という性質を用いた。代わりに「$p\mid xy$ ならば $p\mid x$ または $p\mid y$」というユークリッドの補題(法 $p$ で零因子が存在しないこと)を用いると,因子対を列挙せずに (ii) $\Rightarrow$ (i) が示される。ただし (i) $\Rightarrow$ (ii) には非自明な因子からの構成が必要である。
$n\in S_a$ に対し $X=2n+1$,$Y=2m$ とおくと $X^2-Y^2=M$ である。
(ii) $\Rightarrow$ (i):$M$ を素数とし,$n\in S_a$ とする。$X+Y > 0$ と $(X-Y)(X+Y)=M > 0$ より $X-Y > 0$ であり,$Y\geqq0$ と合わせて $1\leqq X-Y\leqq X+Y$,したがって $X+Y=\frac{M}{X-Y}\leqq M$ である。$M\mid (X-Y)(X+Y)$ であるから,ユークリッドの補題により $M\mid X-Y$ または $M\mid X+Y$ である。
平方数は連続する奇数の和 $N^2=\sum_{j=0}^{N-1}(2j+1)$ である(ピタゴラス学派の図形数)。したがって平方差 $(2n+1)^2-(2m)^2$ は連続する奇数の和であり,「項数 $\times$ 平均」として積が現れる。解の個数は,$M$ を連続する正の奇数の和として表す方法の数になる。
正の奇数 $c$ と正の整数 $L$ について,$c$ から始まる $L$ 個の連続する奇数の和は
$$
\sum_{i=0}^{L-1}(c+2i)=L(c+L-1)
$$
である。$R_M=\lbrace (L,c)\mid L\in\mathbb{Z}_{>0},\ c\text{ は正の奇数},\ L(c+L-1)=M\rbrace$ とおく。
$n\in S_a$ に対し
$$
M=(2n+1)^2-(2m)^2=\sum_{j=2m}^{2n}(2j+1)=(4m+1)+(4m+3)+\cdots+(4n+1)
$$
であり,これは初項 $c=4m+1$,項数 $L=2(n-m)+1$ の連続する奇数の和である。よって $\Lambda(n)=(2(n-m)+1,\ 4m+1)\in R_M$ が定まる。
逆に $(L,c)\in R_M$ とする。$M$ は奇数なので $L$ と $c+L-1$ はともに奇数であり,
補題1
より $L\equiv c+L-1\pmod{4}$,すなわち $c\equiv1\pmod{4}$ である。$m=\frac{c-1}{4}$,$n=m+\frac{L-1}{2}$ とおくと,$n,m$ は $n\geqq m\geqq0$ を満たす整数であり,$2n+1=2m+L$ より $\sum_{j=2m}^{2n}(2j+1)$ は初項 $4m+1=c$,項数 $L$ の和に一致して $M$ に等しい。よって $(2n+1)^2-(2m)^2=M$,すなわち $f_a(n)=m^2$ である。$n=0$ とすると $m=0$,$L=c=1$,$M=1$ となるから $n\geqq1$ であり,$n\in S_a$,$\Lambda(n)=(L,c)$。二つの対応は互いに逆であるから $N_a=\lvert R_M\rvert$ である。
$(L,c)\in R_M$ では $c\geqq1$ より $L\leqq c+L-1$,すなわち $L\leqq\sqrt{M}$ である。$M$ が素数ならば $L=1$,$c=M$ のみであり,$M$ は $2$ 項以上の連続する正の奇数の和として表されないので $N_a=1$。$M$ が合成数ならば,$M=uv$,$1 < u\leqq v$ に対して $(L,c)=(u,\ v-u+1)$ が $R_M$ の第二の元を与え($v-u+1$ は正の奇数),$N_a\geqq2$ である。
以下は導入の仕方が異なるだけで,本解と同じ因子対の全単射に帰着する。
$x=n-m$,$y=n+m$ とおくと,(1.2) より $0\leqq x\leqq y$,$x\equiv y\pmod{2}$ であり,$n=\frac{x+y}{2}$,$m=\frac{y-x}{2}$ である。(1.1) は
$$
a=xy+\frac{x+y}{2},\qquad\text{すなわち}\qquad a-n=xy,\qquad 4a+1=(2x+1)(2y+1)
$$
となり,(1) と (2) が一つの恒等式から読み取れる。$u=2x+1$,$v=2y+1$ であり,偶奇条件 $x\equiv y\pmod{2}$ は $u\equiv v\pmod{4}$(
補題1
)にほかならない。
(1.1) を $n$ の二次方程式 $n^2+n-(a+m^2)=0$ とみると $n=\frac{-1+\sqrt{M+4m^2}}{2}$ であり,$n$ が整数となるための必要十分条件は $M+4m^2$ が平方数であることである($M+4m^2$ は奇数なので,その平方根は奇数となる)。これは $X^2-(2m)^2=M$,すなわち (1.4) に戻る。判別式の計算は平方完成の言い換えである。
$X^2-Y^2=M$ は漸近線 $Y=\pm X$ をもつ直角双曲線であり,漸近線方向の座標 $t=X-Y$,$s=X+Y$ をとると $ts=M$ となる。有理点は $t\in\mathbb{Q}^{\times}$ によって $X=\frac12\left(t+\frac{M}{t}\right)$,$Y=\frac12\left(\frac{M}{t}-t\right)$ と母数表示され,$X > 0$,$Y\geqq0$ を満たす整数点となる条件は,$t$ が $\sqrt{M}$ 以下の $M$ の正の約数であることである(偶奇は 補題1 により自動的に整う)。$t=u$ であり,因子対の言い換えにすぎない。
| 方向 | 帰着先または限界 |
|---|---|
| 微分・増減・凸性 | $f_a$ は $x > -\frac12$ で増加するが,連続的な性質だけでは平方数となる整数点を特定できない。 |
| 複素数・ベクトル | 通常のノルムは平方和を表し,平方差に直接は対応しない。分解型の数を用いると 5.3 節の形になる。 |
| ペル方程式・漸化式 | $X^2-DY^2$ で $D=1$ の分解型であり,無限個の解を生む単数の機構が存在しない(5.3 節)。 |
| 数学的帰納法 | $N_a$ は $4a+1$ の約数構造で決まり,$a$ についての再帰構造をもたない。 |
| 合同式のみ | 素数の場合の一方向は示せるが(参考解2),合成数の場合の構成には因子対が必要である。 |
| 特殊値の観察 | 予想の発見には有効(2.3 節の表)だが,証明には全単射が必要である。 |
| 解法 | 中心となる式 | (1) | (2) | 全解の分類 | 論証の要所 |
|---|---|---|---|---|---|
| 本解 | $uv=M$ | 隣接平方数 | 全単射 | 可 | 逆向きの整数性と境界 $u=v$ |
| 3.1 節 | $m^2 < (n+1)^2$ など | 6 通り | — | — | 整数の離散性 |
| 3.2 節 | $a-n=\frac{(u-1)(v-1)}{4}$ | — | 二方向を個別に | 不要 | 追加解が自明解と異なること |
| 別解1 | $(2k+1)n=a+k^2$ | — | 整除条件 | 可 | $\gcd(d,4)=1$ と $d\leqq\sqrt{M}$ |
| 参考解1 | $UV=M$,$U+V=4n+2$ | 半周長の評価 | 長方形の種類数 | 可 | 図形の直観に逆構成を補う |
| 参考解2 | $M\mid (X-Y)(X+Y)$ | — | 一方向のみ | 不可 | ユークリッドの補題 |
| 参考解3 | $M=\sum_{j=2m}^{2n}(2j+1)$ | — | 奇数和の表し方 | 可 | 初項の範囲と法 $4$ |
完全な分類を与える解法はいずれも,同じ量 $u=2(n-m)+1$(別解1 の $d$,参考解1 の短辺 $U$,参考解3 の項数 $L$,3.7 節の $2x+1$ と $t$)を通じて $D_M$ に到達する。独立な原理は,(1) については整数の離散性,(2) については判別式の平方差表示による因子対の全単射の一つであり,その他は発見の入口の違いである。
本解を主とする理由は三つある。結論の素数が「自明な因子対しかない」という定義に直接接続すること,両方向を一つの全単射で同時に処理できること,そして $N_a=\left\lceil\frac{\tau(M)}{2}\right\rceil$ という一般公式まで得られることである。別解1 は平方完成を予見せずに $4a+1$ へ到達する自然な発見経路であり,3.2 節は試験答案として最短である。
整数係数の多項式 $P$ について,$P(n)$ が平方数(一般に完全冪)となる整数 $n$ の存在・個数・特徴付けを問う問題を対象とする。本問は $P=f_a$ の場合である。
| 観察 | 判断 | 次の行動 |
|---|---|---|
| 平方数・完全冪の条件がある | 補助変数で不定方程式にする | $P(n)=m^2$,$m\geqq0$ とおく |
| 最高次係数が平方数の偶数次式 | 隣接冪の挟み込みで有界になる | $Q(n)^2$ と $(Q(n)+1)^2$ を比較する |
| 最高次係数が平方数でない二次式 | ペル型で解は無限にありうる | 単数による解の生成を調べる |
| 二次式で一次の項がある | 判別式が鍵になる | $4\alpha$ 倍して平方完成する |
| 判別式 $\equiv1\pmod{4}$ | すべての因子対が解に戻る | 補題1 により無条件の全単射を得る |
| 判別式 $\equiv0\pmod{4}$ | 偶奇の制約が残る | 同じ偶奇の因子対に制限する |
| 結論に素数が現れる | 自明な分解のみかを問うている | 自明解と自明な因子対を対応させる |
| 個数を問われる | 全単射で数える | 約数の個数 $\tau$ に帰着させる |
2 章と 3 章の解答は,約数と倍数,素因数分解,約数の個数,剰余の計算という高校数学の範囲で完結している。本章の各項目と高校数学の範囲との関係は次のとおりである。
| 項目 | 節 | 高校数学との関係 |
|---|---|---|
| 判別式による一般化 | 5.2 | 範囲内(証明は本解と同じ) |
| 分解型二次形式とペル方程式 | 5.3 | 範囲外(環,単数群) |
| フェルマーの因数分解法 | 5.4 | 原理は範囲内,現代的な発展は範囲外 |
| 解の順序と最小素因数 | 5.5 | 範囲内 |
| 母数表示,二重線織面,ふるい | 5.6 | ふるいは範囲内,二次曲面論と算術級数定理は範囲外 |
| 生成関数 | 5.7 | 範囲外(形式的冪級数) |
| 平方の合同と素元 | 5.8 | 剰余は範囲内,中国剰余定理と環論は範囲外 |
| 隣接平方数の方法の一般化 | 5.9 | 範囲外(Runge の方法) |
| グノモンと図形数 | 5.10 | 範囲内(歴史的背景) |
本問の構造は,一次の係数が奇数のモニックな二次式全体に及ぶ。
$b$ を奇数,$c$ を整数とし,$g(x)=x^2+bx+c$,$\Delta=b^2-4c$ とおく。このとき $\Delta\equiv1\pmod{4}$ であり,
$$
n\longmapsto\left(2n+b-2\sqrt{g(n)},\ 2n+b+2\sqrt{g(n)}\right)
$$
は $\lbrace n\in\mathbb{Z}\mid g(n)\text{ は平方数}\rbrace$ から $\lbrace (u,v)\in\mathbb{Z}^2\mid uv=\Delta,\ u\leqq v\rbrace$ への全単射である。特に $g(n)$ が平方数となる整数 $n$ の個数は,$\Delta > 0$ のとき $2\left\lceil\frac{\tau(\Delta)}{2}\right\rceil$,$\Delta < 0$ のとき $\tau(\lvert\Delta\rvert)$ である。
$b$ は奇数だから $b^2\equiv1\pmod{4}$,よって $\Delta\equiv1\pmod{4}$ であり,$4g(x)=(2x+b)^2-\Delta$ である。$g(n)=m^2$($m\geqq0$)ならば $u=2n+b-2m$,$v=2n+b+2m$ は $uv=\Delta$,$u\leqq v$ を満たす。逆に $uv=\Delta$,$u\leqq v$ とすると,$u,v$ は奇数で
補題1
より $u\equiv v\pmod{4}$ であるから,$X=\frac{u+v}{2}$ は奇数,$m=\frac{v-u}{4}$ は非負整数,$n=\frac{X-b}{2}$ は整数であり,
$$
g(n)=\frac{X^2-\Delta}{4}=\frac{(u+v)^2-4uv}{16}=\frac{(v-u)^2}{16}=m^2.
$$
二つの対応は互いに逆である。$\Delta > 0$ のとき $u,v$ は同符号で,正の組と負の組は $(u,v)\mapsto(-v,-u)$ で一対一に対応し,それぞれ
系4
の証明と同じく $\left\lceil\frac{\tau(\Delta)}{2}\right\rceil$ 組ある。$\Delta < 0$ のとき $u < 0 < v$ であり,$v$ を $\lvert\Delta\rvert$ の正の約数として任意に選べるから $\tau(\lvert\Delta\rvert)$ 組ある。
本問は $b=1$,$c=-a$,$\Delta=M > 0$ の場合であり,整数解 $2N_a$ 個のうち正のものが $N_a$ 個である(1.4 節)。$\Delta < 0$ の例として $g(x)=x^2+x+1$($\Delta=-3$)では,平方数を与える整数は $n=0,-1$ の $\tau(3)=2$ 個である。
一方,$b$ が偶数のときは $g(n)=m^2\iff\left(n+\frac b2\right)^2-m^2=\Delta'$($\Delta'=\frac{\Delta}{4}=\frac{b^2}{4}-c$)となり,因子対 $uv=\Delta'$ に $u\equiv v\pmod{2}$ という制約が残る。$\Delta'\equiv2\pmod{4}$ なら解はなく,$\Delta'\equiv0\pmod{4}$ なら偶数どうしの因子対だけが解に戻る。このため素数との単純な同値性は成り立たない(1.6 節の $x^2-1$,$x^2-8$)。本問の一次の係数 $1$ は,対応を無条件にする最も簡単な選択である。
$X^2-Y^2$ は有理数の範囲で一次式の積に分解する二次形式(分解型)である。$j^2=1$ を満たす記号 $j$ によって環 $\mathbb{Z}[j]=\lbrace X+Yj\mid X,Y\in\mathbb{Z}\rbrace$ を作ると,ノルム $N(X+Yj)=(X+Yj)(X-Yj)=X^2-Y^2$ は乗法的である。$j\mapsto-1$ と $j\mapsto1$ の二つの環準同型を並べた
$$
\iota:\ \mathbb{Z}[j]\to\mathbb{Z}\times\mathbb{Z},\qquad X+Yj\longmapsto(X-Y,\ X+Y)
$$
は単射であり,像は $\lbrace (u,v)\mid u\equiv v\pmod{2}\rbrace$,ノルムは積 $uv$ に移る。$X+Yj$ を掛ける写像の表現行列 $\begin{pmatrix}X&Y\\ Y&X\end{pmatrix}$ の固有値が $X\pm Y$,行列式が $X^2-Y^2$ であることは,この分解の行列による表現である。したがってノルム方程式 $X^2-Y^2=M$ は $uv=M$ となり,その解は $M$ の約数で尽くされて有限である。1.4 節の符号反転は,ノルム $1$ の単数 $\pm1$ の乗法と共役 $X+Yj\mapsto X-Yj$ が生成する位数 $4$ の群である。
対照的に,$D$ が平方数でない正の整数のとき,$\mathbb{Z}[\sqrt{D}]$ は零因子をもたず,ペル方程式 $X^2-DY^2=1$ は無限個の整数解をもつ(ラグランジュ)。そのため $X^2-DY^2=M$ は,解を一つでももてば単数倍によって無限個の解をもつ。本問の有限性(設問 (1))と約数への帰着(設問 (2))は,いずれも $D=1$ という分解型であることに由来する。
正の整数 $X$ について,$X^2-M$ が平方数であることと,ある $n\in S_a$ により $X=2n+1$ と表されることは同値である。したがって,フェルマーの因数分解法で $X=\lceil\sqrt{M}\rceil,\ \lceil\sqrt{M}\rceil+1,\ \dots,\ \frac{M+1}{2}$ の順に $X^2-M$ が平方数かを調べることは,$n$ を小さい順に動かして $f_a(n)$ が平方数かを調べることと同じであり,探索範囲の上端は (1) の上界 $n\leqq a$ に,下端は 命題3 (a) の下界に一致する。
$X$ が偶数ならば $X^2-M\equiv-1\equiv3\pmod{4}$ であり,平方数は法 $4$ で $0$ または $1$ に合同であるから,$X^2-M$ は平方数でない。$X=2n+1$($n\geqq0$)ならば $X^2-M=4f_a(n)$ である。$f_a(n)=m^2$ ならば $4f_a(n)=(2m)^2$。逆に $4f_a(n)=Y^2$ ならば $Y$ は偶数で $f_a(n)=\left(\frac Y2\right)^2$。$n=0$ は $f_a(0) < 0$ により除かれる。範囲については,$X^2\geqq M$ は $n\geqq\frac{\sqrt{M}-1}{2}$ と,$X\leqq\frac{M+1}{2}$ は $n\leqq a$ と同値である。
$M$ が素数ならば,探索は終端 $X=\frac{M+1}{2}$($n=a$,自明な分解 $1\cdot M$)で初めて成功する。合成数ならばそれより前に成功し,最初に成功する $X$ は $\sqrt{M}$ に最も近い因子対,すなわち最小の解 $n$ に対応する。フェルマー自身が扱った例として知られる $2027651281=44021\cdot46061$ は $4$ で割って $1$ 余り,$a=506912820$ に対応する。このとき $S_a=\lbrace 22520,\ a\rbrace$,$f_a(22520)=510^2$ であり,探索は $\lceil\sqrt{M}\rceil=45030$ から数えて $12$ 番目の $X=45041=2\cdot22520+1$ で成功する。
フェルマー法は $X^2-Y^2=M$ を整数として解くが,これを法 $M$ の合同 $X^2\equiv Y^2\pmod{M}$,$X\not\equiv\pm Y$ に緩めると,$\gcd(X-Y,M)$ が非自明な約数を与える。この考え方(クライチック)は,ディクソン法や二次ふるい法など現代の素因数分解アルゴリズムの基礎になっている(5.8 節)。
$M$ の約数 $d$($1\leqq d\leqq\sqrt{M}$)に対応する解を $n(d)=\frac{d+M/d-2}{4}$ と書く(
系4
)。$n(d)$ は $d$ について狭義単調減少である。したがって $S_a$ の元を大きい順に $n_1 > n_2 > \cdots$ と並べると $n_1=a$ であり,$M$ が合成数ならば,$M$ の最小素因数 $p$ を用いて
$$
n_2=\frac{p+M/p-2}{4},\qquad a-n_2=\frac{(p-1)(M/p-1)}{4}
$$
が成り立つ。さらに $n_2\leqq\frac{a+1}{3}$ であり,等号は $p=3$ のときに限る。また $d=2k+1$ に対応する解は $n=\frac{a+k^2}{2k+1}$ であり,$k=n-m$ である。
$0 < d_1 < d_2\leqq\sqrt{M}$ ならば $d_1d_2 < M$ であるから
$$
\left(d_1+\frac{M}{d_1}\right)-\left(d_2+\frac{M}{d_2}\right)=(d_2-d_1)\left(\frac{M}{d_1d_2}-1\right) > 0.
$$
$1$ の次に小さい $M$ の約数は最小素因数 $p$ であり,$M$ が合成数ならば $p\leqq\sqrt{M}$ である。$a-n_2$ は (2.1) で $(u,v)=(p,M/p)$ とすればよい。$p\geqq3$,$3\leqq\sqrt{M}$ と(実数 $d$ に対する)同じ単調性から $n_2\leqq\frac{3+M/3-2}{4}=\frac{M+3}{12}=\frac{a+1}{3}$ であり,等号は $p=3$ のときに限る。最後の主張は $\frac{d+M/d-2}{4}=\frac{d^2-2d+M}{4d}=\frac{4k^2+4a}{4(2k+1)}$ と,$d=u=2(n-m)+1$ による。
解の位置は $M$ の因数分解を記録している。最大の非自明解 $n_2$ から,$p$ は二次方程式 $p+\frac{M}{p}=4n_2+2$ の小さい方の根として復元される。 命題3 (b)(c) の空白区間とその端点は,この命題の $p\geqq3$ と $p=3$ の場合にあたる。反対側では,最小の解は $\sqrt{M}$ に最も近い因子対に対応し, 命題6 のフェルマー法が最初に見つける分解に一致する。
(a) 正の整数 $a,n$ と非負整数 $m$ の組で $f_a(n)=m^2$ を満たすものの全体は
$$
(a,n,m)=\bigl(k(k+1)+(2k+1)t,\ k+t,\ t\bigr)\qquad\bigl(k,t\in\mathbb{Z}_{\geqq0},\ (k,t)\neq(0,0)\bigr)
$$
によって重複なく与えられる。ここで $k=n-m$,$t=m$ であり,$4a+1=(2k+1)(2k+1+4t)$ である。
(b) $N_a\geqq2$ となる正の整数 $a$ の全体は
$$
\bigcup_{k\geqq1}\bigl\lbrace k(k+1)+(2k+1)t\ \bigm|\ t\in\mathbb{Z}_{\geqq0}\bigr\rbrace=\bigcup_{p\text{:奇素数}}\left\lbrace \frac{p^2-1}{4}+pt\ \middle|\ t\in\mathbb{Z}_{\geqq0}\right\rbrace
$$
に等しい。
(a) 解 $(a,n,m)$ に対して $k=n-m\geqq0$((1.2)),$t=m\geqq0$ とおくと
$$
a=(k+t)^2+(k+t)-t^2=k(k+1)+(2k+1)t.
$$
逆に $(k,t)\neq(0,0)$ ならば,$k\geqq1$ のとき $a\geqq k(k+1)\geqq2$,$k=0$ のとき $a=t\geqq1$ であり,$n=k+t\geqq1$ で $f_a(n)=t^2$ となる。二つの対応は互いに逆である。$4a+1=(2k+1)(2k+1+4t)$ は直接計算による。
(b) 固定した $a$ の解は (a) の $(k,t)$ と一対一に対応し,$k=0$ は $m=n$,すなわち自明解にあたる。よって $N_a\geqq2$ は $k\geqq1$ の表示が存在することと同値であり,左の等式を得る。$p=2k+1$ とおけば $\frac{p^2-1}{4}=k(k+1)$ であるから,右辺は左辺に含まれる。逆に $a$ が左辺に属すれば $M=(2k+1)(2k+1+4t)$ は合成数であり,その最小素因数 $p$ は $p^2\leqq M$ を満たす。$q=\frac{M}{p}\geqq p$ は奇数で,
補題1
より $q\equiv p\pmod{4}$ であるから $q=p+4t'$($t'\geqq0$)と書け,$a=\frac{pq-1}{4}=\frac{p^2-1}{4}+pt'$ となる。
(a) は幾何学的にも読める。$(n,m,a)$ 空間の曲面 $a=n^2+n-m^2$ は双曲放物面であり,二つの直線族で覆われる(二重線織面)。$k=n-m$ を固定すると $a=k(k+1)+(2k+1)m$,$s=n+m$ を固定すると $a=s(s+1)-(2s+1)m$ となり,いずれも $m$ の一次式である。曲面上の格子点を通る二本の母線の番号 $2k+1$,$2s+1$ について $(2k+1)(2s+1)=4a+1$ が成り立つ。すなわち因子対 $(u,v)$ とは,格子点を通る二本の母線の番号の組である。
(b) は,法 $4$ で $1$ に合同な数の列 $4a+1$ に制限したエラトステネスのふるいである。各奇素数 $p$ は,$4a+1$ が $p$ の倍数で $p^2$ 以上となる項,すなわち $a\equiv\frac{p^2-1}{4}\pmod{p}$,$a\geqq\frac{p^2-1}{4}$ の項をふるい落とす。残る $a$($N_a=1$)はちょうど $4a+1$ が素数となるものであり,$4$ で割って $1$ 余る素数が無数に存在すること(ディリクレの算術級数定理の特別な場合で,初等的な証明もある)から,$N_a=1$ となる $a$ は無数に存在する。
形式的冪級数として
$$
\sum_{a=1}^{\infty}N_az^a=\frac{z}{1-z}+\sum_{k=1}^{\infty}\frac{z^{k(k+1)}}{1-z^{2k+1}}
$$
が成り立つ。特に右辺第 $2$ 項の $z^a$ の係数は $N_a-1$ であり,それが $0$ であることと $4a+1$ が素数であることは同値である。
命題8
(a) より,$N_a$ は $k(k+1)+(2k+1)t=a$ を満たす $(k,t)\in\mathbb{Z}_{\geqq0}^2$ の個数に等しい($a\geqq1$ では $(k,t)\neq(0,0)$ は自動的に成り立つ)。各 $a$ についてこのような組は有限個($k(k+1)\leqq a$)であるから,
$$
\sum_{a=1}^{\infty}N_az^a=\sum_{k=0}^{\infty}\sum_{t=0}^{\infty}z^{k(k+1)+(2k+1)t}-1=\sum_{k=0}^{\infty}\frac{z^{k(k+1)}}{1-z^{2k+1}}-1
$$
は形式的冪級数として意味をもつ。$k=0$ の項から $1$ を引いたものが $\frac{1}{1-z}-1=\frac{z}{1-z}$ である。後半は $\frac{z}{1-z}$ の各係数が $1$ であることと設問 (2) による。
第 $1$ 項 $\frac{z}{1-z}$ は自明解の寄与を,第 $2$ 項は非自明解の寄与を表す。第 $2$ 項は等差数列 $\lbrace k(k+1)+(2k+1)t\rbrace_{t\geqq0}$ の母関数の和であり, 命題8 (b) のふるいを係数の言葉で書いたものである。
参考解2 はユークリッドの補題を,本解は「約数が自明なものに限る」ことを用いた。一般の整域では,前者の性質をもつ元(素元)は後者の性質をもつ元(既約元)であるが,逆は成り立たないことがある。たとえば $\mathbb{Z}[\sqrt{-5}]$ では $2\cdot3=(1+\sqrt{-5})(1-\sqrt{-5})$ であり,$2$ は既約だが素元でない。$\mathbb{Z}$ ではベズーの等式からユークリッドの補題が従い,二つの特徴付けが一致するので,本解と参考解2 はどちらも正しい。参考解2 が一方向しか与えない理由は,次の命題で説明される。
奇数 $M > 1$ について,次の二条件は同値である。
(a) $M$ は素数である。
(b) 整数 $X,Y$ が $X^2\equiv Y^2\pmod{M}$ を満たせば,$X\equiv Y$ または $X\equiv-Y\pmod{M}$ である。
(a) $\Rightarrow$ (b):$M\mid (X-Y)(X+Y)$ とユークリッドの補題による。(b) $\Rightarrow$ (a):対偶を示す。$M$ を合成数とする。$M$ が相異なる二つ以上の素因数をもつときは,$M=rs$,$\gcd(r,s)=1$,$r,s\geqq3$ と分け,中国剰余定理により $X\equiv1\pmod{r}$,$X\equiv-1\pmod{s}$ を満たす $X$ をとる。$Y=1$ とすると $X^2\equiv1\equiv Y^2\pmod{M}$ であるが,$X\equiv-1\not\equiv1\pmod{s}$ より $X\not\equiv1$,$X\equiv1\not\equiv-1\pmod{r}$ より $X\not\equiv-1\pmod{M}$。$M=p^e$($p$ は奇素数,$e\geqq2$)のときは $X=p^{\lceil e/2\rceil}$,$Y=0$ とすると,$X^2\equiv0\equiv Y^2$ であるが $\lceil e/2\rceil < e$ より $X\not\equiv0\pmod{M}$。
$M$ が合成数のとき,法 $M$ には (b) に反する「余分な平方根」が存在し,$X^2\equiv Y^2$,$X\not\equiv\pm Y$ を満たす組からは $\gcd(X-Y,M)$ として非自明な約数が得られる(5.4 節)。参考解2 の (ii) $\Rightarrow$ (i) は (a) $\Rightarrow$ (b) の特別な場合であり,逆向きには合同ではなく整数としての因子対の構成が必要になる。
$P\in\mathbb{Z}[x]$ が偶数次 $2r$ で,最高次係数が平方数であり,$\mathbb{Q}[x]$ の多項式の平方でないとする。このとき $P(n)$ が平方数となる整数 $n$ は有限個である。実際,$\deg(P-Q^2) < r$ を満たす $Q\in\mathbb{Q}[x]$($\deg Q=r$)がとれ,$LQ\in\mathbb{Z}[x]$ となる正の整数 $L$ をとると,$\deg L^2(P-Q^2) < \deg LQ$ より,$\lvert x\rvert$ が十分大きいとき $(\lvert LQ(x)\rvert-1)^2 < L^2P(x) < (\lvert LQ(x)\rvert+1)^2$ となる。$P(x)=y^2$ ならば,整数 $L\lvert y\rvert$ の平方がこの区間に入るから $L\lvert y\rvert=\lvert LQ(x)\rvert$,すなわち $P(x)=Q(x)^2$ となるが,$P-Q^2$ は零でない多項式であるから,そのような $x$ は有限個である。これは Runge の方法の最も簡単な場合である。
本問では $Q(x)=x+\frac12$,$L=2$ であり,$4f_a(x)=(2x+1)^2-M$ は $x > a$ で $(2x)^2$ と $(2x+1)^2$ の間に入る(3.1 節 (f))。設問 (1) の上界 $n\leqq a$ は,この一般論で「十分大きい」とされる範囲を明示したものである。
$$
\begin{array}{c}
f_a(n)=m^2\quad(n\geqq1,\ m\geqq0)\\[6pt]
\swarrow\hspace{8em}\searrow\\[6pt]
\begin{array}{c}
\text{隣接平方数}\\
m^2 < (n+1)^2\\
\Downarrow\\
0\leqq m\leqq n\\
\Downarrow\\
a-n=(n-m)(n+m)\geqq0\\
\Downarrow\\
\text{(1)}\ \ n\leqq a
\end{array}
\qquad\qquad
\begin{array}{c}
\text{判別式}\\
4f_a(n)=(2n+1)^2-M\\
\Downarrow\\
uv=M\quad(u\leqq v)\\
\Downarrow\ \ \text{法 }4\text{(補題1)}\\
S_a\ \leftrightarrow\ D_M\\
\Downarrow\\
N_a=\left\lceil\tau(M)/2\right\rceil\\
\Downarrow\\
\text{(2)}\ \ N_a=1\iff M\text{ は素数}
\end{array}
\end{array}
$$
各解法で同じ量がどのように現れるかを整理する。
| 解法 | $u=2(n-m)+1$ の現れ方 | $v=2(n+m)+1$ の現れ方 |
|---|---|---|
| 本解 | 因子対の小さい方 | 因子対の大きい方 |
| 別解1 | 約数 $d=2k+1$ | 共役な約数 $M/d$ |
| 参考解1 | 長方形の短辺 $U$ | 長方形の長辺 $V$ |
| 参考解2 | $X-Y$ | $X+Y$ |
| 参考解3 | 奇数和の項数 $L$ | 奇数和の平均 $c+L-1$ |
| 3.7 節 | $2x+1$,双曲線の母数 $t$ | $2y+1$,$M/t$ |
| 5.6 節 | 母線 $n-m=k$ の番号 $2k+1$ | 母線 $n+m=s$ の番号 $2s+1$ |