§A4.14平方剰余の相互法則

最終更新

平方剰余の相互法則は、相異なる奇素数p,qp,qに対する(pq)\left(\frac{p}{q}\right)と(qp)\left(\frac{q}{p}\right)の関係を定めます。本記事では相互法則と−1,2-1,2に対する補充法則を示し、これらを用いて二次合同方程式の可解性を判定します。

1 相互法則とガウスの補題

相互法則の符号を決めるために、まず法ppの剰余を正負に分けて数えます。

補題 1.1 (ガウスの補題).ppを奇素数、p∤ap \nmid aとする。m=p−12m = \frac{p-1}{2}とし、a,2a,…,maa, 2a, \dots, maをそれぞれ法ppで11からp−1p-1の範囲の代表元に直したとき、その中でp2\frac{p}{2}より大きいものの個数をμ\muとする。このとき

(ap)=(−1)μ.\left(\frac{a}{p}\right) = (-1)^{\mu}.

証明. 各i=1,…,mi=1,\dots,mに対して、iaiaと法ppで合同であり−p/2<ri<p/2-p/2<r_i<p/2を満たす整数rir_iをとる。p∤ap\nmid aかつ1≤i<p1\leq i<pであるからri≠0r_i\neq0であり、1≤∣ri∣≤m1\leq |r_i|\leq mである。ri<0r_i<0となるiiの個数はμ\muに等しい。

1≤i<j≤m1\leq i<j\leq mに対して∣ri∣=∣rj∣|r_i|=|r_j|と仮定する。ri=rjr_i=r_jならば(i−j)a≡0(modp)(i-j)a\equiv0\pmod pであり、p∤ap\nmid aであるからp∣i−jp\mid i-jとなる。しかし0<j−i<p0<j-i<pであるから、この結論は成り立たない。ri=−rjr_i=-r_jならば(i+j)a≡0(modp)(i+j)a\equiv0\pmod pであり、同様にp∣i+jp\mid i+jとなる。しかし0<i+j≤2m−1=p−2<p0<i+j\leq2m-1=p-2<pであるから、この結論も成り立たない。したがって∣r1∣,…,∣rm∣|r_1|,\dots,|r_m|は相異なるmm個の整数であり、1,…,m1,\dots,mの並べ替えである。

各iiについてia≡ri(modp)ia\equiv r_i\pmod pであるから

amm!≡r1r2⋯rm=(−1)μ∣r1∣∣r2∣⋯∣rm∣=(−1)μm!(modp)a^m m!\equiv r_1r_2\cdots r_m =(-1)^\mu |r_1||r_2|\cdots |r_m| =(-1)^\mu m!\pmod p

が成り立つ。m<pm<pであるからp∤m!p\nmid m!であり、m!m!とppは互いに素である。したがって合同式の両辺をm!m!で約して

am≡(−1)μ(modp)a^m\equiv(-1)^\mu\pmod p

を得る。m=(p−1)/2m=(p-1)/2であるから、§A4.13 定理 2.1 (オイラーの規準)によりam≡(ap)(modp)a^m\equiv\left(\frac ap\right)\pmod pである。よって(ap)≡(−1)μ(modp)\left(\frac ap\right)\equiv(-1)^\mu\pmod pとなる。両辺は11または−1-1であり、奇素数ppは22を割らないから、両辺は整数として等しい。▨

注意 1.2. この証明は、フェルマーの小定理の標準的な証明で用いる置換論法を精密化したものである。a,2a,…,(p−1)aa,2a,\dots,(p-1)aが1,2,…,p−11,2,\dots,p-1の並べ替えになることに加えて、絶対値最小代表の符号を追跡することにより、ルジャンドル記号の値を取り出している。

2 第二補充法則

定理 2.1 (第二補充法則).ppを奇素数とすると

(2p)=(−1)p2−18,\left(\frac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}},

すなわちp≡±1(mod8)p \equiv \pm 1 \pmod 8のとき(2p)=1\left(\frac{2}{p}\right) = 1、p≡±3(mod8)p \equiv \pm 3 \pmod 8のとき(2p)=−1\left(\frac{2}{p}\right) = -1。

証明.m=(p−1)/2m=(p-1)/2とおき、補題 1.1をa=2a=2に適用する。2,4,…,2m=p−12,4,\dots,2m=p-1は法ppの11からp−1p-1までの代表元である。このうちp/2p/2を超えるものの個数をμ\muとすると、2k>p/22k>p/2はk>p/4k>p/4と同値であるから

μ=m−⌊p4⌋=p−12−⌊p4⌋\mu=m-\left\lfloor\frac p4\right\rfloor =\frac{p-1}{2}-\left\lfloor\frac p4\right\rfloor

である。

p=8t+sp=8t+s、s∈{1,3,5,7}s\in\{1,3,5,7\}と書く。s=1s=1のときμ=2t\mu=2t、s=3s=3のときμ=2t+1\mu=2t+1、s=5s=5のときμ=2t+1\mu=2t+1、s=7s=7のときμ=2t+2\mu=2t+2である。一方、

p2−18={8t2+2t(s=1),8t2+6t+1(s=3),8t2+10t+3(s=5),8t2+14t+6(s=7)\frac{p^2-1}{8}= \begin{cases} 8t^2+2t & (s=1),\\ 8t^2+6t+1 & (s=3),\\ 8t^2+10t+3 & (s=5),\\ 8t^2+14t+6 & (s=7) \end{cases}

である。したがって、いずれの場合にもμ\muと(p2−1)/8(p^2-1)/8の偶奇は一致する。補題 1.1により

(2p)=(−1)μ=(−1)(p2−1)/8\left(\frac2p\right)=(-1)^\mu=(-1)^{(p^2-1)/8}

を得る。四場合の偶奇から、法88による言い換えも従う。▨

3 相互法則本体の証明

定理 3.1 (平方剰余の相互法則).p,qp, qを相異なる奇素数とする。このとき

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

同値な言い換え：p≡q≡3(mod4)p \equiv q \equiv 3 \pmod 4のときに限り符号が反転する（(pq)=−(qp)\left(\frac{p}{q}\right) = -\left(\frac{q}{p}\right)）。それ以外の場合（p,qp, qの少なくとも一方が≡1(mod4)\equiv 1 \pmod 4）は(pq)=(qp)\left(\frac{p}{q}\right) = \left(\frac{q}{p}\right)。

証明.m=(p−1)/2m=(p-1)/2、n=(q−1)/2n=(q-1)/2とおき、

A=∑i=1m⌊iqp⌋,B=∑j=1n⌊jpq⌋A=\sum_{i=1}^{m}\left\lfloor\frac{iq}{p}\right\rfloor, \qquad B=\sum_{j=1}^{n}\left\lfloor\frac{jp}{q}\right\rfloor

と定める。

各i=1,…,mi=1,\dots,mに対して、iqiqの法ppにおける11からp−1p-1までの代表元をsis_iとし、si>p/2s_i>p/2のときεi=1\varepsilon_i=1、si<p/2s_i<p/2のときεi=0\varepsilon_i=0とする。p∤iqp\nmid iqであるからsi=p/2s_i=p/2とはならない。さらに

ri=si−εipr_i=s_i-\varepsilon_i p

とおくと、rir_iはiqiqの絶対値最小代表である。1≤i<j≤m1\leq i<j\leq mに対して∣ri∣=∣rj∣|r_i|=|r_j|ならばiq≡±jq(modp)iq\equiv\pm jq\pmod pである。p∤qp\nmid qであるからp∣i−jp\mid i-jまたはp∣i+jp\mid i+jとなるが、0<j−i<p0<j-i<pかつ0<i+j<p0<i+j<pであるため、どちらも成り立たない。したがって∣r1∣,…,∣rm∣|r_1|,\dots,|r_m|は1,…,m1,\dots,mの並べ替えである。各iiについて

iq=p⌊iqp⌋+si=p(⌊iqp⌋+εi)+riiq=p\left\lfloor\frac{iq}{p}\right\rfloor+s_i =p\left(\left\lfloor\frac{iq}{p}\right\rfloor+\varepsilon_i\right)+r_i

である。ppとqqは奇数であるから、この等式をi=1,…,mi=1,\dots,mについて加えて法22で見ると

∑i=1mi≡A+∑i=1mεi+∑i=1mri(mod2)\sum_{i=1}^{m}i\equiv A+\sum_{i=1}^{m}\varepsilon_i+\sum_{i=1}^{m}r_i\pmod2

となる。ri≡∣ri∣(mod2)r_i\equiv|r_i|\pmod2であり、∣ri∣|r_i|は1,…,m1,\dots,mの並べ替えであるから、∑ri≡∑i(mod2)\sum r_i\equiv\sum i\pmod2である。よって

A≡∑i=1mεi(mod2)A\equiv\sum_{i=1}^{m}\varepsilon_i\pmod2

を得る。補題 1.1により

(qp)=(−1)A\left(\frac qp\right)=(-1)^A

である。ppとqqを入れ替えた同じ計算から

(pq)=(−1)B\left(\frac pq\right)=(-1)^B

を得る。

1≤i≤m1\leq i\leq m、1≤j≤n1\leq j\leq nを満たす格子点(i,j)(i,j)の集合を考える。iq/piq/pは整数でなく、iq/p<q/2iq/p<q/2であるから、⌊iq/p⌋\left\lfloor iq/p\right\rfloorはpj<qipj<qiを満たすjjの個数である。したがってAAは直線qx=pyqx=pyの下側にある格子点の個数である。同様にBBはqi<pjqi<pjを満たす格子点、すなわち直線の上側にある格子点の個数である。

境界上に格子点があると仮定するとqi=pjqi=pjとなる。相異なる素数p,qp,qは互いに素であるからp∣ip\mid iかつq∣jq\mid jとなるが、1≤i≤(p−1)/2<p1\leq i\leq(p-1)/2<pかつ1≤j≤(q−1)/2<q1\leq j\leq(q-1)/2<qであることに反する。よって長方形内の各格子点は直線の上側または下側のちょうど一方にあり、

A+B=mn=p−12q−12A+B=mn=\frac{p-1}{2}\frac{q-1}{2}

である。以上から

(pq)(qp)=(−1)A+B=(−1)p−12q−12\left(\frac pq\right)\left(\frac qp\right) =(-1)^{A+B} =(-1)^{\frac{p-1}{2}\frac{q-1}{2}}

を得る。指数が奇数となるのはp≡q≡3(mod4)p\equiv q\equiv3\pmod4の場合に限るため、符号についての言い換えも従う。▨

4 計算例

例 4.1.18471847は奇素数であり、365=5⋅73365=5\cdot73である。§A4.13 系 2.4 (乗法性)により

(3651847)=(51847)(731847)\left(\frac{365}{1847}\right) =\left(\frac5{1847}\right)\left(\frac{73}{1847}\right)

と分ける。

55と18471847は相異なる奇素数であり、5≡1(mod4)5\equiv1\pmod4であるから、定理 3.1により符号を変えずに反転することができる。1847≡2(mod5)1847\equiv2\pmod5と定理 2.1から

(51847)=(18475)=(25)=−1\left(\frac5{1847}\right)=\left(\frac{1847}{5}\right) =\left(\frac25\right)=-1

を得る。

7373と18471847は相異なる奇素数であり、73≡1(mod4)73\equiv1\pmod4であるから、同様に

(731847)=(184773)=(2273)=(273)(1173)\left(\frac{73}{1847}\right)=\left(\frac{1847}{73}\right) =\left(\frac{22}{73}\right) =\left(\frac2{73}\right)\left(\frac{11}{73}\right)

となる。73≡1(mod8)73\equiv1\pmod8であるから定理 2.1により(273)=1\left(\frac2{73}\right)=1である。

1111と7373は相異なる奇素数であり、73≡1(mod4)73\equiv1\pmod4であるから

(1173)=(7311)=(711)\left(\frac{11}{73}\right)=\left(\frac{73}{11}\right)=\left(\frac7{11}\right)

である。77と1111は相異なる奇素数であり、両方とも法44で33に合同であるから

(711)=−(117)=−(47)\left(\frac7{11}\right)=-\left(\frac{11}{7}\right)=-\left(\frac47\right)

となる。7≡3(mod4)7\equiv3\pmod4であるから§A4.13 系 2.2 (第一補充法則)により(−17)=−1\left(\frac{-1}{7}\right)=-1である。したがって、乗法性を用いると

−(47)=(−17)(47)=(−47)=(37).-\left(\frac47\right) =\left(\frac{-1}{7}\right)\left(\frac47\right) =\left(\frac{-4}{7}\right) =\left(\frac37\right).

33と77は相異なる奇素数であり、両方とも法44で33に合同であるから

(37)=−(73)=−(13)=−1.\left(\frac37\right)=-\left(\frac73\right)=-\left(\frac13\right)=-1.

よって(1173)=−1\left(\frac{11}{73}\right)=-1であり、

(731847)=1⋅(−1)=−1\left(\frac{73}{1847}\right)=1\cdot(-1)=-1

を得る。最終的に

(3651847)=(−1)(−1)=1\left(\frac{365}{1847}\right)=(-1)(-1)=1

である。したがって、§A4.13 定義 1.2により合同方程式x2≡365(mod1847)x^2\equiv365\pmod{1847}は解をもつ。

繰り返し二乗法で365923 mod 1847365^{923}\bmod1847を計算すると11となる。この計算は§A4.13 定理 2.1 (オイラーの規準)による検算であり、相互法則を用いた判定の証明ではない。

注意 4.2. ガウスは平方剰余の相互法則を「黄金定理」（theorema aureum）と呼び、生涯に8通りの異なる証明を与えた。19歳での最初の証明の後にも、数論的帰納法、ガウス和、種の理論など異なる方法で証明した。現在までに知られている証明は300を超えるともいわれている。平方剰余の相互法則は、後の類体論に現れる一般のアーベル拡大に対する相互法則へ至る歴史の出発点の一つである。

例題

条件と何を求めるかを確認してから、式と答えの対応を見比べてください。

ルジャンドル記号を平方剰余の相互法則で評価し、合同式が解を持つかどうか判定せよ。法はいずれも奇素数である。

解法の型手順: 分子を法で小さくする → 相互法則で反転（両方 ≡3(mod4)\equiv3\pmod4 のときだけ符号が反転）を繰り返す。22 は (2p)=1⟺p≡±1(mod8)\left(\dfrac2p\right)=1\Longleftrightarrow p\equiv\pm1\pmod8、−1-1 は (−1p)=1⟺p≡1(mod4)\left(\dfrac{-1}{p}\right)=1\Longleftrightarrow p\equiv1\pmod4 で処理する。

  1. ルジャンドル記号 (3771)\left(\dfrac{37}{71}\right) を平方剰余の相互法則で評価し、合同式 x2≡37(mod71)x^2\equiv37\pmod{71} が解を持つかどうか判定せよ（7171 は素数）。

    (3771),x2≡37(mod71)\left(\dfrac{37}{71}\right), \qquad x^2 \equiv 37 \pmod{71}

  2. ルジャンドル記号 (101151)\left(\dfrac{101}{151}\right) を平方剰余の相互法則で評価し、合同式 x2≡101(mod151)x^2\equiv101\pmod{151} が解を持つかどうか判定せよ（151151 は素数）。

    (101151),x2≡101(mod151)\left(\dfrac{101}{151}\right), \qquad x^2 \equiv 101 \pmod{151}

  3. ルジャンドル記号 (−163191)\left(\dfrac{-163}{191}\right) を平方剰余の相互法則で評価し、合同式 x2≡−163(mod191)x^2\equiv-163\pmod{191} が解を持つかどうか判定せよ（191191 は素数）。

    (−163191),x2≡−163(mod191)\left(\dfrac{-163}{191}\right), \qquad x^2 \equiv -163 \pmod{191}

  4. ルジャンドル記号 (−5191)\left(\dfrac{-5}{191}\right) を平方剰余の相互法則で評価し、合同式 x2≡−5(mod191)x^2\equiv-5\pmod{191} が解を持つかどうか判定せよ（191191 は素数）。

    (−5191),x2≡−5(mod191)\left(\dfrac{-5}{191}\right), \qquad x^2 \equiv -5 \pmod{191}

  5. ルジャンドル記号 (31137)\left(\dfrac{31}{137}\right) を平方剰余の相互法則で評価し、合同式 x2≡31(mod137)x^2\equiv31\pmod{137} が解を持つかどうか判定せよ（137137 は素数）。

    (31137),x2≡31(mod137)\left(\dfrac{31}{137}\right), \qquad x^2 \equiv 31 \pmod{137}

  6. ルジャンドル記号 (59113)\left(\dfrac{59}{113}\right) を平方剰余の相互法則で評価し、合同式 x2≡59(mod113)x^2\equiv59\pmod{113} が解を持つかどうか判定せよ（113113 は素数）。

    (59113),x2≡59(mod113)\left(\dfrac{59}{113}\right), \qquad x^2 \equiv 59 \pmod{113}

  7. ルジャンドル記号 (−103139)\left(\dfrac{-103}{139}\right) を平方剰余の相互法則で評価し、合同式 x2≡−103(mod139)x^2\equiv-103\pmod{139} が解を持つかどうか判定せよ（139139 は素数）。

    (−103139),x2≡−103(mod139)\left(\dfrac{-103}{139}\right), \qquad x^2 \equiv -103 \pmod{139}

  8. ルジャンドル記号 (53151)\left(\dfrac{53}{151}\right) を平方剰余の相互法則で評価し、合同式 x2≡53(mod151)x^2\equiv53\pmod{151} が解を持つかどうか判定せよ（151151 は素数）。

    (53151),x2≡53(mod151)\left(\dfrac{53}{151}\right), \qquad x^2 \equiv 53 \pmod{151}

  9. ルジャンドル記号 (61139)\left(\dfrac{61}{139}\right) を平方剰余の相互法則で評価し、合同式 x2≡61(mod139)x^2\equiv61\pmod{139} が解を持つかどうか判定せよ（139139 は素数）。

    (61139),x2≡61(mod139)\left(\dfrac{61}{139}\right), \qquad x^2 \equiv 61 \pmod{139}

  10. ルジャンドル記号 (1371)\left(\dfrac{13}{71}\right) を平方剰余の相互法則で評価し、合同式 x2≡13(mod71)x^2\equiv13\pmod{71} が解を持つかどうか判定せよ（7171 は素数）。

    (1371),x2≡13(mod71)\left(\dfrac{13}{71}\right), \qquad x^2 \equiv 13 \pmod{71}

演習

問題を解いてから「解答・解説」を開けます。

ルジャンドル記号を平方剰余の相互法則で評価し、合同式が解を持つかどうか判定せよ。法はいずれも奇素数である。

演習を読み込み中…

前提記事