ポアソンの和公式を用いた平方剰余の相互法則の証明
今回は、平方剰余の相互法則の解析的な証明を思いついたので紹介します。探しても同じ証明は見つからなかったのですが、平方剰余の相互法則には非常に多くの証明が知られているので、おそらく既出だとは思います。
平方剰余の相互法則とは
まず、ルジャンドル記号の定義を確認します。
$p$を素数、$a$を$p$で割り切れない整数とする。$a$が$p$の平方剰余であるとは、$x^2 \equiv a \pmod{p}$を満たす整数$x$が存在することをいう。
$a$が$p$で割り切れず、$a$が$p$の平方剰余でないとき、$a$は$p$の平方非剰余であるという。平方剰余かどうかを表す記号として、次のルジャンドル記号を用いる。
$$\left(\frac{a}{p}\right) := \begin{cases} 1 & \text{$a$が$p$の平方剰余} \\ -1 & \text{$a$が$p$の平方非剰余である} \end{cases}$$
ルジャンドル記号には、次のような性質があります。証明は簡単で調べればすぐに見つかるので省略します。
$p$を奇素数、$a$を$p$で割り切れない整数とする。このとき、次の等式が成り立つ。
$$\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod{p}$$
$p$を奇素数、$a,b$を$p$で割り切れない整数とする。このとき、次の等式が成り立つ。
$$\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$$
$p$を奇素数とする。
$$\left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}}$$
今回証明するのは、平方剰余の相互法則と呼ばれる次の定理と、第二補充法則と呼ばれる次の定理です。
$p,l$を奇素数とする。次の等式が成り立つ。
$$\left(\frac{l}{p}\right) = (-1)^{\frac{p-1}{2}\frac{l-1}{2}}\left(\frac{p}{l}\right)$$
$p$を奇素数とする。次の等式が成り立つ。
$$\left(\frac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}}$$
ここまで述べた定理を用いると、任意の互いに素な整数$a,b$に対して、$x^2 \equiv a \pmod{b}$となる整数$x$が存在するかどうかが判定できます。
$x^2 \equiv 1009 \pmod{2441}$なる$x$が存在するかどうかを判定する。
$$ \left(\frac{1009}{2441}\right) = (-1)^{\frac{2441-1}{2}\frac{1009-1}{2}}\left(\frac{2441}{1009}\right) = \left(\frac{423}{1009}\right) $$
$$ = \left(\frac{3}{1009}\right) ^2 \left(\frac{47}{1009}\right) = \left(\frac{1009}{3}\right)^2 (-1)^{\frac{1009-1}{2} \frac{47-1}{2}}\left(\frac{1009}{47}\right) = \left(\frac{1}{3}\right)^2 \left(\frac{22}{47}\right) $$
$$ = \left(\frac{2}{47}\right) \left(\frac{11}{47}\right) = (-1)^{\frac{47^2-1}{8}} (-1)^{\frac{47-1}{2} \frac{11-1}{2}}\left(\frac{47}{11}\right) = - \left(\frac{3}{11}\right) $$
$$ = - (-1)^{\frac{11-1}{2} \frac{3-1}{2}} \left(\frac{11}{3}\right) = \left(\frac{2}{3}\right) = (-1)^{\frac{3^2-1}{8}} = -1 $$
よって、$x^2 \equiv 1009 \pmod{2441}$なる$x$は存在しない。
これは不定方程式の解の存在判定などに使えるので、競技数学においても有用な結果です。
平方剰余の相互法則を証明するのがこの記事の目標です。
証明の準備
二次ガウス和の導入
平方剰余の相互法則を証明するために、次の関数を考えます。
$p$を正の整数、$l$を整数とする。$p,l$に対して定まる複素数$f_p(l)$を次のように定義する。
$$ f_p(l) := \sum_{k=0}^{p-1} \exp\left(\frac{2\pi i l k^2}{p}\right) $$
$p$が奇素数のとき、$f_p(l)$は二次ガウス和と呼ばれており、平方剰余との間に次のような密接な関係があります。
$p$を奇素数、$l$を$p$で割り切れない整数とする。このとき、次の等式が成り立つ。
$$ f_p(l) = \left(\frac{l}{p}\right) f_p(1) $$
$p$の原子根$g$を取る。$g^{p-1} \equiv 1 \pmod p$である。オイラーの規準などから、
$x$が$p$の平方剰余$\Longleftrightarrow$ $x \equiv g^{2k} \pmod{p}$を満たす整数$k$が存在する
$x$が$p$の平方非剰余$\Longleftrightarrow$ $x \equiv g^{2k+1} \pmod{p}$を満たす整数$k$が存在する
となる。よって、$l \equiv g^m \pmod p$と書けるとき、
$$ f_p(l) = \sum_{k=0}^{p-1} \exp\left(\frac{2\pi i g^m k^2}{p}\right) = 1 + \sum_{n=1}^{p-1} \exp\left(\frac{2\pi i g^m (g^n)^2}{p}\right) = 1 + \sum_{n=1}^{p-1} \exp\left(\frac{2\pi i g^{m+2n}}{p}\right) $$
となる。よって、$m$が偶数、すなわち$l$が$p$の平方剰余のとき、
$$ f_p(l) = 1 + \sum_{n=1}^{p-1} \exp\left(\frac{2\pi i g^{2n}}{p}\right) = f_p(1) $$
となる。一方、$m$が奇数、すなわち$l$が$p$の平方非剰余のとき、
$$ f_p(l) = 1 + \sum_{n=1}^{p-1} \exp\left(\frac{2\pi i g^{2n+1}}{p}\right) $$
であり、
$$ f_p(1) + f_p(l) = 1 + \sum_{n=1}^{p-1} \exp\left(\frac{2\pi i g^{2n}}{p}\right) + 1 + \sum_{n=1}^{p-1} \exp\left(\frac{2\pi i g^{2n+1}}{p}\right) $$
$$ = 2 + 2\sum_{n=1}^{p-1} \exp\left(\frac{2\pi i g^{n}}{p}\right) = 2 \sum_{k=0}^{p-1} \exp\left(\frac{2\pi i k}{p}\right) = 0 $$
なので、$f_p(l) = -f_p(1)$である。よって、$f_p(l) = \left(\frac{l}{p}\right) f_p(1)$である。
このことから、$f_p(l)$と$f_l(p)$の間の関係式を解析的な手法で求めることができれば、平方剰余の相互法則を証明できるということになります。実際、$f_p(l)$をポアソン和公式と呼ばれる公式を用いて変形することで、$f_p(l)$と$f_l(p)$の間の関係式を求めることができます。
ポアソン和公式
$n$を正の整数、$f$を$[0,n]$上で定義された連続関数で、$f(0)=f(n)$を満たすとする。このとき、次の等式が成り立つ。
$$ \sum_{k=0}^{n-1} f(k) = \sum_{m=-\infty}^{\infty} \int_{x=0}^{n} f(x) e^{2\pi i m x} dx $$
なお、和をとる区間と積分区間を$(-\infty,\infty)$としたものをポアソンの和公式と呼ぶことも多いですが、今回用いるのはこの形の方です。
$f$は$[0,n]$で定義された関数だが、これを周期$n$の周期関数になるように全実数に拡張する。すなわち、$f$を次のように定義する。
$$ f(x) := f(x \mod{n}) $$
これに対し、$g$を次のように定義する。
$$ g(x) = \sum_{k=0}^{n-1} f(x+k) $$
$g(x)$は周期$1$の周期関数である。したがって、次のようにフーリエ級数展開できる。
$$ g(x) = \sum_{m=-\infty}^{\infty} a_m e^{-2\pi i m x}, \ \ a_m = \int_{x=0}^{1} g(x) e^{2\pi i m x} dx $$
$a_m$の表示は次のように書き直せる。
$$ a_m = \int_{x=0}^{1} g(x) e^{2\pi i m x} dx = \int_{x=0}^{1} \sum_{k=0}^{n-1} f(x+k) e^{2\pi i m x} dx $$
$$ = \sum_{k=0}^{n-1} \int_{x=0}^{1} f(x+k) e^{2\pi i m x} dx = \sum_{k=0}^{n-1} \int_{y=k}^{k+1} f(y) e^{2\pi i m y} dy $$
$$ = \int_{y=0}^{n} f(y) e^{2\pi i m y} dy $$
これを用いて、$g(x)$は次のように書ける。
$$ g(x) =\sum_{m=-\infty}^{\infty} e^{-2\pi i m x} \int_{y=0}^{n} g(y) e^{2\pi i m y} dy = \sum_{m=-\infty}^{\infty} \int_{y=0}^{n} g(y) e^{2\pi i m (y-x)} dy $$
$$ \therefore g(0) =\sum_{m=-\infty}^{\infty} \int_{y=0}^{n} f(y) e^{2\pi i m y} dy $$
したがって、
$$ \sum_{k=0}^{n-1} f(k) = \sum_{m=-\infty}^{\infty} \int_{x=0}^{n} f(x) e^{2\pi i m x} dx $$
となる。
総和記号の拡張
証明の前に、ちょっとした定義をしておきます。場合分けを減らすための道具なので大したことはありません。
和の記号を少し拡張して定義する。整数$a$に対し、
$$ \sum_{k=a}^{a-1} f(k) := 0 $$
とする。また、$a,b$を整数とし、$a + 1 < b$とするとき、
$$ \sum_{k=b}^{a} f(k) := - \sum_{k=a+1}^{b-1} f(k) $$
と定義する。このように定義することで、普通の和の記号と同様の計算法則が成り立つ。
これを用いて$f_p(l)$を$p<0$のときも定義する。
この記法は便利なので私はよく使うのですが、他の人が使っているのを見たことがないので広めていきたいですね。
平方剰余の相互法則の証明
さて、ポアソン和公式を用いて$f_p(l)$を変形し、実際に平方剰余の相互法則を証明していきます。
$f_p(l)$の変形
ポアソン和公式を用いて$f_p(l)$を変形すると、次のような式を得ることができます。
$p,l$を整数とする。このとき、次の等式が成り立つ。
$$ f_p(l) = \sqrt{\frac{p}{l}} \sum_{k=0}^{l-1} \exp\left( - \frac{\pi ip k^2}{2l} \right)\left\{1+ (-1)^{kp} (-i)^{lp} \right\} \frac{1+i}{2} $$
$l$が十分小さい場合は、この式を用いて$f_p(l)$を計算することができます。
しばらくの間、$p,l$が奇素数であるという条件は設けず、$p,l$が一般に整数であるとする。$p<0$または$l<0$のときは先ほど定義した和の記号の拡張に注意する。
ポアソンの和公式を用いると、
$$ f_p(l) = \sum_{k=0}^{p-1} \exp\left(\frac{2\pi i l k^2}{p}\right) $$
$$
= \sum_{n=-\infty}^{\infty} \int_{x=0}^{p} \exp\left(\frac{2\pi i l x^2}{p} + 2\pi i n x\right) dx
$$
$$
= \sum_{n=-\infty}^{\infty} \int_{x=0}^{p} \exp\left\{\frac{2\pi il}{p} \left( x + \frac{np}{2l} \right)^2 - \frac{\pi i p n^2}{2l} \right\} dx
$$
$\frac{l}{p} x$を改めて$x$とおくと、
$$ f_p(l) = \frac{p}{l} \sum_{n=-\infty}^{\infty} \int_{x=0}^{l} \exp\left\{\frac{2\pi ip}{l} \left( x + \frac{n}{2} \right)^2 - \frac{\pi ip n^2}{2l} \right\} dx $$
$$ = \frac{p}{l} \sum_{n=-\infty}^{\infty} \exp\left\{ - \frac{\pi ip n^2}{2l} \right\} \int_{x=0}^{l} \exp\left\{\frac{2\pi ip}{l} \left( x + \frac{n}{2} \right)^2 \right\} dx $$
ここで、$n$を改めて$nl+k$と置く。$n$はすべての整数を動き、$k$は$0$から$l-1$まで動く。
$$
f_p(l) = \frac{p}{l} \sum_{n=-\infty}^{\infty} \sum_{k=0}^{l-1} \exp\left\{ - \frac{\pi ip (nl+k)^2}{2l} \right\} \int_{x=0}^{l} \exp\left\{\frac{2\pi ip}{l} \left( x + \frac{nl+k}{2} \right)^2 \right\} dx
$$
$$
= \frac{p}{l} \sum_{k=0}^{l-1} \sum_{n=-\infty}^{\infty} \exp\left\{ - \frac{\pi ip (nl+k)^2}{2l} \right\} \int_{x=\frac{n}{2}l}^{\frac{n}{2}l+l} \exp\left\{\frac{2\pi ip}{l} \left( x + \frac{k}{2} \right)^2 \right\} dx
$$
$$
= \frac{p}{l} \sum_{k=0}^{l-1} \sum_{n=-\infty}^{\infty} \exp\left\{ - \frac{\pi ip (2nl+k)^2}{2l} \right\} \int_{x=nl}^{nl+l} \exp\left\{\frac{2\pi ip}{l} \left( x + \frac{k}{2} \right)^2 \right\} dx
$$
$$
\ \ \ + \frac{p}{l} \sum_{k=0}^{l-1} \sum_{n=-\infty}^{\infty} \exp\left\{ - \frac{\pi ip (2nl+l+k)^2}{2l} \right\} \int_{x=nl+\frac{1}{2}l}^{nl+\frac{3}{2}l} \exp\left\{\frac{2\pi ip}{l} \left( x + \frac{k}{2} \right)^2 \right\} dx
$$
ここで、
$$
\exp\left\{ - \frac{\pi ip (2nl+k)^2}{2l} \right\} = \exp\left\{ - 2\pi ip (n^2l + nk) - \pi ip \frac{k^2}{2l} \right\}
$$
$$
= \exp\left( - \frac{\pi ip k^2}{2l} \right)
$$
$$
\exp\left\{ - \frac{\pi ip (2nl+l+k)^2}{2l} \right\} = \exp\left\{ - 2\pi ip (n^2l + nk) - \pi ip \frac{(k+l)^2}{2l} \right\}
$$
$$
= \exp\left\{ - \pi ip \frac{k^2+l^2+2kl}{2l} \right\}
$$
$$
= (-1)^{kp} (-i)^{lp} \exp\left( - \frac{\pi ip k^2}{2l} \right)
$$
したがって、
$$
f_p(l) = \frac{p}{l} \sum_{k=0}^{l-1} \exp\left( - \frac{\pi ip k^2}{2l} \right) \sum_{n=-\infty}^{\infty} \int_{x=nl}^{nl+l} \exp\left\{\frac{2\pi ip}{l} \left( x + \frac{k}{2} \right)^2 \right\} dx
$$
$$
\ \ \ + \frac{p}{l} \sum_{k=0}^{l-1} (-1)^{kp} (-i)^{lp} \exp\left( - \frac{\pi ip k^2}{2l} \right) \sum_{n=-\infty}^{\infty} \int_{x=nl+\frac{1}{2}l}^{nl+\frac{3}{2}l} \exp\left\{\frac{2\pi ip}{l} \left( x + \frac{k}{2} \right)^2 \right\} dx
$$
$$
= \frac{p}{l} \sum_{k=0}^{l-1} \exp\left( - \frac{\pi ip k^2}{2l} \right)\left\{1+ (-1)^{kp} (-i)^{lp} \right\} \int_{x=-\infty}^{\infty} \exp\left(\frac{2\pi ip}{l} x^2 \right) dx
$$
ここで、フレネル積分の公式
$$ \int_{x=-\infty}^{\infty} \exp\left(ix^2 \right) = \sqrt{i \pi} = \sqrt{\frac{\pi}{2}} (1+i) $$
を用いると、
$$ \int_{x=-\infty}^{\infty} \exp\left(\frac{2\pi ip}{l} x^2 \right) = \sqrt{\frac{l}{2p \pi}} \sqrt{i \pi} = \frac{1+i}{2}\sqrt{\frac{l}{p}} $$
となる。よって、
$$ f_p(l) = \sqrt{\frac{p}{l}} \sum_{k=0}^{l-1} \exp\left( - \frac{\pi ip k^2}{2l} \right)\left\{1+ (-1)^{kp} (-i)^{lp} \right\} \frac{1+i}{2} $$
がなりたつ。
実際にこの式を用いて、$l=1,2$のときの$f_p(l)$を計算してみると、平方剰余の第二補充法則を得ることができます。
$f_p(1)$の計算と平方剰余の第二補充法則の証明
$$ f_p(1) =\begin{cases} \sqrt{p}(1+i) & p \equiv 0 \pmod 4 \\ \sqrt{p} & p \equiv 1 \pmod 4 \\ 0 & p \equiv 2 \pmod 4 \\ i\sqrt{p} & p \equiv 3 \pmod 4 \\ \end{cases} $$
補題に$l=1$を代入すると、
$$ f_p(1) = \sqrt{p} \left\{1+ (-i)^{p} \right\} \frac{1+i}{2} = \begin{cases} \sqrt{p}(1+i) & p \equiv 0 \pmod 4 \\ \sqrt{p} & p \equiv 1 \pmod 4 \\ 0 & p \equiv 2 \pmod 4 \\ i\sqrt{p} & p \equiv 3 \pmod 4 \\ \end{cases} $$
$p$を奇素数とする。このとき、次の等式が成り立つ。
$$ \left(\frac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}} $$
$$
f_p(2) = \sqrt{\frac{p}{2}} \sum_{k=0}^{1} \exp\left( - \frac{\pi ip k^2}{4} \right)\left\{1+ (-1)^{kp} (-i)^{2p} \right\} \frac{1+i}{2}
$$
$$
= \sqrt{\frac{p}{2}} \left\{0
+ \exp\left( - \frac{\pi ip}{4} \right) \{1 + (-1)(-1)\}\frac{1+i}{2} \right\} = \sqrt{p} \exp\left(\frac{\pi i (1 - p)}{4} \right)
$$
である。
$$ \left(\frac{2}{p}\right) = \frac{f_p(2)}{f_p(1)} $$
と上の命題を用いると、
$p \equiv 1 \pmod 8$のとき
$$ \left(\frac{2}{p}\right) = \exp\left(\frac{\pi i (1 - p)}{4} \right) = 1 $$
$p \equiv 3 \pmod 8$のとき
$$ \left(\frac{2}{p}\right) = \frac{1}{i}\exp\left(\frac{\pi i (1 - p)}{4} \right) = \frac{-i}{i} = -1 $$
$p \equiv 5 \pmod 8$のとき
$$ \left(\frac{2}{p}\right) = \exp\left(\frac{\pi i (1 - p)}{4} \right) = -1 $$
$p \equiv 7 \pmod 8$のとき
$$ \left(\frac{2}{p}\right) = \frac{1}{i}\exp\left(\frac{\pi i (1 - p)}{4} \right) = \frac{i}{i} = 1 $$
よって、平方剰余の第二補充法則が成り立つ。
$f_p(l)$と$f_l(-p)$の関係式
さらに計算を進めると、次のような$f_p(l)$と$f_l(-p)$の間の関係式を得ることができます。
$p,l$を整数とする。このとき、次の等式が成り立つ。
$$ \{1-(-1)^p(-i)^{pl}\} f_p(l) = \frac{1}{2} (1+i) (-i)^{pl} \{1 - (-1)^p\} \sqrt{\frac{p}{l}} f_l(-p) $$
$$ f_p(l) = \sqrt{\frac{p}{l}} \sum_{k=0}^{l-1} \exp\left( - \frac{\pi ip k^2}{2l} \right)\left\{1+ (-1)^{kp} (-i)^{lp} \right\} \frac{1+i}{2} $$
であった。$k$の偶奇で分けてやると、
$$
f_p(l) = \sqrt{\frac{p}{l}} \sum_{k=0}^{l-1} \exp\left( - \frac{2\pi ip k^2}{l} \right)\left\{1+ (-1)^{kp} (-i)^{lp} \right\} \frac{1+i}{2}
$$
$$
= \frac{1}{2} \sqrt{\frac{p}{l}} \sum_{k=0}^{l-1} \exp\left( - \frac{2\pi ip k^2}{l} \right)\left\{1 + (-i)^{lp} \right\} \frac{1+i}{2}
$$
$$
+ \frac{1}{2} \sqrt{\frac{p}{l}} \sum_{k=0}^{l-1} \exp\left( - \frac{2\pi ip \left(k + \frac{1}{2} \right)^2}{l} \right)\left\{1+ (-1)^p (-i)^{lp} \right\} \frac{1+i}{2}
$$
ここで、
$$ \sum_{k=0}^{l-1} \exp\left\{- \frac{2 \pi ip}{l} \left(k+\frac{1}{2}\right)^2\right\} + \sum_{k=0}^{l-1} \exp\left(- \frac{2 \pi ip}{l} k^2\right) = \sum_{k=0}^{2l-1} \exp\left(- \frac{2 \pi ip}{4l} k^2\right) $$
$$ \therefore \sum_{k=0}^{l-1} \exp\left\{- \frac{2 \pi ip}{l} \left(k+\frac{1}{2}\right)^2\right\} = \frac{1}{2} f_{4l}(-p) - f_l(-p) $$
であり、和の記号の拡張に注意して、$4l,-p$に対し補題の式を適用すると、
$$
f_{4l}(-p) =\sqrt{\frac{4l}{-p}} \sum_{k=0}^{-p-1} \exp\left( + \frac{\pi i(4l) k^2}{2p} \right)\left\{1+ (-1)^{k(4l)} (-i)^{(4l)(-p)} \right\} \frac{1+i}{2}
$$
$$
= -2(1-i)\sqrt{\frac{l}{p}} \sum_{k=0}^{-p-1} \exp\left( + \frac{2\pi il k^2}{p} \right) = 2(1-i)\sqrt{\frac{l}{p}} \sum_{k=-p}^{-1} \exp\left( + \frac{2\pi il k^2}{p} \right)
$$
$$
= 2(1-i)\sqrt{\frac{l}{p}} \sum_{k=0}^{p-1} \exp\left( + \frac{2\pi il k^2}{p} \right) = 2(1-i)\sqrt{\frac{l}{p}} f_p(l)
$$
であるから、
$$ \sum_{k=0}^{l-1} \exp\left\{- \frac{2 \pi ip}{l} \left(k+\frac{1}{2}\right)^2\right\} = \frac{1}{2} f_{4l}(-p) - f_l(-p) \\ = (1-i)\sqrt{\frac{l}{p}} f_p(l) - f_l(-p) $$
よって、
$$ f_p(l) = \frac{1}{2} \sqrt{\frac{p}{l}} f_l(-p)\left\{1 + (-i)^{lp} \right\} \frac{1+i}{2} + \frac{1}{2} \sqrt{\frac{p}{l}}\left\{ (1-i)\sqrt{\frac{l}{p}} f_p(l) - f_l(-p)\right\}\left\{1 + (-1)^p (-i)^{lp} \right\} \frac{1+i}{2} $$
となる。これを整理すると、
$$ \{1-(-1)^p(-i)^{pl}\} f_p(l) = \frac{1}{2} (1+i) (-i)^{pl} \{1 - (-1)^p\} \sqrt{\frac{p}{l}} f_l(-p) $$
となる。
平方剰余の相互法則の証明
いよいよ、平方剰余の相互法則を証明します。
$p,l$を奇素数とする。次の等式が成り立つ。
$$ \left(\frac{l}{p}\right) = (-1)^{\frac{p-1}{2}\frac{l-1}{2}}\left(\frac{p}{l}\right) $$
補題より、
$$ \{1-(-1)^p(-i)^{pl}\} f_p(l) = \frac{1}{2} (1+i) (-i)^{pl} \{1 - (-1)^p\} \sqrt{\frac{p}{l}} f_l(-p) $$
であった。$p,l$が奇素数なので、$1+(-i)^{pl}$は$0$でないから、両辺をこれで割って、
$$ f_p(l) = \frac{(1+i)(-i)^{pl}}{1+(-i)^{pl}} \sqrt{\frac{p}{l}} f_l(-p) $$
を得る。オイラーの規準から、
$$ f_l(-p) = \left(\frac{-p}{l}\right) f_l(1) = \left(\frac{-1}{l}\right) \left(\frac{p}{l}\right) f_l(1) = (-1)^{\frac{l-1}{2}} \left(\frac{p}{l}\right) f_l(1) = (-1)^{\frac{l-1}{2}} f_l(p) $$
となるから、
$$ f_p(l) = \frac{(1+i)(-i)^{pl}(-1)^{\frac{l-1}{2}}}{1+(-i)^{pl}} \sqrt{\frac{p}{l}} f_l(p) $$
が成り立つ。あとは、$p,l$を$4$で割った余りによって場合分けをして、平方剰余の相互法則を証明する。
$p \equiv l \equiv 1 \pmod 4$の場合
$f_p(1) = \sqrt{p}, f_l(1) = \sqrt{l}, (-i)^{pl} = -i, (-1)^{\frac{l-1}{2}} = 1$であるから、
$$ \sqrt{p} \left(\frac{l}{p}\right) = \frac{(1+i)(-i)\cdot 1}{1+(-i)} \sqrt{\frac{p}{l}} \sqrt{l} \left(\frac{p}{l}\right) $$
$$ \therefore \left(\frac{l}{p}\right) = \left(\frac{p}{l}\right) $$
$p \equiv l \equiv 3 \pmod 4$の場合
$f_p(1) = i\sqrt{p}, f_l(1) = i\sqrt{l}, (-i)^{pl} = -i, (-1)^{\frac{l-1}{2}} = -1$であるから、
$$ i\sqrt{p} \left(\frac{l}{p}\right) = \frac{(1+i)(-i)^{pl}(-1)^{\frac{l-1}{2}}}{1+(-i)^{pl}} \sqrt{\frac{p}{l}} i\sqrt{l} \left(\frac{p}{l}\right) $$
$$ \therefore \left(\frac{l}{p}\right) = -\left(\frac{p}{l}\right) $$
$p \not\equiv l \pmod 4$の場合
$p \equiv 1 \pmod 4, l \equiv 3 \pmod 4$であるとして一般性を失わない。
$f_p(1) = \sqrt{p}, f_l(1) = i\sqrt{l}, (-i)^{pl} = i, (-1)^{\frac{l-1}{2}} = -1$であるから、
$$ \sqrt{p} \left(\frac{l}{p}\right) = \frac{(1+i)(+i)(-1)}{1+i} \sqrt{\frac{p}{l}} i\sqrt{l} \left(\frac{p}{l}\right) $$
$$ \therefore \left(\frac{l}{p}\right) = \left(\frac{p}{l}\right) $$
となる。以上の結果をまとめると、次の平方剰余の相互法則を得る。
$$ \left(\frac{l}{p}\right) = (-1)^{\frac{p-1}{2}\cdot\frac{l-1}{2}} \left(\frac{p}{l}\right) $$
さらなる一般化
ここからは、$f_p(l)$に関して私が研究する中で見つけたことを紹介します。
証明の過程で、$f_p(l)$の式で$k$を$\frac{1}{2}$だけずらしたものを用いました。これを一般化すると、次のような式を得ることができます。証明は省略します。
$p,l$を相異なる奇素数とする。このとき、
$$ \sum_{k=0}^{p-1} \exp\left( \frac{2 \pi il (k+\frac{1}{2})^2}{p} \right) = (-1)^{\frac{p-l}{2}} i f_p(l) $$
が成り立つ。
私は、$f_p(l)$を一般化して、$f_p(m,l)$という関数を定義しました。$f_p(m,l)$は、$f_p(l)$を$k$を$\frac{m}{2l}$だけずらしたものに対応します。
$p,l,m$を整数とする。このとき、
$$ f_p(l,m) := \sum_{k=0}^{p-1} \exp\left( \frac{2 \pi i (mk + lk^2)}{p} \right) $$
と定義する。
これに対して$f_p(l)$と全く同じ計算をすると、次のような主張が成り立つことがわかります。本当に全く同じ計算をするだけなので、時間がある人は試してみてください。
$p,l$が奇数のとき、
$$ f_p(m,l) = S_{plm} \sqrt{\frac{p}{l}} \exp\left(-\frac{\pi i m^2}{2 p l}\right) f_l(-m,-p) $$
ただし、$S_{plm}$は次のように定義される。
$$ S_{plm} = \begin{cases} 1 & p \equiv l \pmod 4 ,\ m \equiv 0 \pmod 2 \\ -i & p \equiv l \pmod 4 ,\ m \equiv 1 \pmod 2 \\ i & p \not\equiv l \pmod 4 ,\ m \equiv 0 \pmod 2 \\ -1 & p \not\equiv l \pmod 4 ,\ m \equiv 1 \pmod 2 \\ \end{cases} $$
詳細は省略しますが、これは次のようなことを意味します。
$p$が奇数であるとし、$p,l$の最大公約数を$g$とする。$m$が$g$の倍数でないとき、$f_p(m,l) = 0$である。$m$が$g$の倍数であるとき、$|f_p(m,l)| = \sqrt{pg}$であり、比較的単純なアルゴリズムで$f_p(m,l)$の偏角も求めることができる。
例えば、$p=11, l=5, m=3$のとき、$f_p(m,l) = \sqrt{11 } \exp\left( \frac{7\pi i}{22} \right)$となることが、次のようにしてわかります。
$f_{11}(3,5)$を計算する。
$$
f_{11}(3,5) = S_{11,5,3} \sqrt{\frac{11}{5}} \exp\left(-\frac{\pi i \cdot 3^2}{2 \cdot 11 \cdot 5}\right) f_5(-3,-11)
$$
$$
= (-1) \sqrt{\frac{11}{5}} \exp\left(-\frac{9\pi i}{110}\right) f_5(-3, -1)
$$
$$
= (-1) \sqrt{\frac{11}{5}} \exp\left(-\frac{9\pi i}{110}\right) \sqrt{\frac{5}{11}} S_{5,-1,-3} \exp\left(-\frac{9\pi i}{2\cdot 5 \cdot 1}\right) f_{-1}(3, -5)
$$
$$
= (-1) \sqrt{\frac{11}{5}} \exp\left(-\frac{9\pi i}{110}\right) \sqrt{\frac{5}{11}} (-i) \exp\left(-\frac{9\pi i}{2\cdot 5 \cdot (-1)}\right) f_{-1}(3, -5) \\
= i\sqrt{11} \exp\left( -\frac{9\pi i}{110} +\frac{9\pi i}{10} \right) f_{-1}(0, 0) = i\sqrt{11} \exp\left( -\frac{9\pi i}{110} +\frac{9\pi i}{10} \right) \cdot (-1)
$$
$$ = \sqrt{11} \exp\left( - \frac{\pi}{2} + \frac{9\pi i}{10} -\frac{9\pi i}{110} \right) = \sqrt{11} \exp\left( \frac{7\pi i}{22} \right) $$
したがって、
$$ \sum_{k=0}^{11-1} \exp\left( \frac{2 \pi i (3k + 5k^2)}{11} \right) = \sqrt{11} \exp\left( \frac{7\pi i}{22} \right) $$
これを使えば、$\exp{}$の中身が2次式になっているような周期$p$の和を、なんでも簡単に計算することができます。テータ関数との類似性を見ることもできます。何かに応用できるかもしれません。
まとめ
いかがでしたでしょうか。思いのほか長い記事になってしまいましたが、楽しんでいただけたら嬉しいです。
