Ramanujan–Nagell方程式

同義語:Ramanujan-Nagell方程式ラマヌジャン–ナーゲル方程式Ramanujan–Nagell equationRamanujan-Nagell equationRamanujan–Nagellの定理Ramanujan–Nagell theorem

概要

Ramanujan–Nagell方程式(Ramanujan–Nagell equation)とは、整数 $x$ と非負整数 $n$ についての不定方程式 $x^2+7=2^n$ のことで、解は $n=3,4,5,7,15$($\lvert x\rvert=1,3,5,11,181$)だけである。1913 年に Ramanujan が問い、Nagell が解いた。$\mathbb Q(\sqrt{-7})$ の整数環で $2=\alpha\beta$ と分解すると、方程式は整数列 $u_m=(\alpha^m-\beta^m)/(\alpha-\beta)$ が $\pm1$ になる番号の問題に移り、法 $4$ と $7$ 進付値で解が決まる。$2^k-1$ の形の三角数や、半径 $2$ の Hamming 球の大きさが $2$ の冪になる長さもここから決まる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 2次体, 一意分解整域, p進付値

Ramanujan–Nagell方程式(Ramanujan–Nagell equation)は、整数 $x$ と非負整数 $n$ についての不定方程式
$$ x^2+7=2^n $$
である。解は $(n,\lvert x\rvert)=(3,1),(4,3),(5,5),(7,11),(15,181)$ の 5 組だけである。
1913 年、S. Ramanujan は Journal of the Indian Mathematical Society の問題欄(第 5 巻 p. 120、問題 464)で、$2^n-7$ が $n=3,4,5,7,15$ で平方数になることを指摘し、ほかの $n$ を求めよと問うた。ほかの $n$ がないことは T. Nagell が初めて証明したとされる(Elk99 p. 78 と脚注 12)。この主張を Ramanujan–Nagell の定理 という。
左辺 $x^2+7$ は、2 次体 $\mathbb Q(\sqrt{-7})$ の元 $\frac{x+\sqrt{-7}}2$ のノルムの $4$ 倍で、$2$ はこの体で 2 つの素元の積に分かれる。この記事では、整数環の素因数分解で方程式を 1 つの整数列の値の問題に移し、その列を法 $4$ と $7$ 進の大きさで調べて、解が上の 5 組に限ることを完全に証明する。応用として、$2^k-1$ の形の三角数と、2 個の誤りを訂正する二元の完全符号の長さを決める。

方程式と整数列への言い換え

小さい解と 2 つの言い換え

$x\mapsto-x$ で解は移り合うので $x\ge0$ としてよい。$n\le2$ では $2^n-7< 0$ なので解はない。$n\ge3$ では $x^2=2^n-7$ は奇数なので $x$ は奇数である。

5 組の解

$1+7=8=2^3$、$9+7=16=2^4$、$25+7=32=2^5$、$121+7=128=2^7$、$181^2+7=32761+7=32768=2^{15}$。

$x=2t+1$ とおくと $x^2+7=4(t^2+t+2)$ なので、方程式は
$$ \frac{t(t+1)}2=2^{n-3}-1 $$
と同値である。左辺は 三角数 なので、$2^k-1$ の形の三角数は $k=0,1,2,4,12$ のときの $0,1,3,15,4095$ だけ という主張と、Ramanujan–Nagell の定理は同じものである($4095=\frac{90\cdot91}2$)。
また $\ell\ge0$ について $(2\ell+1)^2+7=8\bigl(1+\ell+\binom \ell2\bigr)$ なので、$1+\ell+\binom \ell2$ が $2$ の冪になることは、$x=2\ell+1$ が方程式の解になることと同値である。$1+\ell+\binom \ell2$ は、長さ $\ell$ の二元の語のうち、ある語との Hamming 距離が $2$ 以下のものの個数で、完全符号 の理論に現れる(節「応用」)。Elk99 p. 78 もこの言い換えに触れている。

整数環と整数列

$K=\mathbb Q(\sqrt{-7})$ の整数環を $\mathcal O$ とする。$-7\equiv1\pmod4$ なので $\mathcal O=\{\frac{s+t\sqrt{-7}}2: s,t\in\mathbb Z,\ s\equiv t\pmod 2\}$ で、ノルムは $N\bigl(\frac{s+t\sqrt{-7}}2\bigr)=\frac{s^2+7t^2}4$ である(2次体)。次の事実を使う。

  1. $\mathcal O$ はノルムで Euclid な整域であり(2次体 の定理「ノルムで Euclid な虚 2 次体」)、したがって単項イデアル整域、一意分解整域 である(Euclid整域 の命題「Euclid整域は単項イデアル整域である」)。
  2. $\mathcal O$ の単数は $\pm1$ だけである。$\frac{s^2+7t^2}4=1$ なら $t=0$、$s=\pm2$ だからである。
2 つの素元と整数列

$$ \alpha:=\frac{1+\sqrt{-7}}2,\qquad \beta:=\bar\alpha=\frac{1-\sqrt{-7}}2 $$
とおく。$\alpha+\beta=1$、$\alpha\beta=2$、$\alpha-\beta=\sqrt{-7}$ である。$m\ge0$ について
$$ u_m:=\frac{\alpha^m-\beta^m}{\alpha-\beta},\qquad v_m:=\alpha^m+\beta^m $$
と定める。

$\alpha,\beta$ は $X^2-X+2$ の根なので、$u_m,v_m$ は漸化式
$$ u_0=0,\ u_1=1,\ u_{m+1}=u_m-2u_{m-1};\qquad v_0=2,\ v_1=1,\ v_{m+1}=v_m-2v_{m-1} $$
を満たし、どれも整数である。最初の値は次のとおり。

$m$012345678910111213
$u_m$011$-1$$-3$$-1$57$-3$$-17$$-11$2345$-1$
$v_m$21$-3$$-5$1119$-13$$-31$$-5$5767$-47$$-181$

$\alpha^m=\frac{v_m+u_m\sqrt{-7}}2$ であり、ノルムをとると $v_m^2+7u_m^2=4\cdot2^m$ である。$\lvert u_m\rvert=1$ のところで $\lvert v_m\rvert$ が $1,3,5,11,181$ になっている。
$\alpha$ と $\beta$ はノルムが素数 $2$ なので $\mathcal O$ の素元であり、$\alpha/\beta=\frac{\alpha^2}2=\frac{-3+\sqrt{-7}}4\notin\mathcal O$ なので互いに同伴でない。$2=\alpha\beta$ は $2$ の素因数分解である。

方程式の言い換え

$n\ge3$ とし、$x$ を $x^2+7=2^n$ を満たす整数とする。$m:=n-2$ とおくと $u_m=\pm1$ であり、$\lvert x\rvert=\lvert v_m\rvert$ である。逆に $u_m=\pm1$ なら $x=v_m$ は $x^2+7=2^{m+2}$ を満たす。

2 つの共役が素元を分け合う

$x$ は奇数なので $\gamma:=\frac{x+\sqrt{-7}}2\in\mathcal O$ であり、
$$ \gamma\bar\gamma=\frac{x^2+7}4=2^{m}=\alpha^m\beta^m $$
である。$\alpha$ が $\gamma$ と $\bar\gamma$ の両方を割るとすると、$\alpha$ は $\gamma-\bar\gamma=\sqrt{-7}$ を割り、ノルムを比べて $2\mid7$ となり矛盾する。$\beta$ についても同じである。
$\mathcal O$ は一意分解整域で、$\gamma$ の素因子は $\gamma\bar\gamma$ を割るので $\alpha,\beta$ と同伴なものに限る。単数は $\pm1$ なので、$\gamma=\varepsilon\alpha^i\beta^j$($\varepsilon=\pm1$、$i,j\ge0$)と書け、共役をとって $\bar\gamma=\varepsilon\beta^i\alpha^j$ である。積を比べて $i+j=m$ を得る。$i\ge1$ かつ $j\ge1$ なら $\alpha$ が $\gamma$ と $\bar\gamma$ の両方を割るので、上で見たとおり矛盾する。よって $\gamma=\varepsilon\alpha^m$ または $\gamma=\varepsilon\beta^m$ である。
$\gamma=\varepsilon\alpha^m$ なら、$\sqrt{-7}=\gamma-\bar\gamma=\varepsilon(\alpha^m-\beta^m)=\varepsilon u_m\sqrt{-7}$ から $u_m=\varepsilon$ である。$\gamma=\varepsilon\beta^m$ なら同様に $u_m=-\varepsilon$ である。どちらでも $x=\gamma+\bar\gamma=\varepsilon v_m$ である。
逆に $u_m=\pm1$ なら、$v_m^2+7u_m^2=4\cdot2^m$ から $v_m^2+7=2^{m+2}$ である。$\square$

この補題で、方程式は「$u_m=\pm1$ となる $m\ge1$ を求めよ」という問題になる。

主定理

Ramanujan–Nagell の定理

整数 $x$ と非負整数 $n$ が $x^2+7=2^n$ を満たすのは、
$$ (n,\lvert x\rvert)=(3,1),\ (4,3),\ (5,5),\ (7,11),\ (15,181) $$
のときに限る。

証明の段取り

$n$ が偶数の場合は整数の範囲で終わる(lem-rn-even)。$n$ が奇数なら $m=n-2$ も奇数で、lem-rn-reduction により $u_m=\pm1$ を調べればよい。符号を法 $4$ で決め(lem-rn-sign)、$u_m=-1$ となる番号を $7$ 進付値で絞る(lem-rn-uniqueness)。証明は prf-rn-main にまとめる。

$n$ が偶数の場合

$n=2k$ のとき、解は $k=2$、$\lvert x\rvert=3$ だけである。

$x\ge0$ としてよい。$(2^k-x)(2^k+x)=7$ で、$2^k+x>0$ なので $2^k-x>0$ でもあり、$2^k+x\ge2^k-x$ である。$7$ は素数なので $2^k-x=1$、$2^k+x=7$ で、足して $2^{k+1}=8$、$k=2$、$x=3$ である。$\square$

符号は負

$m\ge2$ のとき、$m$ が偶数なら $u_m\equiv1\pmod4$、奇数なら $u_m\equiv3\pmod4$ である。とくに奇数の $m\ge3$ で $u_m=\pm1$ なら $u_m=-1$ である。

漸化式を法 4 で見る

$u_2=1$、$u_3=-1\equiv3$ である。$m\ge3$ で $(u_{m-1},u_m)\equiv(1,3)\pmod4$ なら $u_{m+1}=u_m-2u_{m-1}\equiv3-2=1$、$(u_{m-1},u_m)\equiv(3,1)$ なら $u_{m+1}\equiv1-6\equiv3$ である。$m$ についての帰納法で主張が従う。$u_m\equiv3\pmod4$ なら $u_m\ne1$ である。$\square$

$u_m=-1$ を整数の等式に書き直す。二項定理で
$$ \alpha^m-\beta^m=\frac{(1+\sqrt{-7})^m-(1-\sqrt{-7})^m}{2^m}=\frac{2\sqrt{-7}}{2^m}\sum_{j\ge0}\binom m{2j+1}(-7)^j $$
なので、$S(m):=\sum_{j\ge0}\binom m{2j+1}(-7)^j$ とおくと $S(m)=2^{m-1}u_m$ であり、
$$ u_m=-1\iff S(m)=-2^{m-1} $$
である($m\ge1$)。

法 3 での一意性

$m\ne m'$ を正の整数とし、どちらも等式 $S(m)=-2^{m-1}$ を満たすとする。このとき $m\not\equiv m'\pmod 3$ である。

7 進付値を比べる

$m> m'$、$3\mid m-m'$ と仮定して矛盾を導く。$l:=v_7(m-m')\ge0$ とおく($v_7$ は p進付値)。
右辺の差.$3\mid m-m'$ なので $L:=\frac{m-m'}3$ は正の整数で、$v_7(L)=l$ である。$2^3=1+7$ なので
$$ 2^{m-m'}-1=(1+7)^L-1=\sum_{i=1}^{L}\binom Li7^i $$
である。$i=1$ の項 $7L$ の 7 進付値は $1+l$ である。$i\ge2$ では $\binom Li=\frac Li\binom{L-1}{i-1}$ から $v_7\binom Li\ge l-v_7(i)$ で、$7^i$ の付値は $i$ なので、項の付値は $l+i-v_7(i)$ 以上で、これは $l+2$ 以上である($2\le i< 7$ では $v_7(i)=0\le i-2$、$i\ge7$ では $v_7(i)\le\log_7i\le i-2$)。よって $2^{m-m'}\equiv1\pmod{7^{l+1}}$ で、
$$ S(m)-S(m')=-2^{m-1}+2^{m'-1}=-2^{m'-1}\bigl(2^{m-m'}-1\bigr)\equiv0\pmod{7^{l+1}} $$
である。
左辺の差.$k\ge1$ について $P_k(t):=t(t-1)\cdots(t-k+1)$ は整数係数の多項式なので、$m-m'$ は $P_k(m)-P_k(m')$ を割る。$\binom mk-\binom{m'}k=\frac{P_k(m)-P_k(m')}{k!}$ なので
$$ v_7\Bigl(\binom mk-\binom{m'}k\Bigr)\ge l-v_7(k!) $$
である。$j\ge1$ について $k=2j+1$ とすると、Legendre の公式 $v_7(k!)=\sum_{s\ge1}\lfloor k/7^s\rfloor< \frac k6$ から $v_7((2j+1)!)< \frac{2j+1}6\le j$、すなわち $v_7((2j+1)!)\le j-1$ である。よって
$$ v_7\Bigl((-7)^j\Bigl(\binom m{2j+1}-\binom{m'}{2j+1}\Bigr)\Bigr)\ge j+l-(j-1)=l+1 $$
である。$j=0$ の項は $m-m'$ なので
$$ S(m)-S(m')\equiv m-m'\pmod{7^{l+1}} $$
を得る。$v_7(m-m')=l$ なので右辺は $7^{l+1}$ で割れず、右辺の差の計算と矛盾する。$\square$

偶奇で分けて番号を絞る

$x\ge0$ としてよく、$n\le2$ に解はない。$n$ が偶数なら lem-rn-even により $(n,x)=(4,3)$ である。
$n\ge3$ を奇数とし、$m:=n-2$ とおく。lem-rn-reduction により $u_m=\pm1$ で、$x=\lvert v_m\rvert$ である。$m=1$ なら $n=3$、$x=\lvert v_1\rvert=1$ である。$m\ge3$ なら、lem-rn-sign により $u_m=-1$ で、上の同値により $S(m)=-2^{m-1}$ である。
表から $u_3=u_5=u_{13}=-1$ なので、$m=3,5,13$ も $S(m)=-2^{m-1}$ を満たし、これらは法 $3$ でそれぞれ $0,2,1$ である。どの $m$ についても、$m$ と法 $3$ で合同な $m'\in\{3,5,13\}$ がある。lem-rn-uniqueness により $m=m'$ である。よって $m\in\{3,5,13\}$、すなわち $n\in\{5,7,15\}$ で、$x=\lvert v_m\rvert=5,11,181$ である。
逆に、表の 5 組が解であることは ex-rn-solutions で確かめた。$\square$

証明の組み立てについて

2 次体の分解で得られる $u_m=\pm1$ という条件は、漸化式で決まる整数列の値についての条件である。lem-rn-uniqueness では、番号が法 $3$ で合同なとき、$S(m)$ の差の $7$ 進付値は番号の差の $7$ 進付値にちょうど等しく、$2^{m-1}$ の差の付値はそれより真に大きくなるので、両者は等しくなれない。素数 $7$ を使うのは、$7$ が $\alpha-\beta=\sqrt{-7}$ のノルムで、$S(m)$ の展開で $j\ge1$ の項がすべて $7$ の冪を含むからである。法 $3$ は $2$ の法 $7$ での位数である。Nagell の証明は Nag61 にある。

応用

$2^k-1$ の形の三角数

非負整数 $t,k$ について $\frac{t(t+1)}2=2^k-1$ となるのは、$(k,t)=(0,0),(1,1),(2,2),(4,5),(12,90)$ のときに限る。

節「方程式と整数列への言い換え」で見たとおり、$x=2t+1$ とおくと条件は $x^2+7=2^{k+3}$ と同値である。thm-rn-main により $x\in\{1,3,5,11,181\}$、$k+3\in\{3,4,5,7,15\}$ で、$t=\frac{x-1}2\in\{0,1,2,5,90\}$ である。$\square$

$2^k-1$ は Mersenne素数 の候補となる数の形なので、この系は「三角数になる $2^k-1$ は $1,3,15,4095$ だけ」とも読める($k\ge1$)。
符号の言葉では次のようになる。$\mathbb F_2^\ell$ の各点を中心とする半径 $2$ の Hamming 球の点の個数は $V_2(\ell,2)=1+\ell+\binom \ell2$ で、二元の 2 個の誤りを訂正する符号が完全符号であるためには、完全符号 の定理「Hamming の限界」の等号から $V_2(\ell,2)$ が $2^\ell$ を割ること、すなわち $2$ の冪であることが必要である。

半径 2 の Hamming 球の大きさ

$V_2(\ell,2)=1+\ell+\binom \ell2$ が $2$ の冪となる非負整数 $\ell$ は、$\ell=0,1,2,5,90$ だけである。

$(2\ell+1)^2+7=4\ell^2+4\ell+8=8\bigl(1+\ell+\binom \ell2\bigr)$ なので、$V_2(\ell,2)=2^r$ は $(2\ell+1)^2+7=2^{r+3}$ と同値である。thm-rn-main により $2\ell+1\in\{1,3,5,11,181\}$ である。$\square$

$\ell=0,1,2$ では符号語 1 個の自明な場合、$\ell=5$ は長さ $5$ の反復符号 $\{00000,11111\}$ である。$\ell=90$ では $V_2(90,2)=4096=2^{12}$ なので個数の条件は満たされるが、長さ $90$ の 2 個の誤りを訂正する二元完全符号は存在しない(完全符号 の命題「長さ 90 の二元完全符号の非存在」)。完全符号 の記事が有限の範囲の計算で挙げている $\ell=1,2,5,90$ は、上の系により $\ell\ge1$ のすべてである。

関連する方程式

Mordell 方程式との関係と一般化を開く

$n=3k+j$($j\in\{0,1,2\}$)と書き、$y:=2^k$ とおくと、解は曲線 $x^2=2^jy^3-7$ の整数点を与える。さらに $X:=2^jy$、$Y:=2^jx$ とおけば $Y^2=X^3-7\cdot4^j$ の整数点になり、各 $j$ ごとに Mordell方程式 $Y^2=X^3+D$($D=-7,-28,-112$)の整数点の問題に帰着する。Mordell 方程式の整数点は有限個であるが(Mordell方程式 の定理「整数解の有限性」)、そこからは具体的な解の一覧は出てこない。上の証明は、$y$ が $2$ の冪であることを使って解を決めきっている。

右辺を $2^n$ から、決まった有限個の素数の積で表される整数 $y$ に替えた方程式 $x^2+b=c\,y$ は、一般化された Ramanujan–Nagell 方程式と呼ばれる。$q$ 元($q$ は素数冪でない)の 2 個の誤りを訂正する完全符号があれば、この形の方程式の解が得られる(Caz24 pp. 5–6)。

反例

外した仮定・とり替えた条件反例成り立たなくなる結論
lem-rn-uniqueness の $m\equiv m'\pmod3$$m=5$、$m'=3$(どちらも $S(m)=-2^{m-1}$)$m=m'$
lem-rn-sign の「$m$ が奇数」$m=2$$u_m=\pm1$ なら $u_m=-1$
lem-rn-sign の「$m\ge3$」$m=1$$u_m=\pm1$ なら $u_m=-1$

1 行目:$S(3)=3-7=-4=-2^2$、$S(5)=5-70+49=-16=-2^4$ で、どちらも等式を満たすが $5\ne3$ である。$5-3=2$ は $3$ で割れず、合同の仮定だけが外れている。2 行目:$u_2=\alpha+\beta=1$ で、$u_2=\pm1$ だが $u_2\ne-1$ である(lem-rn-sign の偶数の場合のとおり $1\pmod4$)。3 行目:$u_1=1$ で、$m=1$ は奇数だが $u_1\ne-1$ である。主定理の証明で $m=1$($n=3$)を別に扱ったのはこのためである。

関連項目

参考文献

[1]
Noam D. Elkies, The Klein quartic in number theory, S. Levy (ed.), The Eightfold Way: The Beauty of Klein's Quartic Curve, MSRI Publications 35, Cambridge University Press,, 1999, p. 78(式 (3.16) $x^2+7=2^n$、Hamming 球との関係、Ramanujan の観察、Nagell が初めて解いたこと)と脚注 12(J. Indian Math. Soc. 5 (1913) p. 120 の問題 464 の文面)
[2]
Trygve Nagell, The Diophantine equation x²+7=2ⁿ, Arkiv för Matematik 4 (1961), no. 2–3, pp. 185–187. DOI 10.1007/BF02592006, 1961
[3]
Pedro-José Cazorla García, Perfect codes over non-prime power alphabets: an approach based on Diophantine equations, Mathematics (MDPI) 12(11) (2024), 1642. DOI 10.3390/math12111642, 2024, arXiv 版 v2、pp. 5–6(§2、式 (10)–(15):2 個の誤りを訂正する完全符号の条件から一般化された Ramanujan–Nagell 方程式へ)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する