原始根と平方剰余の相互法則：mod p で平方数になる条件を決める

0. この記事の要点

「7 で割った余りの世界で、平方数になる数はどれか」という素朴な問いを考えます。この記事では、その答えを素数ごとに判定する道具を作り、「素数 $p$ で見て $q$ が平方数かどうか」と「$q$ で見て $p$ が平方数かどうか」が、符号を除いてぴったり連動するという美しい規則（平方剰余の相互法則）を証明します。読み終えると、大きな数についても、平方数になるかどうかを手計算で判定できるようになります。

• 素数 $p$ を法とする既約剰余類の群 $(\mathbb{Z}/p\mathbb{Z})^{\times}$（$p$ と互いに素な余りの全体を、かけ算で見たもの）は巡回群（ある 1 つの元のべきですべての元が表せる群）です。つまり $a,a^2,\ldots,a^{p-1}$ が $1,\ldots,p-1$ をちょうど一度ずつ通る原始根 $a$ が存在します（定理 2.5）。証明は、位数が $d$ の元の個数を $\varphi(d)$ で押さえて、約数についての和 $\sum_{d\mid n}\varphi(d)=n$ と突き合わせるだけです。
• 奇素数のべき $p^k$ や $2p^k$ を法としても原始根が存在します（定理 2.8）。
• $a$ が $p$ を法とする平方剰余（ある $x$ について $x^2\equiv a$）であるかどうかは、ルジャンドル記号 $\left(\frac ap\right)$ で表され、オイラーの規準 $\left(\frac ap\right)\equiv a^{(p-1)/2}\pmod p$ で計算できます（定理 3.3）。
• ガウスの補題（補題 4.1）は、$\left(\frac ap\right)$ を $a,2a,\ldots,\frac{p-1}2a$ の剰余のうち $p/2$ を超えるものの個数の偶奇で表します。そこから補充法則 $\left(\frac2p\right)=1\iff p\equiv\pm1\pmod 8$ が出ます。
• 平方剰余の相互法則（定理 5.3）：相異なる奇素数 $p,q$ について $\left(\frac pq\right)\left(\frac qp\right)=(-1)^{\frac{p-1}2\cdot\frac{q-1}2}$。証明は、$\sum_j\lfloor jq/p\rfloor+\sum_k\lfloor kp/q\rfloor$ が長方形の格子点の個数に等しいことに帰着します（アイゼンシュタイン）。
• 結果として、$\left(\frac ap\right)$ は $a$ を素因数分解して相互法則を反復すれば、素数 $p$ の剰余類（法 $4a$）だけから決まります。

この記事で使う事前知識

• 合同: 2 つの整数の差が $n$ で割り切れるとき、$n$ を法として等しいとみなす関係。→ 合同
• フェルマーの小定理: 素数 $p$ と、$p$ で割り切れない $a$ について $a^{p-1}\equiv1\pmod p$ が成り立つ、という事実。→ 合同式とフェルマーの小定理
• オイラー関数: $1$ から $n$ までの整数のうち、$n$ と互いに素なものの個数 $\varphi(n)$。→ オイラー関数
• 互いに素・最大公約数・中国剰余定理: 共通の約数が $1$ だけであること、など。→ 整除と素因数分解
• 整列性: 正の整数からなる空でない集合には最小の元がある、という性質。→ 整列性
• 床関数: 実数 $x$ 以下の最大の整数 $\lfloor x\rfloor$。

1. 動機：何が平方数になるか

合同式 $x^2\equiv a\pmod p$ が解けるのはどんな $a$ でしょうか。$p=7$ なら $x=1,\ldots,6$ の平方は $1,4,2,2,4,1$ で、$a\in\{1,2,4\}$ だけが平方数です。$p=11$ なら $\{1,3,4,5,9\}$。半数ちょうどが平方数になるのは偶然でしょうか。

もう一つ。$a=2$ は $p=7$ で平方数ですが、$p=5$ では平方数ではありません。$p=3,5,11,13$ では平方数でなく、$p=7,17,23$ では平方数です。素数によって決まるこの規則性に、オイラーとルジャンドルは気づいていましたが、証明できたのは 1796 年のガウスです。ガウスはこれを「黄金定理」と呼び、生涯に 8 通りの証明を与えました。この記事で扱う証明は、そのうち第 3 証明に由来するガウスの補題と、アイゼンシュタインの格子点による議論の組合せです。

この定理は、次の意味で整数論の転換点です。左辺 $\left(\frac pq\right)$ は「$p$ が $q$ を法として平方数か」、右辺 $\left(\frac qp\right)$ は「$q$ が $p$ を法として平方数か」で、二つの素数の立場を入れ替えた問いが、符号を除いて同じ答えになる。これは相互法則と呼ばれるより一般の現象（類体論という、この記事では扱わないより進んだ理論）の最初の例です。

記号。 $p$ は奇素数、$h=(p-1)/2$ とします。合同式の基本は 合同式とフェルマーの小定理、互いに素と最大公約数、中国剰余定理、オイラー関数は 整除と素因数分解 を用います。特に次を既知とします。

• 定理 5.1［合同式とフェルマーの小定理］（フェルマーの小定理）：$p\nmid a$ ならば $a^{p-1}\equiv1\pmod p$。
• 定理 7.5［整除と素因数分解］：$\sum_{d\mid n}\varphi(d)=n$。
• ユークリッドの補題（補題 4.1［素数の魅力と素数定理］）：素数 $p$ が $ab$ を割り切るなら $p\mid a$ または $p\mid b$。

2. 位数と原始根

2.1. 位数

定義 2.1（位数）↗

$n$ を正の整数、$\gcd(a,n)=1$ とする。$a^k\equiv1\pmod n$ となる最小の正の整数 $k$ を、$a$ の $n$ を法とする位数といい、$\mathrm{ord}_n(a)$ と書く。

位数が存在すること：$\gcd(a,n)=1$ ならオイラーの定理（定理 5.3［合同式とフェルマーの小定理］）により $a^{\varphi(n)}\equiv1$ なので、$k=\varphi(n)$ が候補になり、整列性から最小のものが取れる。

補題 2.2（位数の基本性質）✓

$d=\mathrm{ord}_n(a)$ とする。

1. $a^k\equiv1\pmod n\iff d\mid k$。特に $d\mid\varphi(n)$（$n=p$ が素数なら $d\mid p-1$）。
2. $\gcd(j,d)=g$ のとき $\mathrm{ord}_n(a^j)=d/g$。特に $a^j$ の位数が $d$ になるのは $\gcd(j,d)=1$ のとき、かつそのときに限る。
3. $a^0,a^1,\ldots,a^{d-1}$ は $n$ を法として互いに合同でない。

証明（補題 2.2）

(1) ($\Leftarrow$) $k=dm$ なら $a^k=(a^d)^m\equiv1$。($\Rightarrow$) $k=dq+r$（$0\le r<d$）とすると $1\equiv a^k=(a^d)^qa^r\equiv a^r$。$d$ の最小性から $r=0$。後半は $k=\varphi(n)$ に適用する。 (2) $(a^j)^k=a^{jk}\equiv1\iff d\mid jk\iff(d/g)\mid(j/g)k$。$\gcd(d/g,j/g)=1$（補題 2.3［整除と素因数分解］）なので、これは $(d/g)\mid k$ と同値（補題 2.3［合同式とフェルマーの小定理］：$\gcd(c,n)=1$ かつ $n\mid cm$ ならば $n\mid m$）。よって最小の $k$ は $d/g$。 (3) $0\le i<j<d$ で $a^i\equiv a^j$ なら、$a$ が $n$ を法として可逆なので両辺に $a^{-i}$ をかけて $a^{j-i}\equiv1$、$0<j-i<d$ は $d$ の最小性に反する。

∎

2.2. 合同方程式の根の個数

多項式の根の個数が次数以下であることは、体上では成り立ちますが、一般の環では成り立ちません。$x^2\equiv1\pmod{15}$ は 4 つの解をもちます（例 6.7［整除と素因数分解］）。素数を法とするときは成り立ちます。

補題 2.3（素数を法とする根の個数）✓

$p$ を素数、$f(x)=c_nx^n+\cdots+c_0$ を整数係数の多項式で $p\nmid c_n$（$n\ge0$）とする。このとき $f(x)\equiv0\pmod p$ の解は、$p$ を法として高々 $n$ 個である。

証明（補題 2.3）

$n$ に関する帰納法。$n=0$ では $f=c_0\not\equiv0$ なので解なし。$n\ge1$ とし、解 $a$ があれば $f(x)=(x-a)g(x)+f(a)$ と書ける（$g$ は整数係数、次数 $n-1$、最高次の係数は $c_n$ で $p\nmid c_n$）。$f(a)\equiv0$ なので、$a$ と合同でない別の解 $b$ について $(b-a)g(b)\equiv0\pmod p$。$p\nmid b-a$ だから、ユークリッドの補題により $p\mid g(b)$。すなわち $a$ 以外の解は $g$ の解で、帰納法の仮定により高々 $n-1$ 個。合わせて高々 $n$ 個。

∎

2.3. 素数を法とする原始根

定義 2.4（原始根）↗

$\gcd(g,n)=1$ で $\mathrm{ord}_n(g)=\varphi(n)$ となる整数 $g$ を、$n$ を法とする原始根という。

原始根 $g$ があると、補題 2.2(3) により $g^0,\ldots,g^{\varphi(n)-1}$ は互いに合同でない $\varphi(n)$ 個の可逆剰余類で、可逆剰余類の個数がちょうど $\varphi(n)$ なので、$n$ を法とする既約剰余類はすべて $g$ のべきで表されます（$(\mathbb{Z}/n\mathbb{Z})^{\times}$ が $g$ で生成される巡回群）。

次の定理の証明の方針は、数え上げです。位数がちょうど $d$ の剰余類の個数を、各約数 $d$ について調べると、多くても $\varphi(d)$ 個です。一方、すべての $d$ にわたる個数の合計は $p-1$ で、$\varphi(d)$ の合計もちょうど $p-1$ です。合計が一致するので、どの $d$ でも等号が成り立つしかなく、$d=p-1$ の分が原始根になります。

定理 2.5（素数を法とする原始根の存在）✓

素数 $p$ について、$p$ を法とする原始根が存在し、その個数（$p$ を法とする合同類として）はちょうど $\varphi(p-1)$ である。

証明（定理 2.5）

$p=2$ は $g=1$。$p$ を奇素数とする。$p\nmid x$ なる各剰余類 $x$ の位数は $p-1$ の約数（補題 2.2(1)）。$d\mid p-1$ に対し、位数がちょうど $d$ である剰余類の個数を $\psi(d)$ とおく。$p-1$ 個の可逆な剰余類がそれぞれちょうど一つの位数をもつので

$$\sum_{d\mid p-1}\psi(d)=p-1.\tag{$*$}$$

主張: $\psi(d)\le\varphi(d)$。 $\psi(d)=0$ なら明らか。$\psi(d)\ge1$ とし、位数 $d$ の剰余類 $a$ を一つ取る。$a^0,a^1,\ldots,a^{d-1}$ は互いに合同でなく（補題 2.2(3)）、どれも $x^d\equiv1$ の解である。補題 2.3 により $x^d-1\equiv0$ の解は高々 $d$ 個なので、解は $a^0,\ldots,a^{d-1}$ ですべてである。したがって位数 $d$ の剰余類は $a^j$ ($0\le j<d$) の中にあり、補題 2.2(2) により位数が $d$ になるのは $\gcd(j,d)=1$ のときに限る。その個数は $\varphi(d)$。よって $\psi(d)=\varphi(d)$。

したがって $\psi(d)\le\varphi(d)$ がすべての $d\mid p-1$ で成り立つ。一方 定理 7.5［整除と素因数分解］ から $\sum_{d\mid p-1}\varphi(d)=p-1$。$(*)$ と合わせると、すべての $d$ で $\psi(d)=\varphi(d)$ でなければならない（一つでも真に小さければ和が $p-1$ に届かない）。$d=p-1$ とすると $\psi(p-1)=\varphi(p-1)\ge1$。

∎

例 2.6（p = 7 と p = 13）

$p=7$：$3^1,\ldots,3^6\equiv3,2,6,4,5,1$ で、$3$ は原始根。原始根は $\varphi(6)=2$ 個で $3,5$。位数の分布は、位数 $1$ が $\{1\}$、位数 $2$ が $\{6\}$、位数 $3$ が $\{2,4\}$、位数 $6$ が $\{3,5\}$ で、$\psi(1),\psi(2),\psi(3),\psi(6)=1,1,2,2=\varphi(1),\varphi(2),\varphi(3),\varphi(6)$。$p=13$ の原始根は $\varphi(12)=4$ 個で $2,6,7,11$。

素数でない法では、原始根が存在しないことがあります。$n=8$ は、奇数 $1,3,5,7$ がどれも $x^2\equiv1\pmod 8$ を満たすので、位数が $\varphi(8)=4$ になる元がありません。

2.4. 素数べきを法とする原始根

素数を法とする原始根を素数べきに持ち上げます。

補題 2.7（$1 + p^j t$ の p 乗）✓

$p$ を奇素数、$j\ge1$、$a=1+p^jt$（$p\nmid t$）とする。このとき $a^p=1+p^{j+1}t'$ と書け、$p\nmid t'$ である。

証明（補題 2.7）

二項展開 $a^p=1+p\cdot p^jt+\binom p2p^{2j}t^2+\cdots+p^{pj}t^p$。$2\le i\le p-1$ の項では $\binom pi$ が $p$ で割り切れるので、その項は $p^{1+ij}$ の倍数、$1+ij\ge1+2j\ge j+2$。最後の項は $p^{pj}$ の倍数で、$pj\ge3j\ge j+2$（$p\ge3,j\ge1$）。よって $a^p\equiv1+p^{j+1}t\pmod{p^{j+2}}$ で、$t'\equiv t\not\equiv0\pmod p$。

∎

次の定理の証明では、$p$ を法とする原始根 $g$ から出発して、$p^k$ を法としても位数が最大になるようにします。そのために $g^{p-1}$ が $p^2$ を法として $1$ にならないことが要るので、そうなっていない場合には $g$ を $g+p$ に取り替えます（$p$ を法とする剰余類は変わりません）。

定理 2.8（素数べきと 2 × 素数べきの原始根）✓

$p$ を奇素数、$k\ge1$ とする。

1. $p^k$ を法とする原始根が存在する。
2. $2p^k$ を法とする原始根が存在する。

証明（定理 2.8）

(1) $k=1$ は 定理 2.5。$k\ge2$ とする。$g$ を $p$ を法とする原始根とする。$g^{p-1}\equiv1\pmod p$ なので $g^{p-1}=1+pt$ と書ける。$p\mid t$ のときは $g$ を $g+p$ に取り替える：$(g+p)^{p-1}\equiv g^{p-1}+(p-1)g^{p-2}p\pmod{p^2}$ で、$g^{p-1}\equiv1\pmod{p^2}$ のとき $(g+p)^{p-1}\equiv1-pg^{p-2}\pmod{p^2}$。$p\nmid g$ だから $p^2\nmid pg^{p-2}$、すなわち $(g+p)^{p-1}\not\equiv1\pmod{p^2}$。また $g+p\equiv g\pmod p$ なので $g+p$ もやはり $p$ を法とする原始根。以下、$p\nmid t$ としてよい。

補題 2.7 を繰り返すと、$g^{(p-1)p^{i}}=1+p^{i+1}t_i$（$p\nmid t_i$、$i\ge0$）。特に $g^{(p-1)p^{k-2}}=1+p^{k-1}t_{k-2}\not\equiv1\pmod{p^k}$ で、$g^{(p-1)p^{k-1}}=1+p^kt_{k-1}\equiv1\pmod{p^k}$。

$d=\mathrm{ord}_{p^k}(g)$ とする。$g^d\equiv1\pmod{p^k}$ から $g^d\equiv1\pmod p$ なので、$p-1=\mathrm{ord}_p(g)$ は $d$ を割り切る（補題 2.2(1)）。また $d\mid\varphi(p^k)=(p-1)p^{k-1}$。よって $d=(p-1)p^s$（$0\le s\le k-1$）。$s\le k-2$ なら $d\mid(p-1)p^{k-2}$ で $g^{(p-1)p^{k-2}}\equiv1\pmod{p^k}$ となり、上に示したことに反する。したがって $s=k-1$、$d=\varphi(p^k)$。

(2) (1) の原始根 $g$ が奇数でなければ $g+p^k$ に取り替える（奇数になり、$p^k$ を法として同じ）。$g$ 奇数なら、すべての $m$ で $g^m\equiv1\pmod2$。したがって $g^m\equiv1\pmod{2p^k}\iff g^m\equiv1\pmod{p^k}$（命題 2.4［整除と素因数分解］ により、$2$ と $p^k$ の倍数であることは $2p^k$ の倍数であることと同値）。よって $\mathrm{ord}_{2p^k}(g)=\mathrm{ord}_{p^k}(g)=\varphi(p^k)=\varphi(2p^k)$。

∎

注意 2.9（原始根をもつ法の分類）

実は、原始根が存在する $n>1$ は $n=2,4,p^k,2p^k$（$p$ は奇素数）に限られます。$2^k$ ($k\ge3$) や、異なる二つの奇素因数をもつ $n$ では、$(\mathbb{Z}/n\mathbb{Z})^{\times}$ に位数 $2$ の元が 3 個以上あるため巡回群になりえません。この記事では存在側（奇素数べきを法とする場合まで）だけを証明しました。非存在側と $2^k$ の構造は主張のみです。

3. 平方剰余とルジャンドル記号

定義 3.1（平方剰余）↗

$p$ を奇素数、$p\nmid a$ とする。ある整数 $x$ について $x^2\equiv a\pmod p$ となるとき、$a$ を $p$ を法とする平方剰余といい、そうでないとき平方非剰余という。

定義 3.2（ルジャンドル記号）↗

奇素数 $p$ と整数 $a$ に対し、

$$\left(\frac ap\right)=\begin{cases}0&(p\mid a)\\1&(p\nmid a\text{ で }a\text{ が平方剰余})\\-1&(p\nmid a\text{ で }a\text{ が平方非剰余})\end{cases}$$

をルジャンドル記号という。

$\left(\frac ap\right)$ は $a$ を $p$ で割った余りだけで決まります。例えば $\left(\frac{-1}{7}\right)=\left(\frac67\right)=-1$。

定理 3.3（オイラーの規準）✓

奇素数 $p$ と整数 $a$ について、$\left(\dfrac ap\right)\equiv a^{(p-1)/2}\pmod p$。

証明（定理 3.3）

$p\mid a$ なら両辺とも $0$。$p\nmid a$ とし、$h=(p-1)/2$。フェルマーの小定理により $(a^h)^2=a^{p-1}\equiv1$ なので $(a^h-1)(a^h+1)\equiv0$、ユークリッドの補題から $a^h\equiv\pm1\pmod p$。

$a\equiv b^2$（平方剰余）なら $a^h\equiv b^{p-1}\equiv1$。次に、平方剰余の個数が $h$ であることを示す。写像 $b\mapsto b^2$ は $\{1,\ldots,p-1\}$ から $p$ を法とする平方剰余の集合への全射で、$b^2\equiv c^2$ なら $(b-c)(b+c)\equiv0$、すなわち $c\equiv\pm b$。また $b\not\equiv-b$（$p$ が奇数で $p\nmid b$）。したがってちょうど二つずつの $b$ が同じ平方に写り、平方剰余の類は $(p-1)/2=h$ 個。

これらはすべて $x^h\equiv1$ の解で、補題 2.3 により解は高々 $h$ 個なので、$x^h\equiv1$ の解は平方剰余でちょうど尽きる。よって平方非剰余 $a$ では $a^h\not\equiv1$、すなわち $a^h\equiv-1$。

∎

系 3.4（ルジャンドル記号の性質）✓

$p$ を奇素数、$a,b$ を整数とする。

1. $\left(\dfrac{ab}p\right)=\left(\dfrac ap\right)\left(\dfrac bp\right)$。
2. $a\equiv b\pmod p$ ならば $\left(\dfrac ap\right)=\left(\dfrac bp\right)$。
3. $\left(\dfrac{-1}p\right)=(-1)^{(p-1)/2}$。すなわち $-1$ が平方剰余であるのは $p\equiv1\pmod4$ のとき、かつそのときに限る。
4. $p\nmid a$ なら $\left(\dfrac{a^2}p\right)=1$。
5. $1,\ldots,p-1$ のうち、平方剰余と平方非剰余はそれぞれちょうど $(p-1)/2$ 個ある。

証明（系 3.4）

(1) 定理 3.3 から $\left(\frac{ab}p\right)\equiv(ab)^h=a^hb^h\equiv\left(\frac ap\right)\left(\frac bp\right)\pmod p$。両辺は $-1,0,1$ のどれかで、$p\ge3$ ならこれらは $p$ を法として互いに合同でないから、等号が成り立つ。(2) 定義から明らか。(3) 規準で $(-1)^h$。(4) $a^2$ は平方剰余。(5) 前の証明で平方剰余の類は $h$ 個、残りの $p-1-h=h$ 個が非剰余。

∎

例 3.5（p = 11 の平方剰余）

$1^2,\ldots,5^2\equiv1,4,9,5,3$。平方剰余は $\{1,3,4,5,9\}$（$5=(p-1)/2$ 個）。$\left(\frac{-1}{11}\right)=\left(\frac{10}{11}\right)=-1$（$11\equiv3\pmod4$）。規準の確認：$2^5=32\equiv-1$ なので $2$ は非剰余、$3^5=243=22\cdot11+1\equiv1$ なので $3$ は剰余（$5^2=25\equiv3$）。

4. ガウスの補題と補充法則

オイラーの規準は $a^{(p-1)/2}$ という巨大なべきの計算を要します。これを、小さい数の個数の偶奇に置き換えるのがガウスの補題です。

証明の方針：$a,2a,\ldots,ha$ の $p$ での余りのうち、$p/2$ を超えるものは $p$ から引いて「折り返し」ます。折り返した値は $1,\ldots,h$ をちょうど一度ずつ通るので、元の余りの積と $h!$ の比べ合わせで、折り返した個数 $\mu$ に応じた符号 $(-1)^{\mu}$ が現れます。これがオイラーの規準の $a^h$ に等しいことから補題が従います。

補題 4.1（ガウスの補題）✓

$p$ を奇素数、$h=(p-1)/2$、$p\nmid a$ とする。$j=1,\ldots,h$ について $ja$ を $p$ で割った余りを $r_j\in\{1,\ldots,p-1\}$ とし、$r_j>p/2$ となる $j$ の個数を $\mu$ とおく。このとき

$$\left(\frac ap\right)=(-1)^{\mu}.$$

さらに、$s_j=r_j$（$r_j<p/2$ のとき）、$s_j=p-r_j$（$r_j>p/2$ のとき）とおくと、$s_1,\ldots,s_h$ は $1,\ldots,h$ の並べ替えである。

証明（補題 4.1）

$r_j\ne p/2$（$p$ は奇数）なので $s_j\in\{1,\ldots,h\}$ が定まる。

$s_j$ が相異なること。 $s_j=s_k$ とすると $r_j\equiv\pm r_k\pmod p$、すなわち $ja\equiv\pm ka$。$p\nmid a$ なので $a$ で割れて（補題 2.3［合同式とフェルマーの小定理］）$j\equiv\pm k\pmod p$。$1\le j,k\le h$ なので $2\le j+k\le p-1$ であり $p\nmid j+k$、また $|j-k|<p$ なので $p\mid j-k$ なら $j=k$。したがって $j=k$。$s_1,\ldots,s_h$ は $\{1,\ldots,h\}$ の $h$ 個の相異なる元だから、並べ替えである。

積を比べる。 $r_j\equiv s_j$（小さい場合）、$r_j\equiv-s_j$（大きい場合）なので、

$$\prod_{j=1}^h(ja)\equiv\prod_{j=1}^hr_j\equiv(-1)^{\mu}\prod_{j=1}^hs_j=(-1)^{\mu}h!\pmod p.$$

左辺は $a^hh!$。$h!$ の因子はすべて $p$ 未満の正の整数だから $p\nmid h!$ で、$h!$ で割って（ユークリッドの補題）$a^h\equiv(-1)^{\mu}\pmod p$。定理 3.3 により $\left(\frac ap\right)\equiv(-1)^{\mu}$。両辺は $\pm1$ で $p\ge3$ なので等号が成り立つ。

∎

例 4.2（p = 7, a = 3）

$h=3$。$3,6,9$ を $7$ で割った余りは $3,6,2$。$7/2=3.5$ を超えるのは $6$ のみで $\mu=1$。よって $\left(\frac37\right)=-1$。$s_j=3,1,2$ は確かに $\{1,2,3\}$ の並べ替え。実際、平方剰余は $\{1,2,4\}$ で $3$ は含まれない。

命題 4.3（2 の平方剰余）✓

奇素数 $p$ について、$\left(\dfrac2p\right)=(-1)^{(p^2-1)/8}$。すなわち $\left(\frac2p\right)=1\iff p\equiv\pm1\pmod8$。

証明（命題 4.3）

ガウスの補題を $a=2$ に適用する。$j=1,\ldots,h$ で $2j\le p-1<p$ なので $r_j=2j$。$2j>p/2\iff j>p/4$ だから、$\mu=h-\lfloor p/4\rfloor$ 。$p=8k+r$（$r\in\{1,3,5,7\}$）として $h=4k+(r-1)/2$、$\lfloor p/4\rfloor=2k+\lfloor r/4\rfloor$ なので

$$\mu=2k+\frac{r-1}2-\left\lfloor\frac r4\right\rfloor:\quad r=1:\ 2k,\quad r=3:\ 2k+1,\quad r=5:\ 2k+1,\quad r=7:\ 2k+2.$$

$\mu$ が偶数であるのは $r=1,7$ のとき、すなわち $p\equiv\pm1\pmod8$ のとき。$(p^2-1)/8$ の偶奇も同じ：$p=8k\pm1$ で $(p^2-1)/8=8k^2\pm2k$（偶）、$p=8k\pm3$ で $8k^2\pm6k+1$（奇）。

∎

5. 平方剰余の相互法則

5.1. アイゼンシュタインの補題

ガウスの補題の $\mu$ を、床関数の和の偶奇で置き換えます。$\mu$ は「折り返した個数」で数えにくいので、$ja$ を $p$ で割った商の和 $S(a,p)$ に言い換えるのが狙いです。証明では、$a$ が奇数のとき両者の偶奇が一致することを、$ja=p\lfloor ja/p\rfloor+r_j$ の和をとって調べます。

補題 5.1（アイゼンシュタインの補題）✓

$p$ を奇素数、$h=(p-1)/2$、$a$ を $p\nmid a$ なる奇数とする。このとき

$$\left(\frac ap\right)=(-1)^{S(a,p)},\qquad S(a,p)=\sum_{j=1}^h\left\lfloor\frac{ja}p\right\rfloor.$$

証明（補題 5.1）

補題 4.1 の記号を使う。$ja=p\lfloor ja/p\rfloor+r_j$ を $j=1,\ldots,h$ で足すと

$$a\sum_{j=1}^hj=p\,S(a,p)+\sum_{j=1}^hr_j.$$

$r_j$ を、小さいもの（$r_j=s_j$）と大きいもの（$r_j=p-s_j$、$\mu$ 個）に分けると、$\sum r_j=\sum_{j}s_j+\mu p-2\sum_{\text{大}}s_j$。補題より $\sum_js_j=1+2+\cdots+h=\sum_{j=1}^hj$。これを代入して整理すると

$$(a-1)\sum_{j=1}^hj=p\,S(a,p)+p\mu-2\sum_{\text{大}}s_j.$$

$a$ は奇数なので左辺は偶数。右辺の最後の項も偶数、$p$ は奇数だから $S(a,p)+\mu$ は偶数、すなわち $\mu\equiv S(a,p)\pmod2$。ガウスの補題より $\left(\frac ap\right)=(-1)^{\mu}=(-1)^{S(a,p)}$。

∎

5.2. 格子点の数え上げ

次の補題は、床関数の和 $S(q,p)$ と $S(p,q)$ を、長方形の中の格子点（座標がどちらも整数の点）の個数として読み替えます。長方形の対角線に当たる直線 $py=qx$ で点を上下に分けると、下側の点が $S(q,p)$ 個、上側の点が $S(p,q)$ 個になり、合計は長方形全体の点の個数です。下の図で $p=11$, $q=7$ の場合を確かめられます。

補題 5.2（格子点の数え上げ）✓

$p,q$ を相異なる奇素数、$h_p=(p-1)/2$, $h_q=(q-1)/2$ とすると、

$$S(q,p)+S(p,q)=\sum_{x=1}^{h_p}\left\lfloor\frac{qx}p\right\rfloor+\sum_{y=1}^{h_q}\left\lfloor\frac{py}q\right\rfloor=h_ph_q=\frac{p-1}2\cdot\frac{q-1}2.$$

証明（補題 5.2）

長方形の格子点の集合 $R=\{(x,y)\in\mathbb{Z}^2\mid1\le x\le h_p,\ 1\le y\le h_q\}$ の個数は $h_ph_q$。直線 $py=qx$ 上に $R$ の点はない：$py=qx$ とすると $p\mid qx$ で、$p\nmid q$ だからユークリッドの補題により $p\mid x$、しかし $1\le x\le h_p<p$ に反する。したがって $R$ の各点は $py<qx$（直線の下）か $py>qx$（上）のどちらか一方にだけ属する。

下側の点の個数：$x$ を固定すると、$1\le y<qx/p$ を満たす整数 $y$ の個数は $\lfloor qx/p\rfloor$（$qx/p$ は整数でない）。このとき $y\le h_q$ が自動的に満たされる：$x\le h_p$ より $qx/p<q/2$ なので $y<q/2$、整数だから $y\le h_q$。和は $S(q,p)$。

上側の点の個数：$y$ を固定すると、$1\le x<py/q$ を満たす整数 $x$ の個数は $\lfloor py/q\rfloor$（$py/q$ は整数でない）で、同様に $x\le h_p$ が自動的に満たされる。和は $S(p,q)$。

下側と上側の点で $R$ が分割されるので $S(q,p)+S(p,q)=|R|=h_ph_q$。

∎

p = 11, q = 7。長方形 1 ≤ x ≤ 5, 1 ≤ y ≤ 3 の 15 個の格子点は、直線 y = 7x/11 の下側（塗りつぶし）に 7 個、上側（白抜き）に 8 個。

下側の点の個数は $x=1,\ldots,5$ について $\lfloor7x/11\rfloor=0,1,1,2,3$ の和で $S(7,11)=7$、上側は $y=1,2,3$ について $\lfloor11y/7\rfloor=1,3,4$ の和で $S(11,7)=8$。合計 $15=5\cdot3$ です。

5.3. 相互法則

定理 5.3（平方剰余の相互法則（ガウス））✓

$p,q$ を相異なる奇素数とする。

$$\left(\frac pq\right)\left(\frac qp\right)=(-1)^{\frac{p-1}2\cdot\frac{q-1}2}.$$

すなわち、$p\equiv1$ または $q\equiv1\pmod4$ なら $\left(\frac pq\right)=\left(\frac qp\right)$、$p\equiv q\equiv3\pmod4$ なら $\left(\frac pq\right)=-\left(\frac qp\right)$。

証明（定理 5.3）

$q$ は奇数で $p\nmid q$ なので、補題 5.1 を $(a,p)=(q,p)$ に使って $\left(\frac qp\right)=(-1)^{S(q,p)}$。同様に $(a,p)=(p,q)$ で $\left(\frac pq\right)=(-1)^{S(p,q)}$。補題 5.2 により

$$\left(\frac pq\right)\left(\frac qp\right)=(-1)^{S(q,p)+S(p,q)}=(-1)^{\frac{p-1}2\cdot\frac{q-1}2}.$$

後半は、$\frac{p-1}2\cdot\frac{q-1}2$ が奇数であるのは $\frac{p-1}2,\frac{q-1}2$ がともに奇数、すなわち $p\equiv q\equiv3\pmod4$ のとき、かつそのときに限ることから従う。

∎

5.4. 使い方

相互法則とルジャンドル記号の性質（系 3.4, 命題 4.3）をあわせると、$\left(\frac ap\right)$ を機械的に計算できます。$a$ を素因数分解して積に分け、各素因数 $\ell$ について $\left(\frac\ell p\right)$ を相互法則で $\left(\frac p\ell\right)$ に反転し、$p$ を $\ell$ で割った余りに置き換えます。$\ell$ が小さいので計算が減ります。

例 5.4（(30/61) の計算）

$30=2\cdot3\cdot5$。$61\equiv5\pmod8$ なので 命題 4.3 より $\left(\frac2{61}\right)=-1$。$61\equiv1\pmod4$ なので相互法則から $\left(\frac3{61}\right)=\left(\frac{61}3\right)=\left(\frac13\right)=1$、$\left(\frac5{61}\right)=\left(\frac{61}5\right)=\left(\frac15\right)=1$。積は $-1$。よって $30$ は $61$ を法とする平方非剰余。

例 5.5（3 が平方剰余になる素数）

$p>3$ を素数とする。定理 5.3 で $q=3$ とすると $\left(\frac3p\right)\left(\frac p3\right)=(-1)^{(p-1)/2}$。$p$ を $12$ で割った余りで分けて、

• $p\equiv1$: $\left(\frac p3\right)=\left(\frac13\right)=1$、符号 $(-1)^{\text{偶}}=+1$ なので $\left(\frac3p\right)=1$。
• $p\equiv5$: $\left(\frac p3\right)=\left(\frac23\right)=-1$（$2$ は $3$ の平方非剰余）、符号 $+1$ なので $\left(\frac3p\right)=-1$。
• $p\equiv7$: $\left(\frac p3\right)=\left(\frac13\right)=1$、符号 $-1$ なので $\left(\frac3p\right)=-1$。
• $p\equiv11$: $\left(\frac p3\right)=\left(\frac23\right)=-1$、符号 $-1$ なので $\left(\frac3p\right)=1$。

すなわち $3$ が $p$ を法とする平方剰余となるのは $p\equiv\pm1\pmod{12}$ のとき。例えば $p=13$ で $4^2=16\equiv3$。

例 5.6（合成数を法とする二次合同式）

$x^2\equiv a\pmod{pq}$（相異なる奇素数 $p,q$、$p,q\nmid a$）の解は、中国剰余定理（命題 6.6［整除と素因数分解］）により、$x^2\equiv a\ (p)$ と $x^2\equiv a\ (q)$ の解の個数の積。それぞれ $1+\left(\frac ap\right)$, $1+\left(\frac aq\right)$ 個（$\pm$ の二つか、なし）なので、解の個数は $\left(1+\left(\frac ap\right)\right)\left(1+\left(\frac aq\right)\right)\in\{0,4\}$。例えば $x^2\equiv2\pmod{7\cdot17}$：$\left(\frac27\right)=\left(\frac2{17}\right)=1$ なので 4 個の解がある（$3^2=9\equiv2\ (7)$、$6^2=36\equiv2\ (17)$）。

注意 5.7（ヤコビ記号）

合成数 $n=\ell_1\cdots\ell_r$（奇数）に対し、$\left(\frac an\right)=\prod_i\left(\frac a{\ell_i}\right)$ とおいたものをヤコビ記号といい、素因数分解せずに互除法と同じ要領で計算できます（相互法則の拡張が成り立つ）。ただし $\left(\frac an\right)=1$ でも $a$ が平方剰余とは限らないことに注意が必要です。この拡張は証明を省略します。

6. 演習

演習 6.1易

$p=17$ を法とする原始根を一つ見つけ、位数が $4$ の元をすべて挙げよ。

解答

$3$ をべきで調べる：$3^1,3^2,3^4,3^8=3,9,81\equiv13,13^2=169\equiv16\equiv-1$。$3^{16}\equiv1$ で、位数は $16$ の約数。$3^8\equiv-1\ne1$ なので位数は $16$。よって $3$ は原始根。位数 $4$ の元は $3^j$ ($\gcd(j,16)=4$、すなわち $j=4,12$)：$3^4\equiv13$, $3^{12}=3^8\cdot3^4\equiv-13\equiv4$。位数 $4$ の元は $4$ と $13$（実際 $4^2=16\equiv-1$）。

演習 6.2標準

$5$ は $97$ を法とする平方剰余か。また、$x^2\equiv-1\pmod{97}$ を解け。

解答

$97\equiv1\pmod4$ なので相互法則から $\left(\frac5{97}\right)=\left(\frac{97}5\right)=\left(\frac25\right)=-1$（$97\equiv2\pmod5$、$5\equiv5\pmod8$）。平方非剰余。$-1$ は $97\equiv1\pmod4$ なので平方剰余 (系 3.4(3))。解を探すには、$97=81+16=9^2+4^2$ から $9^2\equiv-4^2$、$(9\cdot4^{-1})^2\equiv-1$。$4^{-1}\equiv73$ ($4\cdot73=292=3\cdot97+1$)、$9\cdot73=657=6\cdot97+75$ で $x\equiv\pm75\equiv\pm22$。確認：$22^2=484=4\cdot97+96\equiv-1$ ✓。

演習 6.3標準

$4k+1$ の形の素数は無限に存在することを、平方剰余を用いて示せ。

解答

有限個の素数 $p_1,\ldots,p_r\equiv1\pmod4$ があるとして、$N=(2p_1\cdots p_r)^2+1$ をとる。$N$ は奇数で $N>1$。$q$ を $N$ の素因数とすると $q$ は奇素数で、$(2p_1\cdots p_r)^2\equiv-1\pmod q$。よって $-1$ は $q$ を法とする平方剰余で、系 3.4(3) から $q\equiv1\pmod4$。もし $q=p_i$ なら $q\mid(2p_1\cdots p_r)^2$ と $q\mid N$ から $q\mid1$ となり矛盾。したがって $q$ は新しい $4k+1$ 型の素数で、仮定に反する。

演習 6.4難

素数 $p\equiv1\pmod4$ について、$p$ を法とする平方剰余 $a$（$1\le a\le p-1$）の総和は $p(p-1)/4$ であることを示せ。（$-1$ が平方剰余であることを使う。）

解答

$p\equiv1\pmod4$ なので $-1$ は平方剰余 (系 3.4(3))。$a\in\{1,\ldots,p-1\}$ が平方剰余なら $p-a\equiv-a$ も平方剰余（積の性質 (1)）。$a\mapsto p-a$ は平方剰余の集合の上の対合で、不動点（$a=p-a$）は $p$ が奇数なのでない。したがって平方剰余は和が $p$ の対 $\{a,p-a\}$ に分かれ、系 3.4(5) の $(p-1)/2$ 個から対が $(p-1)/4$ 組できる。総和は $p(p-1)/4$。

参考文献

• C. F. Gauss, Disquisitiones Arithmeticae, 1801（英訳: Springer, 1986）— 第 4 節（二次の合同式）。相互法則の第 1 証明と補充法則。
• 高木貞治『初等整数論講義』第 2 版、共立出版、1971 — 第 3 章（原始根、二次剰余）。
• G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 6th ed., Oxford University Press, 2008 — 第 6 章（平方剰余の相互法則）。
• K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, 2nd ed., Springer GTM 84, 1990 — 第 4 章、第 5 章（二次の相互法則）。
• G. Eisenstein, “Geometrischer Beweis des Fundamentalsatzes für die quadratischen Reste”, Journal für die reine und angewandte Mathematik 28 (1844), 246–248.