インテジャーズ

読者です 読者をやめる 読者になる 読者になる

インテジャーズ

数、特に整数に関する記事。

n^2+(n+1)^2に関するシェルピンスキーの定理

昨夜、次の問題がTwitterのTLで話題になっていました。


この問題に興味がある方は挑戦してみてください(大学入試問題に出来る程度の難易度?)。

この記事ではn^2+(n+1)^2が素数になることと三角数のとある関係性(Sierpińskiの定理)を紹介したいと思います。

三角数\displaystyle T_n=\frac{n(n+1)}{2}に関して最近書いた記事としては
integers.hatenablog.com
があります(幾つかの数値が掲載されています)。

次が紹介したい定理です:

定理 (Sierpiński) n^2+(n+1)^2が合成数であることと、或る自然数m, lが存在して
T_n=T_m+T_l
が成り立つことは同値である。

例えば、T_8=36, \ T_{10}=55, \ T_{13}=91なので

T_{13}=T_{8}+T_{10}

が成り立ちますが、

13^2+14^2=169+196=365

は確かに合成数です。

一方、T_{19}=190は(先ほどの数値表を眺めれば分かるように)二つの三角数の和として表すことはできず、

19^2+20^2=761

は確かに素数になっています。

互いに素な二平方和に関する定理

integers.hatenablog.com
において、「自然数が二つの平方数の和として表されるための必要十分条件はその自然数の素因数分解に現れる4n+3型素数の指数が全て偶数であること」を証明しました*1

実は、「二つの平方数が互いに素である」という条件を課した場合についても精密な定理が知られています:

定理 自然数が二つの互いに素な平方数の和として表されるための必要十分条件は、その自然数が奇数または単偶数(4で割れないような偶数)であり、4n+3型の素因数を持たないことである。更に、自然数Nがその条件を満たすとき、N=a^2+b^2 (a, bは互いに素な整数)と書き表す方法の場合の数を\rho_2(N)とすると、\rho_2(N)=2^{t+2}が成り立つ。ただし、tN4n+1型素因数の個数を表す。

例えば、25=5^2の場合にチェックしてみましょう。先の記事で紹介したJacobiの定理を用いるとr_2(25)=12となり*2、実際

25=0^2+(\pm 5)^2=(\pm 5)^2+0^2=(\pm 3)^2+(\pm 4)^2=(\pm 4)^2+(\pm 3)^2

12通りの二平方和としての表示があることが分かりますが、互いに素という条件をつけると

25=(\pm 4)^2+(\pm 7)^2=(\pm 7)^2+(\pm 4)^2

8通りになり、上記定理から導かれる\rho_2(25)=2^{1+2}=8に合致します。

この定理の証明はそれなりの準備が必要なので、ここでは紹介しません。将来的に書けると嬉しいですが、とりあえずNiven-Zuckerman-Montgomeryの"An introduction to the theory of numbers"の§3.6を参考文献としてあげておきます。

Sierpińskiの定理の証明

f(n)=n^2+(n+1)^2とおく。

f(n)=pが素数のとき T_n=T_m+T_lなる自然数m, lが存在したと仮定して矛盾を導く。m \geq lと仮定してよい。このとき

\displaystyle \frac{n(n+1)}{2}=\frac{m(m+1)}{2}+\frac{l(l+1)}{2}

であり、

p=n^2+(n+1)^2 = (m-l)^2+(m+l+1)^2 ー①

と変形できる。素数pが二平方和として表されているのでp4n+1型であるが、そのような素数を二平方和として表す方法は本質的に*3一通りのはずである。

しかしながら、①の後者の表現については(m+l+1)-(m-l)=2l+1 > 1と二数の差が1より大なので、前者の表現とは相異なる。これは矛盾である。

f(n)=Nが合成数のとき 次の主張を示す:

主張 2Nは或る奇数u, v(ただし、ともに3以上)を用いて、2N=u^2+v^2と表すことができる。

Nを互いに素な二つの平方数の和として表す方法が本質的に二通り以上存在する場合
一つは

N=n^2+(n+1)^2

であり、それとは異なる互いに素な二平方和としての表示を

N=a^2+b^2

とする(a, bは互いに素(或いはNが奇数)なので、b > aとしてよい)。このとき、差b-a1ではないので、b-a > 1である。従って、

2N=(b-a)^2+(a+b)^2

が主張を示している。というのも、Nは奇数なのでa, bのパリティは異なり、b-aおよびa+bはともに3以上の奇数となるからである。

Nを互いに素な二つの平方数の和として表す方法が本質的に一通りの場合
これは前節の定理を用いれば、4n+1型の素数pおよび自然数eを用いてN=p^eと表される場合であることが分かる(本質的に一通り\Longleftrightarrow \rho_2(N)=8であることに注意)。今、Nは合成数なのでe \geq 2である。

eが偶数の場合
e=2e'とおくと、

2N=2p^{2e'}=(p^{e'})^2+(p^{e'})^2

より主張が成立する。

eが奇数の場合
e=2e'+1とおく(e' \geq 1)。p4n+1型素数なので

p=a^2+b^2

と二平方和で表すことができる(a, bは自然数。b > aとしてよい)。pは奇数なので、a, bのパリティは異なる。このとき、

2N=2p^e= (p^{e'}(b-a) )^2+(p^{e'}(a+b) )^2

より主張が成立する(b-a=1の可能性はあるのであって、e' \geq 1が重要)。

以上で、主張が証明された(Nの定義からNを互いに素な二つの平方数の和として表す方法は少なくとも一通りはあることに注意せよ)。

すると、自然数m, lが存在してu=2m+1, \ v=2l+1と書ける。このとき、2N=u^2+v^2

2(n^2+(n+1)^2)=(2m+1)^2+(2l+1)^2

と表され、変形すると

T_n=T_m+T_l

が得られる。 Q.E.D.

*1:平方数には0を含みます。また、1の素因数分解は全ての素数に対する指数が0と考えることにします。そうすると、10^2+1^2などと二つの平方数の和として表されることに矛盾しません。

*2:4n+1型の約数の個数から4n+3型の約数を引いて4倍する。この場合、4n+3型の約数はなく、4n+1型の約数は1, 5, 253個である。

*3:符号や順番の違いを除いての意。