平方剰余の相互法則

相互法則 $(\frac{p}{q}) (\frac{q}{p}) = (- 1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}}$ と補充法則 $(\frac{- 1}{p}) = (- 1)^{\frac{p - 1}{2}}$ , $(\frac{2}{p}) = (- 1)^{\frac{p ^{2} - 1}{8}}$ を使って、 $(\frac{13}{103})$ のようなルジャンドル記号の値を求め、 $(\frac{- 3}{p})$ などを $p$ の余りで判定できる

前提

平方剰余とオイラーの規準（大学数学整数論）

この技能までの道筋（30 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
乗法公式による展開（中学数学数と式）
因数分解（中学数学数と式）
約数の見つけ方（算数整数の性質）
文字式で表した整数の性質（中学数学数と式）
余りによる整数の分類（数学A 整数の性質）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
合同式（数学A 整数の性質）
最大公約数と最小公倍数（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
最大公約数と最小公倍数（数学A 整数の性質）
互いに素な法への分解（数学A 整数の性質）
順列・円順列・重複順列（数学A 場合の数と確率）
組合せ（数学A 場合の数と確率）
確率の定義と和事象・余事象（数学A 場合の数と確率）
包除原理（数学A 場合の数と確率）
オイラー関数の計算（大学数学整数論）
フェルマーの小定理とオイラーの定理（大学数学整数論）
n 進法（数学A 整数の性質）
繰り返し二乗法によるべき剰余（大学数学暗号理論）
平方剰余とオイラーの規準（大学数学整数論）

説明

平方剰余の相互法則を使うと、 $(\frac{13}{103})$ のように法 $p$ が大きいルジャンドル記号を、べき乗計算なしで「分子と分母を入れ替えて余りをとる」操作の繰り返しで求められます。ここで $p, q$ は異なる奇素数とします。補充法則と組み合わせると、 $(\frac{- 1}{p})$ 、 $(\frac{2}{p})$ 、 $(\frac{- 3}{p})$ などの値が $p$ を 4・8・3 で割った余りだけで決まることもわかります。平方根が存在するかの判定や、2 次合同式 $x^{2} \equiv a (mod p)$ の解の有無を調べるときに使います。

なぜそうしてよいのか

第 1 補充法則はオイラーの規準からすぐに出ます。奇素数 $p$ について $(\frac{- 1}{p}) \equiv (- 1)^{\frac{p - 1}{2}} (mod p)$ で、両辺はどちらも $\pm 1$ です。 $1$ と $- 1$ は $p \geq 3$ のとき法 $p$ で合同にならないので、合同はそのまま等号になります。よって $p \equiv 1 (mod 4)$ なら $1$ 、 $p \equiv 3 (mod 4)$ なら $- 1$ です。

第 2 補充法則も数え上げで示せます。 $m = \frac{p - 1}{2}$ とし、偶数 $2, 4, \dots, 2 m$ の積 $2^{m} m!$ を考えます。 $2 k > m$ である因子は $2 k \equiv - (p - 2 k) (mod p)$ と書き直します。 $p - 2 k$ は $1$ 以上 $m$ 以下の奇数です。一方、残りの因子 $2 k \leq m$ は $m$ 以下の偶数です。これらを合わせると $1, 2, \dots, m$ がちょうど 1 回ずつ現れます。したがって $2^{m} m! \equiv (- 1)^{N} m! (mod p)$ となります。ここで $N = m - ⌊ m /2 ⌋$ は書き直した因子の個数です。 $m!$ は $p$ と互いに素なので割ることができ、オイラーの規準から $(\frac{2}{p}) = (- 1)^{N}$ が得られます。 $p = 8 t + 1, 8 t + 3, 8 t + 5, 8 t + 7$ を順に代入すると、 $N$ はそれぞれ偶・奇・奇・偶になります。これは $\frac{p ^{2} - 1}{8}$ の偶奇と一致します。

相互法則 $(\frac{p}{q}) (\frac{q}{p}) = (- 1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}}$ はガウスが証明した深い定理です。証明の一つ（アイゼンシュタインの証明）では、右辺の指数 $\frac{p - 1}{2} \cdot \frac{q - 1}{2}$ を、縦横 $\frac{q - 1}{2} \times \frac{p - 1}{2}$ の長方形の中の格子点の個数として数えます。対角線で 2 つに分けたそれぞれの格子点の個数が、 $(\frac{p}{q})$ と $(\frac{q}{p})$ の符号を決めます。使うときに大事なのは、指数が奇数になるのは $\frac{p - 1}{2}$ と $\frac{q - 1}{2}$ がともに奇数のとき、つまり $p \equiv q \equiv 3 (mod 4)$ のときだけだという点です。したがって、入れ替えで符号が変わるのはこの場合だけです。たとえば $(\frac{3}{7}) = - 1$ 、 $(\frac{7}{3}) = (\frac{1}{3}) = 1$ で、確かに符号が逆です。

手順

分子 $a$ を $p$ で割った余りに置き換える（ $(\frac{a}{p})$ は $a mod p$ だけで決まる）。
$a$ を $\pm$ 素数の積に分解し、乗法性で $(\frac{- 1}{p})$ ・ $(\frac{2}{p})$ ・ $(\frac{q}{p})$ （ $q$ は奇素数）の積にする。2 乗の因子は値が $1$ なので消す。
$(\frac{- 1}{p})$ は $p mod 4$ で決める： $p \equiv 1$ なら $1$ 、 $p \equiv 3$ なら $- 1$ 。 $(\frac{2}{p})$ は $p mod 8$ で決める： $p \equiv \pm 1$ なら $1$ 、 $p \equiv \pm 3$ なら $- 1$ 。
奇素数 $q \neq = p$ の $(\frac{q}{p})$ は $(\frac{p}{q})$ に入れ替える。 $p \equiv q \equiv 3 (mod 4)$ のときだけ符号を $-$ にする。
入れ替えた後は分母 $q$ が小さくなっているので、手順 1 に戻って $p mod q$ をとり、値が $(\frac{1}{q}) = 1$ などすぐわかる形になるまで繰り返す。

例題

ルジャンドル記号 $(\frac{13}{103})$ の値を求めよ。（ $13$ と $103$ はともに素数である。）

例題の解答

手順 1・2：分子 $13$ は $103$ より小さい素数なので、そのまま手順 4 に進む。

手順 4： $13 \equiv 1 (mod 4)$ なので符号は変わらない。よって $(\frac{13}{103}) = (\frac{103}{13})$ 。

手順 5→1： $103 = 7 \cdot 13 + 12$ より $(\frac{103}{13}) = (\frac{12}{13})$ 。

手順 2： $12 = 2^{2} \cdot 3$ で、2 乗の因子は消えるので $(\frac{12}{13}) = (\frac{2}{13})^{2} (\frac{3}{13}) = (\frac{3}{13})$ 。

手順 4： $13 \equiv 1 (mod 4)$ なので $(\frac{3}{13}) = (\frac{13}{3})$ 。

手順 5→1： $13 \equiv 1 (mod 3)$ より $(\frac{13}{3}) = (\frac{1}{3}) = 1$ 。

以上より $(\frac{13}{103}) = 1$ 。

検算： $4^{2} = 16 \equiv 3 (mod 13)$ なので、確かに $3$ は法 $13$ の平方剰余である。

答え: $1$

よくある誤り

$p \equiv q \equiv 3 (mod 4)$ のときに符号を変えずに入れ替えてしまう誤り。たとえば $(\frac{3}{7}) = (\frac{7}{3}) = 1$ とするのは間違い。正しくは $(\frac{3}{7}) = - (\frac{7}{3}) = - (\frac{1}{3}) = - 1$ （法 $7$ の平方は $1, 2, 4$ だけ）。
$(\frac{2}{p})$ を $p mod 4$ で判定してしまう誤り。たとえば $5 \equiv 1 (mod 4)$ だからといって $(\frac{2}{5}) = 1$ とするのは間違い。正しくは $p mod 8$ を見る。 $5 \equiv 5 (mod 8)$ なので $(\frac{2}{5}) = (- 1)^{\frac{25 - 1}{8}} = (- 1)^{3} = - 1$ （法 $5$ の平方は $1, 4$ ）。
$2$ や $- 1$ に相互法則を当てはめて $(\frac{2}{p}) = (\frac{p}{2})$ のように入れ替えてしまう誤り。相互法則は異なる奇素数どうしにしか使えない。正しくは $2$ と $- 1$ は補充法則で処理する。たとえば $(\frac{- 3}{p}) = (\frac{- 1}{p}) (\frac{3}{p}) = (- 1)^{\frac{p - 1}{2}} \cdot (- 1)^{\frac{p - 1}{2}} (\frac{p}{3}) = (\frac{p}{3})$ となる（ $p > 3$ ）。したがって $p \equiv 1 (mod 3)$ なら $1$ 、 $p \equiv 2 (mod 3)$ なら $- 1$ 。
分子を素因数分解せずに、合成数のまま入れ替えてしまう誤り。たとえば $(\frac{12}{13})$ を $(\frac{13}{12})$ とするのは、ここで定めた記号（分母は奇素数）の範囲外である。正しくは $(\frac{12}{13}) = (\frac{2}{13})^{2} (\frac{3}{13})$ と分解してから、奇素数の因子だけを入れ替える。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

この技能を使う問題

この技能の次に学べること

ルジャンドル記号の和と 2 次合同式の解の個数（大学数学整数論）
原始的指標と導手（大学院数学解析的整数論）
2 次体での素数の分解（大学院数学代数的整数論）