# 原始根と平方剰余の相互法則：mod p で平方数になる条件を決める > 素数を法とする原始根の存在を位数の数え上げで示し、ルジャンドル記号、オイラーの規準、ガウスの補題を経て、格子点の数え上げによる平方剰余の相互法則の証明まで一続きに与える。 > https://rikai.mugen-giken.com/mathematics/number-theory/quadratic-reciprocity ## 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$ が存在します（）。証明は、位数が $d$ の元の個数を $\varphi(d)$ で押さえて、約数についての和 $\sum_{d\mid n}\varphi(d)=n$ と突き合わせるだけです。 - 奇素数のべき $p^k$ や $2p^k$ を法としても原始根が存在します（）。 - $a$ が $p$ を法とする**平方剰余**（ある $x$ について $x^2\equiv a$）であるかどうかは、**ルジャンドル記号** $\left(\frac ap\right)$ で表され、**オイラーの規準** $\left(\frac ap\right)\equiv a^{(p-1)/2}\pmod p$ で計算できます（）。 - **ガウスの補題**（）は、$\left(\frac ap\right)$ を $a,2a,\ldots,\frac{p-1}2a$ の剰余のうち $p/2$ を超えるものの個数の偶奇で表します。そこから補充法則 $\left(\frac2p\right)=1\iff p\equiv\pm1\pmod 8$ が出ます。 - **平方剰余の相互法則**（）：相異なる奇素数 $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$）だけから決まります。 ## 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$ とします。合同式の基本は [合同式とフェルマーの小定理](/mathematics/number-theory/congruences-and-fermat)、互いに素と最大公約数、中国剰余定理、[オイラー関数](/mathematics/number-theory/elementary-number-theory#def-phi)は [整除と素因数分解](/mathematics/number-theory/elementary-number-theory) を用います。特に次を既知とします。 - （フェルマーの小定理）：$p\nmid a$ ならば $a^{p-1}\equiv1\pmod p$。 - ：$\sum_{d\mid n}\varphi(d)=n$。 - ユークリッドの補題（）：素数 $p$ が $ab$ を割り切るなら $p\mid a$ または $p\mid b$。 ## 2. 位数と原始根 ### 2.1. 位数 $n$ を正の整数、$\gcd(a,n)=1$ とする。$a^k\equiv1\pmod n$ となる最小の正の整数 $k$ を、$a$ の $n$ を法とする**位数**といい、$\mathrm{ord}_n(a)$ と書く。 位数が存在すること：$\gcd(a,n)=1$ ならオイラーの定理（）により $a^{\varphi(n)}\equiv1$ なので、$k=\varphi(n)$ が候補になり、[整列性](/mathematics/foundations/proof-techniques#ax-well-ordering)から最小のものが取れる。 $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$ を法として互いに合同でない。 (1) ($\Leftarrow$) $k=dm$ なら $a^k=(a^d)^m\equiv1$。($\Rightarrow$) $k=dq+r$（$0\le r）なので、これは $(d/g)\mid k$ と同値（：$\gcd(c,n)=1$ かつ $n\mid cm$ ならば $n\mid m$）。よって最小の $k$ は $d/g$。 (3) $0\le i ### 2.2. 合同方程式の根の個数 多項式の根の個数が次数以下であることは、体上では成り立ちますが、一般の環では成り立ちません。$x^2\equiv1\pmod{15}$ は 4 つの解をもちます（）。素数を法とするときは成り立ちます。 $p$ を素数、$f(x)=c_nx^n+\cdots+c_0$ を整数係数の多項式で $p\nmid c_n$（$n\ge0$）とする。このとき $f(x)\equiv0\pmod p$ の解は、$p$ を法として高々 $n$ 個である。 $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. 素数を法とする原始根 $\gcd(g,n)=1$ で $\mathrm{ord}_n(g)=\varphi(n)$ となる整数 $g$ を、$n$ を法とする**原始根**という。 原始根 $g$ があると、(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$ の分が原始根になります。 素数 $p$ について、$p$ を法とする原始根が存在し、その個数（$p$ を法とする合同類として）はちょうど $\varphi(p-1)$ である。 $p=2$ は $g=1$。$p$ を奇素数とする。$p\nmid x$ なる各剰余類 $x$ の位数は $p-1$ の約数（(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}$ は互いに合同でなく（(3)）、どれも $x^d\equiv1$ の解である。 により $x^d-1\equiv0$ の解は高々 $d$ 個なので、解は $a^0,\ldots,a^{d-1}$ ですべてである。したがって位数 $d$ の剰余類は $a^j$ ($0\le j(2) により位数が $d$ になるのは $\gcd(j,d)=1$ のときに限る。その個数は $\varphi(d)$。よって $\psi(d)=\varphi(d)$。 したがって $\psi(d)\le\varphi(d)$ がすべての $d\mid p-1$ で成り立つ。一方 から $\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$。 $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. 素数べきを法とする原始根 素数を法とする原始根を素数べきに持ち上げます。 $p$ を奇素数、$j\ge1$、$a=1+p^jt$（$p\nmid t$）とする。このとき $a^p=1+p^{j+1}t'$ と書け、$p\nmid t'$ である。 二項展開 $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$ を法とする剰余類は変わりません）。 $p$ を奇素数、$k\ge1$ とする。 1. $p^k$ を法とする原始根が存在する。 2. $2p^k$ を法とする原始根が存在する。 (1) $k=1$ は 。$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$ としてよい。 を繰り返すと、$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$ を割り切る（(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$ と $p^k$ の倍数であることは $2p^k$ の倍数であることと同値）。よって $\mathrm{ord}_{2p^k}(g)=\mathrm{ord}_{p^k}(g)=\varphi(p^k)=\varphi(2p^k)$。 実は、原始根が存在する $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. 平方剰余とルジャンドル記号 $p$ を奇素数、$p\nmid a$ とする。ある整数 $x$ について $x^2\equiv a\pmod p$ となるとき、$a$ を $p$ を法とする**平方剰余**といい、そうでないとき**平方非剰余**という。 奇素数 $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$。 奇素数 $p$ と整数 $a$ について、$\left(\dfrac ap\right)\equiv a^{(p-1)/2}\pmod p$。 $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$ の解で、 により解は高々 $h$ 個なので、$x^h\equiv1$ の解は平方剰余でちょうど尽きる。よって平方非剰余 $a$ では $a^h\not\equiv1$、すなわち $a^h\equiv-1$。 $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$ 個ある。 (1) から $\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$ 個が非剰余。 $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$ に等しいことから補題が従います。 $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_1,\ldots,s_h$ は $1,\ldots,h$ の並べ替えである。 $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$ で割れて（）$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| により $\left(\frac ap\right)\equiv(-1)^{\mu}$。両辺は $\pm1$ で $p\ge3$ なので等号が成り立つ。 $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$ は含まれない。 奇素数 $p$ について、$\left(\dfrac2p\right)=(-1)^{(p^2-1)/8}$。すなわち $\left(\frac2p\right)=1\iff p\equiv\pm1\pmod8$。 ガウスの補題を $a=2$ に適用する。$j=1,\ldots,h$ で $2j\le p-1p/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$ の和をとって調べます。 $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. $$ の記号を使う。$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$ の場合を確かめられます。 $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. $$ 長方形の格子点の集合 $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_pqx$（上）のどちらか一方にだけ属する。 下側の点の個数：$x$ を固定すると、$1\le y

12345 123 x
下側の点の個数は $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. 相互法則 $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)$。 $q$ は奇数で $p\nmid q$ なので、 を $(a,p)=(q,p)$ に使って $\left(\frac qp\right)=(-1)^{S(q,p)}$。同様に $(a,p)=(p,q)$ で $\left(\frac pq\right)=(-1)^{S(p,q)}$。 により $$ \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. 使い方 相互法則とルジャンドル記号の性質（, ）をあわせると、$\left(\frac ap\right)$ を機械的に計算できます。$a$ を素因数分解して積に分け、各素因数 $\ell$ について $\left(\frac\ell p\right)$ を相互法則で $\left(\frac p\ell\right)$ に反転し、$p$ を $\ell$ で割った余りに置き換えます。$\ell$ が小さいので計算が減ります。 $30=2\cdot3\cdot5$。$61\equiv5\pmod8$ なので より $\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$ を法とする平方非剰余。 $p>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$。 $x^2\equiv a\pmod{pq}$（相異なる奇素数 $p,q$、$p,q\nmid a$）の解は、中国剰余定理（）により、$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)$）。 合成数 $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. 演習 $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$）。 $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))。解を探すには、$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$ ✓。 $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) から $q\equiv1\pmod4$。もし $q=p_i$ なら $q\mid(2p_1\cdots p_r)^2$ と $q\mid N$ から $q\mid1$ となり矛盾。したがって $q$ は新しい $4k+1$ 型の素数で、仮定に反する。 素数 $p\equiv1\pmod4$ について、$p$ を法とする平方剰余 $a$（$1\le a\le p-1$）の総和は $p(p-1)/4$ であることを示せ。（$-1$ が平方剰余であることを使う。） $p\equiv1\pmod4$ なので $-1$ は平方剰余 ((3))。$a\in\{1,\ldots,p-1\}$ が平方剰余なら $p-a\equiv-a$ も平方剰余（積の性質 (1)）。$a\mapsto p-a$ は平方剰余の集合の上の対合で、不動点（$a=p-a$）は $p$ が奇数なのでない。したがって平方剰余は和が $p$ の対 $\{a,p-a\}$ に分かれ、(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.