0

2025年 東京大学 理系 第4問

2
0
$$$$
2025年 東京大学 理系 第4問

この問いでは,$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$ は素数である。


1. 問題の構造

1.1 記法

本稿では次の記号を用いる。

  • 平方数は問題文の定義に従い,$0=0^2$ を含む。
  • $M=4a+1$ とおく。$a\geqq1$ より $M\geqq5$ であり,$M\equiv1\pmod{4}$ である。
  • $S_a=\lbrace n\in\mathbb{Z}_{>0}\mid f_a(n)\text{ は平方数}\rbrace$ とおく。$N_a=\lvert S_a\rvert$ である。
  • $n\in S_a$ に対し,$f_a(n)=m^2$ を満たす $m\in\mathbb{Z}_{\geqq0}$ はただ一つ定まる。以下,$n\in S_a$ に付随する $m$ は常にこの値を表す。
  • $D_M=\lbrace (u,v)\in\mathbb{Z}_{>0}^2\mid uv=M,\ u\leqq v\rbrace$ を $M$ の正の因子対の集合とし,$(1,M)$ を自明な因子対と呼ぶ。
  • 正の整数 $N$ の正の約数の個数を $\tau(N)$ と書く。

1.2 平方数条件の翻訳と隣接平方数

正の整数 $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) から次が従う。

  • $n\leqq a$ であり(設問 (1)),等号は $m=n$ のときに限る。
  • $f_a(a)=a^2$ であるから,$a\in S_a$ は常に成り立つ。これを自明解と呼ぶ。
    したがって $S_a\subset\lbrace 1,2,\dots,a\rbrace$,$1\leqq N_a\leqq a$ であり,条件 (i) は $S_a=\lbrace a\rbrace$,すなわち自明解以外に解が存在しないことと同値である。設問 (1) は $N_a$ が有限な値として定まることも保証している。

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}$ から次の補題によって保証される。

奇数の積と法 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))。

1.4 対称性と正規化

$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). $$

  • $m\geqq0$ とすることは,$Y\geqq0$,すなわち $u\leqq v$ を選ぶことにあたる。
  • $n\geqq0$ とすることは,$X > 0$,すなわち $u,v > 0$ を選ぶことにあたる。$f_a(0)=-a < 0$ であるから,これは $n\geqq1$ と同じである。
    したがって問題文の「正の整数 $n$」と「$0$ 以上の整数の $2$ 乗」という二つの条件は,この対称性による正規化にほかならず,数える対象をちょうど $D_M$ に一致させている。$f_a(n)$ が平方数となる整数 $n$ の全体は $S_a\cup\lbrace -1-n\mid n\in S_a\rbrace$ であり,ちょうど $2N_a$ 個ある。

1.5 解の配置

設問 (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 節)。

1.6 作問の設計

以下は数値設定と設問構成からの分析であり,出題者の意図についての推定を含む。

  • 判別式としての $4a+1$:(ii) の $4a+1$ は $f_a$ の判別式であり,平方完成の過程で必然的に現れる。結論の形そのものが「$4$ 倍して平方完成せよ」という誘導になっている。
  • 一次の係数を奇数にする:一次の係数が奇数であるため $M\equiv1\pmod{4}$ となり, 補題1 によってすべての因子対が解に戻る。一次の係数が偶数の場合,たとえば $g(x)=x^2-c$ では $n^2-m^2=c$ の因子対に偶奇の制約が課され,素数との同値性は崩れる。実際,$c=1$ では正の解は $n=1$ のみ,$c=8$ では $n=3$ のみであるが,いずれの $c$ も素数でない(5.2 節)。
  • 自明解の埋め込み:$f_a(a)=a^2$ は自明な因子対 $(1,M)$ に対応する。これにより $N_a\geqq1$ が常に成り立ち,(i) は「非自明な解がない」,(ii) は「非自明な因子対がない」という同型の主張になる。
  • $0$ を平方数に含める定義:この定義は (2) が成り立つために必要である。仮に $0$ を除くと,$m=0$ に対応する因子対 $(s,s)$($M=s^2$)が失われる。$M=p^2$($p$ は奇素数)のとき $D_M=\lbrace (1,p^2),(p,p)\rbrace$ であるから,$a=\frac{p^2-1}{4}$ はすべて反例になる。最小の例は $a=2$ で,$f_2(1)=0$,$f_2(2)=4$,$M=9$ である。
  • $a\geqq1$ と設問 (1) の役割:$a\geqq1$ は不等式 $m^2 < (n+1)^2$ の根拠であり,$M\geqq5$ を保証して「$\tau(M)=2\iff M$ は素数」を成り立たせる。設問 (1) は $S_a$ の有限性,したがって $N_a$ が定義されることを保証し,同時に (2) で用いる $m\leqq n$($u\geqq1$)を与える。
  • 正の整数への制限:1.4 節のとおり,これは対称性 $n\leftrightarrow-1-n$ による正規化であり,数える対象を $D_M$ に一致させる条件である。
  • 主題:奇数 $M > 1$ が素数であることと,$M$ を平方数の差 $X^2-Y^2$($X > Y\geqq0$)として表す方法がただ一通りであることは同値であり,これはフェルマーの因数分解法の原理である(5.4 節)。本問はこの古典的事実を,パラメータ $a$ を含む二次式の値の平方数判定として書き直したものと解釈できる。

1.7 構造と解法の対応

着目する構造数学的翻訳対応する解法
隣接平方数の間隔$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 節

2. 本解:平方差の因数分解と因子対の全単射

2.1 方針

  1. は平方根 $m$ を隣接平方数と比較して $m\leqq n$ を導き,(1.1) に戻す。(2) は自明解 $n=a$ を確認したうえで,判別式による平方差表示 (1.4) から $S_a$ と $D_M$ の全単射( 定理2 )を構成する。逆向きの整数性は $M\equiv1\pmod{4}$ と 補題1 が保証し,境界 $u=v$($m=0$)も含めて対応させる。$N_a=\lvert D_M\rvert$ となるので,同値性は素数の定義に帰着する。

2.2 解答

(1)

$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$ である。

(2)

$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) は同値である。

2.3 検証・検算

  • 自明解:$n=a$ では $m=a$ であり,$\Phi(a)=(1,4a+1)$。(2.1) で $u=1$ とすると $a-n=0$ となり整合する。
  • 境界 $m=0$:$u=v$ の因子対を除外すると,$M$ が平方数のときに解を失う。$a=2$ では $(3,3)$ が $n=1$,$f_2(1)=0$ に対応する。
  • 法 $4$ の整合:$M=45$ の非自明な因子対 $(3,15)$,$(5,9)$ はそれぞれ $3\equiv15\equiv3$,$5\equiv9\equiv1\pmod{4}$ を満たす。
  • 対称性:$a=11$ のとき,$f_{11}(n)$ が平方数となる整数 $n$ は $11,4,3$ と $-12,-5,-4$ の $6=2N_{11}$ 個である(1.4 節)。
  • 解の配置:下表で $a\equiv2\pmod{3}$ となる $a=2,5,8,11$ では,それぞれ $n=\frac{a+1}{3}=1,2,3,4$ が解であり, 命題3 (c) と一致する。
  • 網羅的確認:$1\leqq a\leqq3000$ について $N_a$ を定義どおり数え上げ,$N_a=\lvert D_M\rvert$ および「$N_a=1\iff M$ は素数」が成り立つことを計算機で確認した。
    $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$

2.4 系:全解の明示と個数公式

全解の明示と個数公式

次が成り立つ。
$$ 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$ の素因数分解の指数だけで決まるというより強い事実の,最も単純な場合である。

3. 別解と参考解

3.1 (1) の別証

以下では $f_a(n)=m^2$($m\in\mathbb{Z}_{\geqq0}$)とする。いずれの証明も「隣り合う整数の間に整数は存在しない」という離散性の異なる現れ方である。

(a) 背理法:隣接平方数による挟み込み

$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$ は存在しない。

(b) 主客転倒:パラメータを評価する

(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$ に反する。

(c) 有理化:漸近線との距離

$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$ はこの現象が始まる位置を正確に与えている。

(d) 二分法:自明解か否か

(1.2) のもとで,$m=n$ ならば (1.3) より $n=a$ である。$m\leqq n-1$ ならば 命題3 (b) より $n\leqq\frac{a+1}{3} < a$ である。いずれの場合も $n\leqq a$ であり,結論より強い情報(解の空白区間)が同時に得られる。

(e) 因子対の正値性

$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$ は自明解に対応する。

(f) 判別式表示による挟み込み

$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 節で述べる一般的方法の最も簡単な場合である。

検証・検算

  • 鋭さ:すべての $a$ で $n=a$ が解であるから,上界 $n\leqq a$ は改良できない。(a)〜(f) はいずれも等号を $m=n$($u=1$)の場合にのみ許しており,これと整合する。
  • (c) の数値例:$a=1$,$n=2$ では $f_1(2)=5$ であり,$\sqrt5-2\approx0.236$ は区間 $\left(0,\frac12\right)$ に入る。
  • (d) の数値例:$a=11$ の非自明解 $4,3$ はいずれも $\frac{a+1}{3}=4$ 以下である。

3.2 (2) の他の導出:自明解と追加解の二分

着想・方針

同値性の証明に全単射の全体は要らない。自明解 $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$。

検証・検算

  • (ii) $\Rightarrow$ (i) の対偶で得る因子 $2n+1-2m$ は,$a=11$ では $n=4$ に対して $3$,$n=3$ に対して $5$ であり,$45$ の非自明な約数を与える。
  • (i) $\Rightarrow$ (ii) の対偶で $M=33$($a=8$)を $3\cdot11$ と分解すると $n=3$,$m=2$ であり,$f_8(3)=4$。
  • この二分は, 定理2 の単射性・全射性のうち同値性に必要な部分だけを取り出したものである。

3.3 別解1:平方根との差による整除条件

着想・方針

$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) は同値である。

検証・検算

  • $a=11$:$\sqrt{45}\approx6.7$ 以下の $45$ の約数 $d=1,3,5$ から $k=0,1,2$,$n=\frac{11}{1},\frac{12}{3},\frac{15}{5}=11,4,3$ を得る。
  • 境界 $d=\sqrt{M}$:$a=2$ では $d=3=\sqrt9$,$k=1$,$n=\frac{2+1}{3}=1$,$m=0$。条件 $d\leqq\sqrt{M}$ の等号を除外してはならない。
  • 素数の例:$a=3$ では $M=13$ の約数で $\sqrt{13}\approx3.6$ 以下のものは $1$ のみであり,$N_3=1$。
  • 本解との一致:$\frac{a+k^2}{2k+1}=\frac{d+M/d-2}{4}$ が成り立ち,$d=2(n-m)+1$ は本解の $u$ にほかならない。

3.4 参考解1:長方形の面積・周長とグノモン

着想・方針

(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$ 以外の長方形を作れない数である。

検証・検算

  • $a=11$:$1\times45$,$3\times15$,$5\times9$ の半周長 $46,18,14$ から $n=11,4,3$,辺の差 $44,12,4$ から $m=11,3,1$ を得る。
  • $m=0$ は正方形 $U=V$ に対応する。$a=2$ では $3\times3$ の正方形が $n=1$ を与える。
  • 図形の直観だけでは $n,m$ の整数性は保証されず,法 $4$ の条件が逆構成に不可欠である。実際,$15\equiv3\pmod{4}$ を面積とする $3\times5$ からは $n=\frac32$ となり,解は生じない。

3.5 参考解2:素数の素元性による (ii) ⇒ (i)

着想・方針

本解は素数の「正の約数が $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$ である。

  • $M\mid X-Y$ ならば $M\leqq X-Y\leqq X+Y\leqq M$ より $X-Y=X+Y=M$ となり,$M^2=M$ に反する。
  • よって $M\mid X+Y$ であり,$1\leqq X+Y\leqq M$ から $X+Y=M$,$X-Y=1$。すなわち $2(n-m)+1=1$,$m=n$ であり,(1.3) より $n=a$。
    したがって $S_a=\lbrace a\rbrace$,$N_a=1$ である。
    (i) $\Rightarrow$ (ii):対偶を示す。$M$ が合成数ならば,3.2 節と同じく非自明な因子対 $(u,v)$ から $n=\frac{u+v-2}{4}\in S_a$,$n < a$ が構成され,$N_a\geqq2$ となる。

検証・検算

  • $a=3$($M=13$):$n=3$ で $X=7$,$Y=6$,$X-Y=1$,$X+Y=13$ となる。
  • 合成数では議論が働かない:$a=2$($M=9$)の解 $n=1$ では $X=3$,$Y=0$ であり,$9\mid 3\cdot3$ だが $9\nmid3$。法 $9$ には $3\cdot3\equiv0$ という零因子があり,ユークリッドの補題が成り立たない。この方法が一方向しか与えないのはこの非対称性による(5.8 節)。

3.6 参考解3:連続する奇数の和

着想・方針

平方数は連続する奇数の和 $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$ である。

検証・検算

  • $45=13+15+17=5+7+9+11+13$ と $45$ 自身の三通りが,$(L,c)=(1,45),(3,13),(5,5)$ を経て $(n,m)=(11,11),(4,3),(3,1)$ に対応する。
  • $m=0$ は $c=1$,すなわち $1+3+\cdots+(2L-1)=L^2$ に対応し,$M$ が平方数の場合と整合する。$a=2$ では $9=1+3+5$ である。
  • 初項が常に $c\equiv1\pmod{4}$ となることは, 補題1 の別の現れである。また上の議論は,正の奇数 $M > 1$ が素数であることと,$M$ を $2$ 項以上の連続する正の奇数の和として表せないことの同値性を示している。

3.7 同じ系列に属する変形

以下は導入の仕方が異なるだけで,本解と同じ因子対の全単射に帰着する。

和と差の変数

$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 節の表)だが,証明には全単射が必要である。

3.8 解法の比較

解法中心となる式(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 節は試験答案として最短である。

4. 汎用的な探索手順

4.1 対象

整数係数の多項式 $P$ について,$P(n)$ が平方数(一般に完全冪)となる整数 $n$ の存在・個数・特徴付けを問う問題を対象とする。本問は $P=f_a$ の場合である。

4.2 手順

  1. 定義域と正規化を確定する。平方数に $0$ を含むか,$n$ の符号と範囲,$P$ の対称性(本問では $P(-1-x)=P(x)$)を確認する。境界の扱いは結論の真偽を左右しうる(1.6 節)。
  2. 補助変数を導入する。$P(n)=m^2$($m\geqq0$)とおき,二変数の不定方程式に移す。
  3. 有界性を確保する。$P$ が偶数次で最高次係数が平方数ならば,$P(n)$ を隣接する平方数で挟む。二次式では,最高次係数 $\alpha$ の $4$ 倍を掛けた $4\alpha P(n)$ を挟むのが最も確実である(3.1 節 (f))。最高次係数が平方数でなければペル型であり,有限性は一般に期待できない(5.3 節)。
  4. 自明解を探す。恒等的に平方数を与える点(本問では $n=a$)を見つけ,主張を「自明解以外の解」についての命題に書き換える。
  5. 結論の対象から逆算する。素数は「非自明な因子分解の不存在」,約数の個数は「全単射の存在」,合成数は「非自明な分解の構成」として読む。
  6. 平方完成で判別式を取り出す。$P(x)=\alpha x^2+\beta x+\gamma$ に対し $4\alpha P(x)=(2\alpha x+\beta)^2-\Delta$($\Delta=\beta^2-4\alpha\gamma$)であるから,$\alpha$ が平方数ならば $P(n)=m^2$ は「平方差 $=\Delta$」となり,一次因子の積に分解される。
  7. 対応を両方向で検査する。逆向きでは,偶奇と合同条件(本問では法 $4$),符号,大小,境界($m=0$,$n\geqq1$)をすべて確認する。
  8. 対応先で数える。全単射が得られれば,個数は対応先の集合(因子対)の個数として計算でき,一般公式が得られる。
  9. 要求に合わせて圧縮する。試験答案では同値性に必要な方向だけを示せばよい(3.2 節)。
  10. 見かけと本質を区別する。複数の解法が同一の量(本問では $u=2(n-m)+1$)に帰着するかを判定し,独立な原理と言い換えを分ける。

4.3 判断の分岐

観察判断次の行動
平方数・完全冪の条件がある補助変数で不定方程式にする$P(n)=m^2$,$m\geqq0$ とおく
最高次係数が平方数の偶数次式隣接冪の挟み込みで有界になる$Q(n)^2$ と $(Q(n)+1)^2$ を比較する
最高次係数が平方数でない二次式ペル型で解は無限にありうる単数による解の生成を調べる
二次式で一次の項がある判別式が鍵になる$4\alpha$ 倍して平方完成する
判別式 $\equiv1\pmod{4}$すべての因子対が解に戻る補題1 により無条件の全単射を得る
判別式 $\equiv0\pmod{4}$偶奇の制約が残る同じ偶奇の因子対に制限する
結論に素数が現れる自明な分解のみかを問うている自明解と自明な因子対を対応させる
個数を問われる全単射で数える約数の個数 $\tau$ に帰着させる

5. 発展事項

5.1 高校数学との境界

2 章と 3 章の解答は,約数と倍数,素因数分解,約数の個数,剰余の計算という高校数学の範囲で完結している。本章の各項目と高校数学の範囲との関係は次のとおりである。

項目節高校数学との関係
判別式による一般化5.2範囲内(証明は本解と同じ)
分解型二次形式とペル方程式5.3範囲外(環,単数群)
フェルマーの因数分解法5.4原理は範囲内,現代的な発展は範囲外
解の順序と最小素因数5.5範囲内
母数表示,二重線織面,ふるい5.6ふるいは範囲内,二次曲面論と算術級数定理は範囲外
生成関数5.7範囲外(形式的冪級数)
平方の合同と素元5.8剰余は範囲内,中国剰余定理と環論は範囲外
隣接平方数の方法の一般化5.9範囲外(Runge の方法)
グノモンと図形数5.10範囲内(歴史的背景)

5.2 判別式による一般化

本問の構造は,一次の係数が奇数のモニックな二次式全体に及ぶ。

判別式による一般化

$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$ は,対応を無条件にする最も簡単な選択である。

5.3 分解型の二次形式:ペル方程式との対比

$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$ という分解型であることに由来する。

5.4 フェルマーの因数分解法

フェルマー法との一致

正の整数 $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 節)。

5.5 解の順序と最小素因数

解の順序と最小素因数

$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 のフェルマー法が最初に見つける分解に一致する。

5.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$ は無数に存在する。

5.7 生成関数

生成関数

形式的冪級数として
$$ \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) のふるいを係数の言葉で書いたものである。

5.8 平方の合同と素元

参考解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) の特別な場合であり,逆向きには合同ではなく整数としての因子対の構成が必要になる。

5.9 隣接平方数の方法の一般化

$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$ は,この一般論で「十分大きい」とされる範囲を明示したものである。

5.10 グノモンと図形数

  • 正方形にグノモン(L 字形)を付け加えて次の正方形を作る操作は,$k^2=1+3+\cdots+(2k-1)$ というピタゴラス学派の図形数の考え方であり,参考解3 の基礎である。
  • 平方差を長方形に組み替える操作は,ユークリッド『原論』第 2 巻命題 5 の内容(線分を等しい部分と等しくない部分に分けるとき,等しくない部分が作る長方形と分点間の線分上の正方形の和は半分の上の正方形に等しい)にあたり,代数的には $(X+Y)(X-Y)+Y^2=X^2$ である。その証明にグノモンが用いられる(参考解1)。
  • 平方差による表示が「素数ならただ一通り」であるのに対し,平方和では,$4$ で割って $1$ 余る素数が二つの正の平方数の和として(順序を除き)ただ一通りに表されること(フェルマーが主張しオイラーが証明)が知られ,二通りの表示から因数を求めるオイラーの因数分解法がある。本問の $4a+1$ は判別式として現れたものであり,二平方和定理とは無関係である。両者を混同しないよう注意する。

6. 最終整理

6.1 構造マップ

$$ \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$

6.2 数学的教訓

  • 平方数条件は補助変数 $m\geqq0$ によって不定方程式に翻訳する。平方数に $0$ を含むかという定義は境界解 $m=0$ の有無を決め,本問では (2) の真偽そのものを左右する。
  • 隣接平方数の比較は有界性を与える。比較を一段精密化する($m\leqq n-1$)と,非自明解の空白区間 $\frac{a+1}{3} < n < a$ が得られる。
  • 二次式の平方数判定では,最高次係数の $4$ 倍を掛けて平方完成し,判別式を取り出す。平方差は一次因子の積になり,問題は約数の問題に移る。結論に現れる $4a+1$ はこの判別式である。
  • 全単射は両方向で示す。逆向きでは偶奇と法 $4$ の合同,符号,境界($u=v$,$n\geqq1$)を点検する。本問では $M\equiv1\pmod{4}$ がすべての因子対を解に戻す。
  • 結論に素数が現れたら「非自明な分解が存在しない」と読み,自明解と自明な分解を対応させる。
  • 個数は対応先で数える。本問は $N_a=\left\lceil\frac{\tau(4a+1)}{2}\right\rceil$ という一般公式で解決し,(2) はその最も単純な場合である。
  • 差の変数,判別式,長方形,奇数の和,双曲線,母線はいずれも同じ量 $u=2(n-m)+1$ を別の名で呼んだものである。発見の入口の多様さと分類原理の同一性を区別する。
  • 素数の二つの特徴付け(約数が自明なものに限ること,ユークリッドの補題)は $\mathbb{Z}$ では一致するが,論証の中で果たす役割は異なる。
投稿日:2日前
数学の力で現場を変える アルゴリズムエンジニア募集 - Mathlog served by OptHub

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

医学部・難関大受験生の指導を行っています。

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中