続・二平方定理 (オイラーの 6n+1 定理)

前回の記事：
平方剰余の第一補充則から二平方定理を導く - tsujimotterのノートブック

昨日書いた「フェルマーの二平方定理」の話ですが，定理をもっと一般化できることに気づきました。ワクワクしながらこの記事を書いています。

昨日は

「 $4n+1$ 型の素数は $x^2+y^2$ の形で表せること」

を示しました。

今日の記事では，

「ほかの形の素数でも同様の定理は成り立つか」

について考えたいと思います。

結論を先に言ってしまうと，

「 $6n+1$ 型の素数は $x^2+3y^2$ の形で表せる」

が成り立ちます。

これを示すことを目指しましょう。

方針

昨日の記事の過程で，以下の補題を証明しました。

補題１：
$\left( \frac{-1}{p} \right) = 1$ のとき，すなわち $i^2 \equiv -1 \pmod p$ が成り立つ $i$ が存在するとき，

$(x+iy)\equiv 0 \pmod p$
を満たす $x, y$ が存在する。ただし， $x, y$ は $0 < |x| < \sqrt{p}$ ， $0 < |y| < \sqrt{p}$ を満たす整数である。

上の補題では $(-1)$ を使っていますが，必ずしも $(-1)$ である必要はありません。つまり，一般に $a$ としても同様の議論が成り立ちます。

$(-1)$ の部分を $a$ に置き換えてみると，次のような命題が成り立つことがわかるでしょう。

補題２：
$\left( \frac{a}{p} \right) = 1$ のとき，すなわち $i^2 \equiv a \pmod p$ が成り立つ $i$ が存在するとき，

$(x+iy)\equiv 0 \pmod p$
を満たす $x, y$ が存在する。ただし， $x, y$ は $0 < |x| < \sqrt{p}$ ， $0 < |y| < \sqrt{p}$ を満たす整数である。

このままいけるところまで進めていきましょう。
まず，両辺に $(x-iy)$ を掛けます。

$(x+iy)(x-iy) \equiv 0 \pmod p$

これを展開します。

$x^2-i^2y^2 \equiv 0 \pmod p$

仮定 $i^2 \equiv a \pmod p$ より，

$x^2-ay^2 \equiv 0 \pmod p$

あとは， $a$ に具体的に値を入れて，不等式を評価して（右辺） $= p$ となることを示せば良いわけです。具体的に $a$ に値を入れてみると，冒頭で述べた平方和の公式が作れます。

それでは， $a = -3$ でやってみましょう。

$a = -3$ の場合

$\left( \frac{-3}{p} \right) = 1$ について考えます。平方剰余の相互法則から，

$\displaystyle \left( \frac{-3}{p} \right) = 1 \Longleftrightarrow p = 6n+1, p = 3$

が成り立ちます。これが成り立つ理由については，最後に述べたいと思いますが，まずは成り立つとして考えましょう。

また，補題２より

$x^2+3y^2 \equiv 0 \pmod p$

となるような $x, y$ （ただし， $0 < |x| < \sqrt{p}$ ， $0 < |y| < \sqrt{p}$ ）が存在します。

左辺を不等式で評価すると，

$0 < x^2+3y^2 < 4p$

となりますから，右辺の候補は $p, 2p, 3p$ のいずれかですね。 $p$ の場合は，目的の式となりますから， $2p, 3p$ の場合を検討しましょう。

(i) $x^2+3y^2 = 2p$ の場合:
$p = 6n+1$ と $p = 3$ の２パターンで考えます。

$p = 6n+1$ の場合，

$x^2 + 3y^2 = 12n + 2$

${\rm mod} \; 3$ で考えると，

$x^2 \equiv 2 \pmod 3$

となる。ここで ${\rm mod} \; 3$ では，

$0^2 \equiv 0 \pmod 3$

$1^2 \equiv 1 \pmod 3$

$2^2 \equiv 1 \pmod 3$

より， $x^2 \equiv 2 \pmod 3$ となる $x$ は存在しません。

一方， $p = 3$ の場合，

$x^2 + 3y^2 = 6$

この式を満たすような， $x, y$ は存在しません。

よって，いずれの場合も不適です。

(ii) $x^2+3y^2 = 3p$ の場合:
この場合，両辺 $3$ で割ると，

$\displaystyle 3\left( x/3 \right)^2 + y^2 = p$

となります。もし， $x$ が $3$ の倍数であれば，目的の式が成り立つことがわかります。

ここで， $x^2+3y^2 = 3p$ の式に対して， ${\rm mod} \; 3$ で考えると，

$x^2 \equiv 0 \pmod 3$

上の議論において， $x^2 \equiv 0$ となるのは $x \equiv 0$ であるから， $x$ は $3$ の倍数となります。

したがって， $x/3 = x'$ とおくと，

$3x'^2+y^2 = p$

が成り立つから， $x, y$ の符号を適切に付け替えて目的の式が成り立ちます。

以上，(i), (ii) より， $a = -3$ では以下の定理が成り立つことがわかりました。

$\displaystyle \left( \frac{-3}{p} \right) = 1$ のとき，
$p = x^2 + 3y^2$
を満たす整数の組 $x, y$ が存在する。

まったく同じことですが，以下のように言い換えても良いでしょう。

$p=6n+1$ または $p = 3$ を満たす奇素数 $p$ に対して，
$p = x^2 + 3y^2$
を満たす整数の組 $x, y$ が存在する。

以上が求めたかったものです。

ちなみに，この定理は「オイラーの 6n+1 定理 (Euler's 6n+1 Theorem)」と呼ばれています。

参考：
Euler's 6n+1 Theorem -- from Wolfram MathWorld

（また出ましたか，オイラー。）

$\left( \frac{-3}{p} \right)$ が平方剰余となる $p$ の条件

最後に $\displaystyle \left( \frac{-3}{p} \right)$ が平方剰余となる $p$ の条件を考えたいと思います。

まず， $p = 3$ のとき，明らかに平方剰余となりますから， $p$ として $3$ を除いた奇素数を考えます。

平方剰余の乗法性と相互法則より，

$\displaystyle \left( \frac{-3}{p} \right) = \left( \frac{-1}{p} \right)\left( \frac{3}{p} \right) = \left( \frac{p}{3} \right)$

です。

ここで，

$\displaystyle \left( \frac{p}{3} \right) = \left\{ \begin{array}{c} 1 & (p \equiv 1 \pmod 6) \\ -1 & (p \equiv 5 \pmod 6) \end{array} \right.$

となりますから，結局

$\displaystyle \left( \frac{-3}{p} \right) = \left\{ \begin{array}{c} 1 & (p \equiv 1 \pmod 6) \\ -1 & (p \equiv 5 \pmod 6) \end{array} \right.$

であることがわかります。

結局，以下のことが示せました。

$\displaystyle \left( \frac{-3}{p} \right) = 1 \Longleftrightarrow p = 3$ または $p = 6n+1$

ところで文献によっては，

$p \equiv 1, 3, 7 \pmod {12}$

と書いているものもあるかと思います。この条件は，

$p\equiv 1 \pmod 6$ または $p=3$

とまったく同値な条件です。 $p = 3$ を無理矢理条件に含めた書き方となっているのですね。

$p \equiv 1, 7 \pmod {12}$ は ${\rm mod} \; 6$ では $1$ に合同です。そして， $p \equiv 3 \pmod {12}$ となるような素数は $3$ 以外にありえません。だから，今回の条件と同値です。

また，ほかにも，

$p \equiv 1 \pmod 3$ である奇素数または $p = 3$

という表現を見かけることもあるかと思いますが，これもまったく同じことです。 $p \equiv 1 \pmod 3$ は ${\rm mod} \; 6$ においては $p \equiv 1, 4$ ですが， $p\equiv 4 \pmod 6$ となるような素数は存在しません。ちょっとだけ無駄ですね。

まとめ

今回の記事では，前回紹介した「フェルマーの二平方定理」の延長で，

$p = x^2 + ay^2$

となるような，素数 $p$ の条件について考えました。

このような形の式を「重み付き平方和」と呼びます。素数が重み付き平方和で表せる $p$ の条件は，ほかにもたくさんありますよ。

たとえば， $p = 8n+1, 8n+3$ のときには， $p = x^2 + 2y^2$ のように表せます。これは， $\displaystyle \left( \frac{-2}{p} \right)$ が平方剰余である条件に対応しています。

また， $p = 8n+1, 8n+7$ のときには， $p = x^2 - 2y^2$ のように表せます。これも同様に， $\displaystyle \left( \frac{2}{p} \right)$ が平方剰余である条件に対応しています。

本当は，この式もすべて証明するつもりで居たのですが， $6n+1$ の場合に手間取ったので諦めました。これらは，今回の記事とほとんど同じやり方で証明できますから，興味ある人はやってみてください。

それにしても，素数が重み付き平方和で表せる条件が，平方剰余 $\displaystyle \left( \frac{a}{p} \right)$ に深く関係しているということがわかって，実にスッキリ気持ちの良い定理ですね。

それでは，今日はこの辺で。

<a href="http://tsujimotter.hatenablog.com/entry/quadratic-residue-and-sum-of-two-squares">平方剰余の第一補充則から二平方定理を導く - tsujimotterのノートブック</a>
平方剰余の第一補充則から二平方定理を導く - tsujimotterのノートブック

かつて，この話題にさらっと触れた記事です。
<a href="http://tsujimotter.hatenablog.com/entry/2014/03/31/122232">3n+1型の素数とか - tsujimotterのノートブック</a>
3n+1型の素数とか - tsujimotterのノートブック