平方剰余の相互法則 | 初等整数論

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

相互法則の符号を決めるために、まず $p$ で割り切れない整数 $a$ について、 $a,2a,\dots,\frac{p-1}{2}a$ の法 $p$ における剰余を正負に分け、負の剰余の個数を数えます。

補題 1.1 (ガウスの補題). $p$ を奇素数、 $a$ を $p\nmid a$ を満たす整数とし、 $m=(p-1)/2$ とおく。各 $i=1,\dots,m$ に対して、 $ia$ と法 $p$ で合同であり $-p/2<r_i<p/2$ を満たす整数を $r_i$ とする。 $a,2a,\dots,ma$ の法 $p$ における $1$ から $p-1$ までの代表元のうち、 $p/2$ より大きいものの個数を $\mu$ とする。このとき $|r_1|,\dots,|r_m|$ は $1,\dots,m$ の並べ替えであり、

\left(\frac ap\right)=(-1)^\mu

が成り立つ。

証明. $p\nmid a$ かつ $1\leq i<p$ であるから $r_i\neq0$ であり、 $1\leq |r_i|\leq m$ である。 $r_i<0$ となる $i$ の個数は $\mu$ に等しい。

$1\leq i<j\leq m$ に対して $|r_i|=|r_j|$ と仮定する。 $r_i=r_j$ ならば $(i-j)a\equiv0\pmod p$ であり、 $p\nmid a$ であるから $p\mid i-j$ となる。しかし $0<j-i<p$ であるから、この結論は成り立たない。 $r_i=-r_j$ ならば $(i+j)a\equiv0\pmod p$ であり、同様に $p\mid i+j$ となる。しかし $0<i+j\leq2m-1=p-2<p$ であるから、この結論も成り立たない。したがって $|r_1|,\dots,|r_m|$ は相異なる $m$ 個の整数であり、 $1,\dots,m$ の並べ替えである。

各 $i$ について $ia\equiv r_i\pmod p$ であるから

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<p$ であるから $p\nmid m!$ であり、 $m!$ と $p$ は互いに素である。したがって合同式の両辺を $m!$ で約して

a^m\equiv(-1)^\mu\pmod p

を得る。 $m=(p-1)/2$ であるから、§A4.13 定理 2.1により $a^m\equiv\left(\frac ap\right)\pmod p$ である。よって $\left(\frac ap\right)\equiv(-1)^\mu\pmod p$ となる。両辺は $1$ または $-1$ であり、奇素数 $p$ は $2$ を割らないから、両辺は整数として等しい。▨

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

2 第二補充法則

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

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

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

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

\mu=m-\left\lfloor\frac p4\right\rfloor =\frac{p-1}{2}-\left\lfloor\frac p4\right\rfloor

である。

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

\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$ と $(p^2-1)/8$ の偶奇は一致する。補題 1.1により

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

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

3 相互法則本体の証明

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

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

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

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

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,\dots,m$ に対して、 $iq$ の法 $p$ における $1$ から $p-1$ までの代表元を $s_i$ とし、 $s_i>p/2$ のとき $\varepsilon_i=1$ 、 $s_i<p/2$ のとき $\varepsilon_i=0$ とする。 $p\nmid iq$ であるから $s_i=p/2$ とはならない。さらに

r_i=s_i-\varepsilon_i p

とおくと、 $r_i$ は $iq$ の絶対値最小代表である。補題 1.1により、 $|r_1|,\dots,|r_m|$ は $1,\dots,m$ の並べ替えである。各 $i$ について

iq=p\left\lfloor\frac{iq}{p}\right\rfloor+s_i =p\left(\left\lfloor\frac{iq}{p}\right\rfloor+\varepsilon_i\right)+r_i

である。 $p$ と $q$ は奇数であるから、この等式を $i=1,\dots,m$ について加えて法 $2$ で見ると

\sum_{i=1}^{m}i\equiv A+\sum_{i=1}^{m}\varepsilon_i+\sum_{i=1}^{m}r_i\pmod2

となる。 $r_i\equiv|r_i|\pmod2$ であり、 $|r_i|$ は $1,\dots,m$ の並べ替えであるから、 $\sum r_i\equiv\sum i\pmod2$ である。よって

A\equiv\sum_{i=1}^{m}\varepsilon_i\pmod2

を得る。補題 1.1により

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

である。 $p$ と $q$ を入れ替えた同じ計算から

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

を得る。

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

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

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

である。以上から

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

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

4 計算例

例 4.1. $1847$ は奇素数であり、 $365=5\cdot73$ である。§A4.13 系 2.5により

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

と分ける。

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

\left(\frac5{1847}\right)=\left(\frac{1847}{5}\right) =\left(\frac25\right)=-1

を得る。

$73$ と $1847$ は相異なる奇素数であり、 $73\equiv1\pmod4$ であるから、同様に

\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\equiv1\pmod8$ であるから定理 2.1により $\left(\frac2{73}\right)=1$ である。

$11$ と $73$ は相異なる奇素数であり、 $73\equiv1\pmod4$ であるから

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

である。 $7$ と $11$ は相異なる奇素数であり、両方とも法 $4$ で $3$ に合同であるから

\left(\frac7{11}\right)=-\left(\frac{11}{7}\right)=-\left(\frac47\right)

となる。 $4=2^2$ であるから $\left(\frac47\right)=1$ であり、 $-\left(\frac47\right)=-1$ である。よって $\left(\frac{11}{73}\right)=-1$ であり、

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

を得る。最終的に

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

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

一方、 $1847\equiv3\pmod4$ であるから、§A4.13 系 2.3と§A4.13 系 2.5により

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

となる。したがって、合同方程式 $x^2\equiv-365\pmod{1847}$ は解をもたない。

繰り返し二乗法で $365^{923}\bmod1847$ を計算すると $1$ となる。この計算は§A4.13 定理 2.1による検算であり、相互法則を用いた判定の証明ではない。

問題 4.2. 素数 $p$ に対して、合同方程式

x^2+x+1\equiv0\pmod p

が解をもつための必要十分条件を求めよ。また、解が存在する場合の、法 $p$ における解の剰余類の個数を求めよ。

解答.

$p=2$ の場合には、 $x\equiv0,1\pmod2$ のいずれでも $x^2+x+1\equiv1\pmod2$ となるため、解はない。 $p=3$ の場合には

x^2+x+1\equiv(x-1)^2\pmod3

であるから、解は $x\equiv1\pmod3$ の一つである。

以下では $p\ge5$ とする。恒等式

4(x^2+x+1)=(2x+1)^2+3

と、 $2$ および $4$ が法 $p$ で逆数をもつことから、求める合同方程式が解をもつことと、 $z^2\equiv-3\pmod p$ が解をもつことは同値である。§A4.13 系 2.5、§A4.13 系 2.3、定理 3.1により

\begin{aligned} \left(\frac{-3}{p}\right) &=\left(\frac{-1}{p}\right)\left(\frac3p\right)\\ &=(-1)^{(p-1)/2} (-1)^{(3-1)(p-1)/4}\left(\frac p3\right)\\ &=\left(\frac p3\right) \end{aligned}

である。法 $3$ の零でない平方剰余は $1$ だけであるから、 $\left(\frac p3\right)=1$ は $p\equiv1\pmod3$ と同値である。したがって、元の合同方程式が解をもつための必要十分条件は

p=3\quad\text{または}\quad p\equiv1\pmod3

である。

$p\equiv1\pmod3$ の場合に $z_0^2\equiv-3\pmod p$ とすると、 $p\nmid z_0$ である。§A4.13 補題 1.3により、 $z^2\equiv-3\pmod p$ の解は $z\equiv z_0,-z_0\pmod p$ の相異なる二つである。法 $p$ の各剰余類 $z$ に対し、 $2x+1\equiv z\pmod p$ を満たす $x$ はただ一つ存在する。よって、元の合同方程式の解も二つである。 $p=3$ の場合の解は既に求めた一つである。▨

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

5 例題

レベル3 — 平方剰余の相互法則

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

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

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

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

答 $\left(\dfrac{37}{71}\right) = 1,$ 解を持つ

注意 $(37/71) = (34/37) = (2/37)(17/37) = −(3/17) = −(2/3) = 1$ 。分子を法で小さくし、素因数に分けて（平方因子は $1$ ）反転する、を繰り返す。符号は「分子・分母がともに $\equiv3\pmod4$ のときだけ反転」。 $2$ は第二補充法則、 $-1$ は第一補充法則で処理する。値が $1$ なので $x^2\equiv37\pmod{71}$ は解を持つ。相互法則は、平方剰余の問いを符号の補正を除いて反転する法則である。

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

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

答 $\left(\dfrac{101}{151}\right) = -1,$ 解を持たない

注意 $(101/151) = (50/101) = (2/101) = −1$ 。分子を法で小さくし、素因数に分けて（平方因子は $1$ ）反転する、を繰り返す。符号は「分子・分母がともに $\equiv3\pmod4$ のときだけ反転」。 $2$ は第二補充法則、 $-1$ は第一補充法則で処理する。値が $-1$ なので $x^2\equiv101\pmod{151}$ は解を持たない。相互法則は、平方剰余の問いを符号の補正を除いて反転する法則である。

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

\left(\dfrac{-163}{191}\right), \qquad x^2 \equiv -163 \pmod{191}

答 $\left(\dfrac{-163}{191}\right) = -1,$ 解を持たない

注意 $(−163/191) = −(163/191) = (28/163) = (7/163) = −(2/7) = −1$ 。分子を法で小さくし、素因数に分けて（平方因子は $1$ ）反転する、を繰り返す。符号は「分子・分母がともに $\equiv3\pmod4$ のときだけ反転」。 $2$ は第二補充法則、 $-1$ は第一補充法則で処理する。値が $-1$ なので $x^2\equiv-163\pmod{191}$ は解を持たない。相互法則は、平方剰余の問いを符号の補正を除いて反転する法則である。

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

\left(\dfrac{-5}{191}\right), \qquad x^2 \equiv -5 \pmod{191}

答 $\left(\dfrac{-5}{191}\right) = -1,$ 解を持たない

注意 $(−5/191) = −(5/191) = −1$ 。分子を法で小さくし、素因数に分けて（平方因子は $1$ ）反転する、を繰り返す。符号は「分子・分母がともに $\equiv3\pmod4$ のときだけ反転」。 $2$ は第二補充法則、 $-1$ は第一補充法則で処理する。値が $-1$ なので $x^2\equiv-5\pmod{191}$ は解を持たない。相互法則は、平方剰余の問いを符号の補正を除いて反転する法則である。

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

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

答 $\left(\dfrac{31}{137}\right) = -1,$ 解を持たない

注意 $(31/137) = (13/31) = (5/13) = (3/5) = (2/3) = −1$ 。分子を法で小さくし、素因数に分けて（平方因子は $1$ ）反転する、を繰り返す。符号は「分子・分母がともに $\equiv3\pmod4$ のときだけ反転」。 $2$ は第二補充法則、 $-1$ は第一補充法則で処理する。値が $-1$ なので $x^2\equiv31\pmod{137}$ は解を持たない。相互法則は、平方剰余の問いを符号の補正を除いて反転する法則である。

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

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

答 $\left(\dfrac{59}{113}\right) = -1,$ 解を持たない

注意 $(59/113) = (54/59) = (2/59)(3/59) = (2/3) = −1$ 。分子を法で小さくし、素因数に分けて（平方因子は $1$ ）反転する、を繰り返す。符号は「分子・分母がともに $\equiv3\pmod4$ のときだけ反転」。 $2$ は第二補充法則、 $-1$ は第一補充法則で処理する。値が $-1$ なので $x^2\equiv59\pmod{113}$ は解を持たない。相互法則は、平方剰余の問いを符号の補正を除いて反転する法則である。

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

\left(\dfrac{-103}{139}\right), \qquad x^2 \equiv -103 \pmod{139}

答 $\left(\dfrac{-103}{139}\right) = 1,$ 解を持つ

注意 $(−103/139) = −(103/139) = (36/103) = 1$ 。分子を法で小さくし、素因数に分けて（平方因子は $1$ ）反転する、を繰り返す。符号は「分子・分母がともに $\equiv3\pmod4$ のときだけ反転」。 $2$ は第二補充法則、 $-1$ は第一補充法則で処理する。値が $1$ なので $x^2\equiv-103\pmod{139}$ は解を持つ。相互法則は、平方剰余の問いを符号の補正を除いて反転する法則である。

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

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

答 $\left(\dfrac{53}{151}\right) = -1,$ 解を持たない

注意 $(53/151) = (45/53) = (5/53) = (3/5) = (2/3) = −1$ 。分子を法で小さくし、素因数に分けて（平方因子は $1$ ）反転する、を繰り返す。符号は「分子・分母がともに $\equiv3\pmod4$ のときだけ反転」。 $2$ は第二補充法則、 $-1$ は第一補充法則で処理する。値が $-1$ なので $x^2\equiv53\pmod{151}$ は解を持たない。相互法則は、平方剰余の問いを符号の補正を除いて反転する法則である。

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

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

答 $\left(\dfrac{61}{139}\right) = -1,$ 解を持たない

注意 $(61/139) = (17/61) = (10/17) = (2/17)(5/17) = (2/5) = −1$ 。分子を法で小さくし、素因数に分けて（平方因子は $1$ ）反転する、を繰り返す。符号は「分子・分母がともに $\equiv3\pmod4$ のときだけ反転」。 $2$ は第二補充法則、 $-1$ は第一補充法則で処理する。値が $-1$ なので $x^2\equiv61\pmod{139}$ は解を持たない。相互法則は、平方剰余の問いを符号の補正を除いて反転する法則である。

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

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

答 $\left(\dfrac{13}{71}\right) = -1,$ 解を持たない

注意 $(13/71) = (6/13) = (2/13)(3/13) = −1$ 。分子を法で小さくし、素因数に分けて（平方因子は $1$ ）反転する、を繰り返す。符号は「分子・分母がともに $\equiv3\pmod4$ のときだけ反転」。 $2$ は第二補充法則、 $-1$ は第一補充法則で処理する。値が $-1$ なので $x^2\equiv13\pmod{71}$ は解を持たない。相互法則は、平方剰余の問いを符号の補正を除いて反転する法則である。

6 演習

レベル3 — 平方剰余の相互法則

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

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

\left(\dfrac{-41}{101}\right), \qquad x^2 \equiv -41 \pmod{101}

解答.

答 $\left(\dfrac{-41}{101}\right) = -1,$ 解を持たない

注意 $(−41/101) = (41/101) = (19/41) = (3/19) = −1$ 。分子を法で小さくし、素因数に分けて（平方因子は $1$ ）反転する、を繰り返す。符号は「分子・分母がともに $\equiv3\pmod4$ のときだけ反転」。 $2$ は第二補充法則、 $-1$ は第一補充法則で処理する。値が $-1$ なので $x^2\equiv-41\pmod{101}$ は解を持たない。相互法則は、平方剰余の問いを符号の補正を除いて反転する法則である。▨

問題 6.2. ルジャンドル記号 $\left(\dfrac{-61}{73}\right)$ を平方剰余の相互法則で評価し、合同式 $x^2\equiv-61\pmod{73}$ が解を持つかどうか判定せよ（ $73$ は素数）。

\left(\dfrac{-61}{73}\right), \qquad x^2 \equiv -61 \pmod{73}

解答.

答 $\left(\dfrac{-61}{73}\right) = 1,$ 解を持つ

注意 $(−61/73) = (61/73) = (12/61) = (3/61) = 1$ 。分子を法で小さくし、素因数に分けて（平方因子は $1$ ）反転する、を繰り返す。符号は「分子・分母がともに $\equiv3\pmod4$ のときだけ反転」。 $2$ は第二補充法則、 $-1$ は第一補充法則で処理する。値が $1$ なので $x^2\equiv-61\pmod{73}$ は解を持つ。相互法則は、平方剰余の問いを符号の補正を除いて反転する法則である。▨

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

\left(\dfrac{-103}{173}\right), \qquad x^2 \equiv -103 \pmod{173}

解答.

答 $\left(\dfrac{-103}{173}\right) = -1,$ 解を持たない

注意 $(−103/173) = (103/173) = (70/103) = (2/103)(5/103)(7/103) = −(3/5)(5/7) = −(2/3)(2/5) = −1$ 。分子を法で小さくし、素因数に分けて（平方因子は $1$ ）反転する、を繰り返す。符号は「分子・分母がともに $\equiv3\pmod4$ のときだけ反転」。 $2$ は第二補充法則、 $-1$ は第一補充法則で処理する。値が $-1$ なので $x^2\equiv-103\pmod{173}$ は解を持たない。相互法則は、平方剰余の問いを符号の補正を除いて反転する法則である。▨

問題 6.4. ルジャンドル記号 $\left(\dfrac{-31}{97}\right)$ を平方剰余の相互法則で評価し、合同式 $x^2\equiv-31\pmod{97}$ が解を持つかどうか判定せよ（ $97$ は素数）。

\left(\dfrac{-31}{97}\right), \qquad x^2 \equiv -31 \pmod{97}

解答.

答 $\left(\dfrac{-31}{97}\right) = 1,$ 解を持つ

注意 $(−31/97) = (31/97) = (4/31) = 1$ 。分子を法で小さくし、素因数に分けて（平方因子は $1$ ）反転する、を繰り返す。符号は「分子・分母がともに $\equiv3\pmod4$ のときだけ反転」。 $2$ は第二補充法則、 $-1$ は第一補充法則で処理する。値が $1$ なので $x^2\equiv-31\pmod{97}$ は解を持つ。相互法則は、平方剰余の問いを符号の補正を除いて反転する法則である。▨

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

\left(\dfrac{37}{73}\right), \qquad x^2 \equiv 37 \pmod{73}

解答.

答 $\left(\dfrac{37}{73}\right) = 1,$ 解を持つ

注意 $(37/73) = (36/37) = 1$ 。分子を法で小さくし、素因数に分けて（平方因子は $1$ ）反転する、を繰り返す。符号は「分子・分母がともに $\equiv3\pmod4$ のときだけ反転」。 $2$ は第二補充法則、 $-1$ は第一補充法則で処理する。値が $1$ なので $x^2\equiv37\pmod{73}$ は解を持つ。相互法則は、平方剰余の問いを符号の補正を除いて反転する法則である。▨

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

\left(\dfrac{-113}{191}\right), \qquad x^2 \equiv -113 \pmod{191}

解答.

答 $\left(\dfrac{-113}{191}\right) = 1,$ 解を持つ

注意 $(−113/191) = −(113/191) = −(78/113) = −(2/113)(3/113)(13/113) = −(2/3)(9/13) = −(2/3) = 1$ 。分子を法で小さくし、素因数に分けて（平方因子は $1$ ）反転する、を繰り返す。符号は「分子・分母がともに $\equiv3\pmod4$ のときだけ反転」。 $2$ は第二補充法則、 $-1$ は第一補充法則で処理する。値が $1$ なので $x^2\equiv-113\pmod{191}$ は解を持つ。相互法則は、平方剰余の問いを符号の補正を除いて反転する法則である。▨

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

\left(\dfrac{6}{83}\right), \qquad x^2 \equiv 6 \pmod{83}

解答.

答 $\left(\dfrac{6}{83}\right) = -1,$ 解を持たない

注意 $(6/83) = (2/83)(3/83) = (2/3) = −1$ 。分子を法で小さくし、素因数に分けて（平方因子は $1$ ）反転する、を繰り返す。符号は「分子・分母がともに $\equiv3\pmod4$ のときだけ反転」。 $2$ は第二補充法則、 $-1$ は第一補充法則で処理する。値が $-1$ なので $x^2\equiv6\pmod{83}$ は解を持たない。相互法則は、平方剰余の問いを符号の補正を除いて反転する法則である。▨

問題 6.8. ルジャンドル記号 $\left(\dfrac{86}{179}\right)$ を平方剰余の相互法則で評価し、合同式 $x^2\equiv86\pmod{179}$ が解を持つかどうか判定せよ（ $179$ は素数）。

\left(\dfrac{86}{179}\right), \qquad x^2 \equiv 86 \pmod{179}

解答.

答 $\left(\dfrac{86}{179}\right) = -1,$ 解を持たない

注意 $(86/179) = (2/179)(43/179) = (7/43) = −1$ 。分子を法で小さくし、素因数に分けて（平方因子は $1$ ）反転する、を繰り返す。符号は「分子・分母がともに $\equiv3\pmod4$ のときだけ反転」。 $2$ は第二補充法則、 $-1$ は第一補充法則で処理する。値が $-1$ なので $x^2\equiv86\pmod{179}$ は解を持たない。相互法則は、平方剰余の問いを符号の補正を除いて反転する法則である。▨

問題 6.9. ルジャンドル記号 $\left(\dfrac{109}{149}\right)$ を平方剰余の相互法則で評価し、合同式 $x^2\equiv109\pmod{149}$ が解を持つかどうか判定せよ（ $149$ は素数）。

\left(\dfrac{109}{149}\right), \qquad x^2 \equiv 109 \pmod{149}

解答.

答 $\left(\dfrac{109}{149}\right) = -1,$ 解を持たない

注意 $(109/149) = (40/109) = (2/109)(5/109) = −(4/5) = −1$ 。分子を法で小さくし、素因数に分けて（平方因子は $1$ ）反転する、を繰り返す。符号は「分子・分母がともに $\equiv3\pmod4$ のときだけ反転」。 $2$ は第二補充法則、 $-1$ は第一補充法則で処理する。値が $-1$ なので $x^2\equiv109\pmod{149}$ は解を持たない。相互法則は、平方剰余の問いを符号の補正を除いて反転する法則である。▨

問題 6.10. ルジャンドル記号 $\left(\dfrac{-31}{43}\right)$ を平方剰余の相互法則で評価し、合同式 $x^2\equiv-31\pmod{43}$ が解を持つかどうか判定せよ（ $43$ は素数）。

\left(\dfrac{-31}{43}\right), \qquad x^2 \equiv -31 \pmod{43}

解答.

答 $\left(\dfrac{-31}{43}\right) = -1,$ 解を持たない

注意 $(−31/43) = −(31/43) = (12/31) = (3/31) = −1$ 。分子を法で小さくし、素因数に分けて（平方因子は $1$ ）反転する、を繰り返す。符号は「分子・分母がともに $\equiv3\pmod4$ のときだけ反転」。 $2$ は第二補充法則、 $-1$ は第一補充法則で処理する。値が $-1$ なので $x^2\equiv-31\pmod{43}$ は解を持たない。相互法則は、平方剰余の問いを符号の補正を除いて反転する法則である。▨

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

\left(\dfrac{-37}{139}\right), \qquad x^2 \equiv -37 \pmod{139}

解答.

答 $\left(\dfrac{-37}{139}\right) = -1,$ 解を持たない

注意 $(−37/139) = −(37/139) = −(28/37) = −(7/37) = −(2/7) = −1$ 。分子を法で小さくし、素因数に分けて（平方因子は $1$ ）反転する、を繰り返す。符号は「分子・分母がともに $\equiv3\pmod4$ のときだけ反転」。 $2$ は第二補充法則、 $-1$ は第一補充法則で処理する。値が $-1$ なので $x^2\equiv-37\pmod{139}$ は解を持たない。相互法則は、平方剰余の問いを符号の補正を除いて反転する法則である。▨

問題 6.12. ルジャンドル記号 $\left(\dfrac{-113}{127}\right)$ を平方剰余の相互法則で評価し、合同式 $x^2\equiv-113\pmod{127}$ が解を持つかどうか判定せよ（ $127$ は素数）。

\left(\dfrac{-113}{127}\right), \qquad x^2 \equiv -113 \pmod{127}

解答.

答 $\left(\dfrac{-113}{127}\right) = -1,$ 解を持たない

注意 $(−113/127) = −(113/127) = −(14/113) = −(2/113)(7/113) = −1$ 。分子を法で小さくし、素因数に分けて（平方因子は $1$ ）反転する、を繰り返す。符号は「分子・分母がともに $\equiv3\pmod4$ のときだけ反転」。 $2$ は第二補充法則、 $-1$ は第一補充法則で処理する。値が $-1$ なので $x^2\equiv-113\pmod{127}$ は解を持たない。相互法則は、平方剰余の問いを符号の補正を除いて反転する法則である。▨

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

\left(\dfrac{89}{137}\right), \qquad x^2 \equiv 89 \pmod{137}

解答.

答 $\left(\dfrac{89}{137}\right) = -1,$ 解を持たない

注意 $(89/137) = (48/89) = (3/89) = (2/3) = −1$ 。分子を法で小さくし、素因数に分けて（平方因子は $1$ ）反転する、を繰り返す。符号は「分子・分母がともに $\equiv3\pmod4$ のときだけ反転」。 $2$ は第二補充法則、 $-1$ は第一補充法則で処理する。値が $-1$ なので $x^2\equiv89\pmod{137}$ は解を持たない。相互法則は、平方剰余の問いを符号の補正を除いて反転する法則である。▨

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

\left(\dfrac{-83}{139}\right), \qquad x^2 \equiv -83 \pmod{139}

解答.

答 $\left(\dfrac{-83}{139}\right) = -1,$ 解を持たない

注意 $(−83/139) = −(83/139) = (56/83) = (2/83)(7/83) = (6/7) = (2/7)(3/7) = −1$ 。分子を法で小さくし、素因数に分けて（平方因子は $1$ ）反転する、を繰り返す。符号は「分子・分母がともに $\equiv3\pmod4$ のときだけ反転」。 $2$ は第二補充法則、 $-1$ は第一補充法則で処理する。値が $-1$ なので $x^2\equiv-83\pmod{139}$ は解を持たない。相互法則は、平方剰余の問いを符号の補正を除いて反転する法則である。▨

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

\left(\dfrac{-103}{127}\right), \qquad x^2 \equiv -103 \pmod{127}

解答.

答 $\left(\dfrac{-103}{127}\right) = -1,$ 解を持たない

注意 $(−103/127) = −(103/127) = (24/103) = (2/103)(3/103) = −1$ 。分子を法で小さくし、素因数に分けて（平方因子は $1$ ）反転する、を繰り返す。符号は「分子・分母がともに $\equiv3\pmod4$ のときだけ反転」。 $2$ は第二補充法則、 $-1$ は第一補充法則で処理する。値が $-1$ なので $x^2\equiv-103\pmod{127}$ は解を持たない。相互法則は、平方剰余の問いを符号の補正を除いて反転する法則である。▨

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

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

2 第二補充法則

3 相互法則本体の証明

4 計算例

5 例題

6 演習

前提記事