√pの作り方（ガウス和） - tsujimotterのノートブック

一昨日にこんなツイートをしてみたら、思った以上に多くの方に面白がってもらえました。せっかくなので、この記事を通して「種明かし（？）」をしたいと思います。

√pの作り方 pic.twitter.com/qy2gzay6EW
— tsujimotter (@tsujimotter) 2020年3月31日

今回は３日連続で投稿する「ガウス和シリーズ」の第１回の記事となっています。よかったら続きもぜひご覧になってください：
tsujimotter.hatenablog.com

平方剰余／平方非剰余

今回の記事全体を通して、 $p$ を奇数の素数とします。

$p$ で割り切れない整数 $a$ に対して、次のような合同式を考えます：

$X^2 \equiv a \pmod{p}$

解 $X$ が整数の範囲に存在するとき、 $a$ は $p$ の平方剰余といいます。逆に、そうでないとき $a$ は $p$ の平方非剰余といいます。

このことを記号であらわすために、 $a$ は $p$ の平方剰余のとき

$\displaystyle \newcommand{\qr}[2]{\left(\frac{#1}{\;#2\;}\right)} \qr{a}{p} = +1$

$a$ は $p$ の平方非剰余のとき

$\displaystyle \qr{a}{p} = -1$

と表すことにします。
（これは平方剰余を表す形式的な記号であって、 $\frac{a}{p}$ に分数としての意味はないことに注意。）

たとえば、 $p = 5$ のとき

$1^2 \equiv 1 \pmod{5}, \;\; 2^2 \equiv 4 \pmod{5}$

が成り立つので、 $1, 4$ は $5$ の平方剰余です。逆に

$X^2 \equiv 2 \pmod{5}, \;\; Y^2 \equiv 3 \pmod{5}$

を満たす整数 $X, Y$ は存在しないため、 $2, 3$ は $5$ の平方非剰余です。

上の記号を使って表すと

$\displaystyle \qr{1}{5} = +1, \;\qr{2}{5} = -1, \;\qr{3}{5} = -1, \;\qr{4}{5} = +1$

ということになりますね。

整数論においてこの平方剰余はたいへん重要視されていて、とても興味深い性質がたくさん調べられています。

その一つが、今回のネタである「ガウス和」という量の持つ次の性質です。

ガウス和とその性質

ガウス和は、平方剰余の記号を用いて、次のように定義されます：

定義（ガウス和）

$\displaystyle G_p := \sum_{k=1}^{p-1} \qr{k}{p} \exp\left(\frac{2\pi i}{p}k\right)$

たとえば、 $p = 5$ のときは

$\displaystyle \begin{align} G_5 &= \sum_{k=1}^{4} \qr{k}{5} \exp\left(\frac{2\pi i}{5}k\right) \\ &= \qr{1}{5}\exp\left(\frac{2\pi i}{5}\right) + \qr{2}{5}\exp\left(\frac{4\pi i}{5}\right) \\ &\;\;\;\;+ \qr{3}{5}\exp\left(\frac{6\pi i}{5}\right) + \qr{4}{5}\exp\left(\frac{8\pi i}{5}\right) \end{align}$

となります。平方剰余の記号を具体的に計算すると

$\displaystyle G_5 = \exp\left(\frac{2\pi i}{5}\right) - \exp\left(\frac{4\pi i}{5}\right) - \exp\left(\frac{6\pi i}{5}\right) + \exp\left(\frac{8\pi i}{5}\right)$

となります。だんだんとツイートの式に近づいてきました。

さてこのガウス和ですが、次の「とてもきれいな性質」が成り立ちます。

定理１

$\displaystyle G_p = \begin{cases} \sqrt{p} & p \equiv 1 \pmod{4} \\ \sqrt{-p} & p \equiv 3 \pmod{4} \end{cases}$

ガウス和の元々の定義は複雑そうなのに、その計算結果はとてもきれいなものになるのです！

tsujimotterはいつ見てもこの式は面白いなと思ってしまいます。

この定理１を証明したのはあのカール・フリードリヒ・ガウスです。だから「ガウス和」と呼ばれるんですね。

証明はやや込み入っているので、次回の記事で改めて紹介したいと思いますが、今回は定理１が成り立つことを受け入れて、計算してみましょう。

例１： $\sqrt{5}$ の作り方

やはり $p = 5$ のときに考えると、 $5 \equiv 1 \pmod{4}$ なので、定理１より $G_5 = \sqrt{5}$ が成り立ちます。ガウス和の定義を展開した結果と比較すると

$\displaystyle \exp\left(\frac{2\pi i}{5}\right) - \exp\left(\frac{4\pi i}{5}\right) - \exp\left(\frac{6\pi i}{5}\right) + \exp\left(\frac{8\pi i}{5}\right) = \sqrt{5}$

となります。目的の式まであと少しです。

ここで有名なオイラーの公式

$\exp(ix) = \cos(x) + i\sin(x)$

を使うと

$\displaystyle \begin{align} &\left(\cos\left(\frac{2\pi}{5}\right) + i\sin\left(\frac{2\pi}{5}\right) \right) - \left(\cos\left(\frac{4\pi}{5}\right) + i\sin\left(\frac{4\pi}{5}\right) \right) \\ &- \left(\cos\left(\frac{6\pi}{5}\right) + i\sin\left(\frac{6\pi}{5}\right) \right) + \left(\cos\left(\frac{8\pi}{5}\right) + i\sin\left(\frac{8\pi}{5}\right) \right) = \sqrt{5} \end{align}$

となります。

ところで、右辺を見ると実数ですので、左辺も実数でなければなりません。すなわち、虚部はすべて打ち消されるということです。

一方で、左辺の虚部は $\sin$ の項しかないので、 $\cos$ だけ考えればよいことになります。したがって

$\displaystyle \begin{align} \cos\left(\frac{2\pi}{5}\right) - \cos\left(\frac{4\pi}{5}\right) - \cos\left(\frac{6\pi}{5}\right) + \cos\left(\frac{8\pi}{5}\right) = \sqrt{5} \end{align}$

となります。

これが冒頭のツイートの式の一つだったというわけですね。

複素数平面で表すと、黒い太矢印の長さが $\sqrt{5}$ になります。

f:id:tsujimotter:20200402002724p:plain:w400

例２： $\sqrt{7}$ の作り方

$p = 7$ のときも同様に計算できます。 $a$ が $7$ の平方剰余であるような $a$ は

$1, 2, 4$

の３つです。逆に、平方非剰余のリストは

$3, 5, 6$

となります。
（余談ですが、一般に平方剰余／平方非剰余の個数は一致します。）

また、 $7 \equiv 3 \pmod 4$ なので、定理１より

$\displaystyle \begin{align} &\exp\left(\frac{2\pi i}{7}\right) + \exp\left(\frac{4\pi i}{7}\right) - \exp\left(\frac{6\pi i}{7}\right) \\ &\;\; + \exp\left(\frac{8\pi i}{7}\right) - \exp\left(\frac{10\pi i}{7}\right) - \exp\left(\frac{12\pi i}{7}\right) = \sqrt{-7} \end{align}$

が得られるというわけです。

さて今度は $\sqrt{-7} = \sqrt{7}i$ で純虚数です。したがって、左辺は虚部、すなわち $\sin$ の項だけ見ればよく

$\displaystyle \begin{align} \sin\left(\frac{2\pi}{7}\right) + \sin\left(\frac{4\pi}{7}\right) - \sin\left(\frac{6\pi}{7}\right) + \sin\left(\frac{8\pi}{7}\right) - \sin\left(\frac{10\pi}{7}\right) - \sin\left(\frac{12\pi}{7}\right) = \sqrt{7} \end{align}$

が得られることになります。

$\sqrt{5}$ のときと同様に、複素数平面上で図形的に表現するとこんな感じになります。

f:id:tsujimotter:20200402003705p:plain:w340

ほかにも

以下同様に、任意の奇素数 $p$ に対して $G_p$ を計算することで cos, sinを使って「 $\sqrt{p}$ を作る式」をいくらでも作ることができます。

$\begin{align} \sin\left(\frac{2\pi}{3}\right) - \sin\left(\frac{4\pi}{3}\right) = \sqrt{3} \end{align}$

$\begin{align} \cos\left(\frac{2\pi}{5}\right) - \cos\left(\frac{4\pi}{5}\right) - \cos\left(\frac{6\pi}{5}\right) + \cos\left(\frac{8\pi}{5}\right) = \sqrt{5} \end{align}$

$\begin{align} \sin\left(\frac{2\pi}{7}\right) + \sin\left(\frac{4\pi}{7}\right) - \sin\left(\frac{6\pi}{7}\right) + \sin\left(\frac{8\pi}{7}\right) - \sin\left(\frac{10\pi}{7}\right) - \sin\left(\frac{12\pi}{7}\right) = \sqrt{7} \end{align}$

$\begin{align} &\sin\left(\frac{2\pi}{11}\right) - \sin\left(\frac{4\pi}{11}\right) + \sin\left(\frac{6\pi}{11}\right) + \sin\left(\frac{8\pi}{11}\right) + \sin\left(\frac{10\pi}{11}\right) \\ &- \sin\left(\frac{12\pi}{11}\right) - \sin\left(\frac{14\pi}{11}\right) - \sin\left(\frac{16\pi}{11}\right) + \sin\left(\frac{18\pi}{11}\right) - \sin\left(\frac{20\pi}{11}\right) = \sqrt{11} \end{align}$

$\begin{align} &\cos\left(\frac{2\pi}{13}\right) - \cos\left(\frac{4\pi}{13}\right) + \cos\left(\frac{6\pi}{13}\right) + \cos\left(\frac{8\pi}{13}\right) - \cos\left(\frac{10\pi}{13}\right) \\ &- \cos\left(\frac{12\pi}{13}\right) - \cos\left(\frac{14\pi}{13}\right) - \cos\left(\frac{16\pi}{13}\right) + \cos\left(\frac{18\pi}{13}\right) + \cos\left(\frac{20\pi}{13}\right) \\ &- \cos\left(\frac{22\pi}{13}\right) + \cos\left(\frac{24\pi}{13}\right) = \sqrt{13} \end{align}$