ルジャンドル記号の和と 2 次合同式の解の個数

$x^{2} \equiv a (mod p)$ の解の個数が $1 + (\frac{a}{p})$ であることと $\sum_{x} (\frac{x ^{2} + c}{p}) = - 1$ （ $p ∤ c$ ）を使い、 $x^{2} + a y^{2} \equiv b (mod p)$ の解の組の個数 $p - (\frac{- a}{p})$ のような値を求められる

前提

平方剰余の相互法則（大学数学整数論）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

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

説明

奇素数 $p$ を法とする 2 次の合同式 $x^{2} \equiv a (mod p)$ の解の個数は、ルジャンドル記号を使うと $1 + (\frac{a}{p})$ という 1 つの式で書けます。これを足し合わせ、和の公式 $\sum_{x} (\frac{x ^{2} + c}{p}) = - 1$ （ $p ∤ c$ ）と組み合わせると、 $x^{2} + a y^{2} \equiv b (mod p)$ のような 2 変数の合同式の解の組の個数を、全部調べずに求められます。答えは $p - (\frac{- a}{p})$ となり、ルジャンドル記号の値は相互法則で求めます。

なぜそうしてよいのか

以下 $p$ は奇素数とし、 $(\frac{0}{p}) = 0$ と約束します。和の範囲 $\sum_{x}$ は $x = 0, 1, \dots, p - 1$ です。まず $x^{2} \equiv a$ の解の個数を考えます。 $a \equiv 0$ なら $p ∣ x^{2}$ より $x \equiv 0$ だけで 1 個です。 $a$ が平方非剰余なら解は 0 個です。 $a$ が平方剰余で $x_{0}^{2} \equiv a$ なら、 $x^{2} - x_{0}^{2} = (x - x_{0}) (x + x_{0}) \equiv 0$ と $p$ が素数であることから $x \equiv \pm x_{0}$ です。 $p$ が奇数で $x_{0} \neq \equiv 0$ なので $x_{0} \neq \equiv - x_{0}$ となり、解はちょうど 2 個です。3 つの場合はどれも $1 + (\frac{a}{p})$ に一致します（値は $1 + 0, 1 - 1, 1 + 1$ ）。

次に、 $1, \dots, p - 1$ のうち平方剰余と平方非剰余はちょうど $\frac{p - 1}{2}$ 個ずつあるので、 $\sum_{t} (\frac{t}{p}) = 0$ です。 $t$ を $t + c$ にずらしても全体を動くので $\sum_{t} (\frac{t + c}{p}) = 0$ も成り立ちます。また、オイラーの規準 $(\frac{a}{p}) \equiv a^{\frac{p - 1}{2}}$ から $(\frac{ab}{p}) = (\frac{a}{p}) (\frac{b}{p})$ （乗法性）が従います。

これらを使って $\sum_{x} (\frac{x ^{2} + c}{p})$ （ $p ∤ c$ ）を計算します。 $x^{2} = t$ となる $x$ は $1 + (\frac{t}{p})$ 個なので、和は $\sum_{t} (1 + (\frac{t}{p})) (\frac{t + c}{p}) = \sum_{t} (\frac{t + c}{p}) + \sum_{t} (\frac{t ( t + c )}{p})$ と書き直せます。第 1 項は $0$ です。第 2 項では $t = 0$ の項が $0$ なので $t \neq = 0$ だけを考えます。 $t^{- 1}$ を $t$ の逆元とすると $t (t + c) \equiv t^{2} (1 + c t^{- 1})$ で、 $(\frac{t ^{2}}{p}) = 1$ より各項は $(\frac{1 + c t ^{- 1}}{p})$ です。 $t$ が $0$ 以外を動くと、 $c t^{- 1}$ も $0$ 以外をすべて 1 回ずつ動きます。したがって $1 + c t^{- 1}$ は「 $1$ 以外のすべての剰余」を 1 回ずつとります。よって第 2 項は $0 - (\frac{1}{p}) = - 1$ となり、 $\sum_{x} (\frac{x ^{2} + c}{p}) = - 1$ が得られます。2 変数の個数は、一方の変数を固定して $1 + (\frac{\cdot}{p})$ を足し上げれば、この和に帰着できます。

手順

条件を確認する: $p$ は奇素数で、 $p ∤ a$ 、 $p ∤ b$ であること。
$y$ を 1 つ固定すると $x^{2} \equiv b - a y^{2}$ の解の個数は $1 + (\frac{b - a y ^{2}}{p})$ 。これを $y = 0, \dots, p - 1$ で足して $N = p + \sum_{y} (\frac{b - a y ^{2}}{p})$ とする。
$b - a y^{2} \equiv - a (y^{2} + c)$ （ $c \equiv - b a^{- 1}$ 、 $p ∤ c$ ）と変形し、乗法性から $(\frac{b - a y ^{2}}{p}) = (\frac{- a}{p}) (\frac{y ^{2} + c}{p})$ とする。
和の公式 $\sum_{y} (\frac{y ^{2} + c}{p}) = - 1$ を使い、 $N = p - (\frac{- a}{p})$ を得る。
$(\frac{- a}{p})$ を補充法則と相互法則で計算し、 $N$ の値を出す。

例題

$x^{2} + 5 y^{2} \equiv 2 (mod 13)$ を満たす整数の組 $(x, y)$ （ $0 \leq x \leq 12, 0 \leq y \leq 12$ ）の個数を求めよ。

例題の解答

【手順 1】 $p = 13$ は奇素数で、 $13 ∤ 5$ 、 $13 ∤ 2$ である。
【手順 2】 $y$ を固定すると、 $x$ の個数は $1 + (\frac{2 - 5 y ^{2}}{13})$ 。よって $N = 13 + \sum_{y} (\frac{2 - 5 y ^{2}}{13})$ 。
【手順 3】 $2 - 5 y^{2} \equiv - 5 (y^{2} + c)$ 、ただし $c \equiv - 2 \cdot 5^{- 1}$ である。 $5 \cdot 8 = 40 \equiv 1$ より $5^{- 1} \equiv 8$ なので、 $c \equiv - 16 \equiv 10$ となり $13 ∤ c$ 。したがって $(\frac{2 - 5 y ^{2}}{13}) = (\frac{- 5}{13}) (\frac{y ^{2} + 10}{13})$ 。
【手順 4】 $\sum_{y} (\frac{y ^{2} + 10}{13}) = - 1$ なので、 $N = 13 - (\frac{- 5}{13})$ 。
【手順 5】 $13 \equiv 1 (mod 4)$ より $(\frac{- 1}{13}) = 1$ 。相互法則より $(\frac{5}{13}) = (\frac{13}{5}) = (\frac{3}{5})$ である。 $mod 5$ の平方は $1, 4$ だけなので $(\frac{3}{5}) = - 1$ 。よって $(\frac{- 5}{13}) = 1 \cdot (- 1) = - 1$ となり、 $N = 13 - (- 1) = 14$ 。

答え: $14$

よくある誤り

$x^{2} \equiv 0 (mod p)$ の解を「 $\pm 0$ で 2 個」と数えてしまう誤り。正しくは $x \equiv 0$ の 1 個だけで、 $1 + (\frac{0}{p}) = 1 + 0 = 1$ と一致する。
和 $\sum_{x} (\frac{x ^{2} + c}{p})$ を、剰余と非剰余が同数だからと $0$ にしてしまう誤り。 $x^{2} + c$ は全剰余を一様には動かないので、正しくは $- 1$ （ $p ∤ c$ のとき）。例えば $p = 3, c = 1$ では $(\frac{1}{3}) + (\frac{2}{3}) + (\frac{2}{3}) = 1 - 1 - 1 = - 1$ 。
$- a$ をくくり出すときに符号を落とし、 $N = p - (\frac{a}{p})$ としてしまう誤り。正しくは $b - a y^{2} \equiv - a (y^{2} - b a^{- 1})$ なので $N = p - (\frac{- a}{p})$ 。 $p \equiv 3 (mod 4)$ では $(\frac{- 1}{p}) = - 1$ なので結果が変わる。
$b \equiv 0$ （つまり $c \equiv 0$ ）のときにも $- 1$ の公式を使ってしまう誤り。 $c \equiv 0$ では $\sum_{x} (\frac{x ^{2}}{p}) = p - 1$ となる。このとき $x^{2} + a y^{2} \equiv 0$ の解の個数は $1 + (p - 1) (1 + (\frac{- a}{p}))$ であり、 $p - (\frac{- a}{p})$ ではない。

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

ルジャンドル記号の和と 2 次合同式の解の個数

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題