エレファント・コンピューティング調査報告

極限に関する順序を論理プログラミングの手法を使って指定することを目指すブロクです。

平方剰余の相互法則(7)

「平方剰余の相互法則 ガウスの全証明」IV、「数論への出発 増補版」に従って証明します。

ガウスの和の定義】

 \zeta 1の原始  p 乗根とします。整数  a に対して
 \displaystyle g[a] = \sum_{t=0}^{p-1} \left(\cfrac{t}{p}\right) \zeta^{at}
 g = g[1]
と定義します。

【定理1】

  • (a)  g[a] = \left(\cfrac{a}{p}\right) g[1]
  • (b)  g^2 = (-1)^\frac{p-1}{2}p

[証明]

(a)
  •  a≡0 \ (\mathrm{mod} \ p) のとき

 r F_p^* の生成元とします。もし  r≡s^2 \ (\mathrm{mod} \ p) だとすると、 s^{p-1}≡1 \ (\mathrm{mod} \ p) となります。 r^\frac{p-1}{2}≡1 \ (\mathrm{mod} \ p) となり、  r は生成元とはなりません。よって  \left(\cfrac{r}{p}\right) = 1 となります。

 \displaystyle g[a] = \sum_{t=0}^{p-1} \left(\cfrac{t}{p}\right) \zeta^{at} = \sum_{t=0}^{p-1} \left(\cfrac{t}{p}\right) だから
 \displaystyle \left(\cfrac{r}{p}\right) g[a] = \sum_{t=0}^{p-1} \left(\cfrac{r}{p}\right) \left(\cfrac{t}{p}\right) = \sum_{t=0}^{p-1} \left(\cfrac{rt}{p}\right) = \sum_{t=0}^{p-1} \left(\cfrac{t}{p}\right) = g[a]
よって  \displaystyle g[a] \left(\left(\cfrac{r}{p}\right) - 1\right) = 0 g[a] = 0 となります。 \displaystyle \left(\cfrac{a}{p}\right) = 0 より右辺も  0 となります。

  •  a≡0 \ (\mathrm{mod} \ p) ではないとき

 \displaystyle \left(\cfrac{a}{p}\right) g[a] = \sum_{t=0}^{p-1} \left(\cfrac{a}{p}\right) \left(\cfrac{t}{p}\right) \zeta^{at} = \sum_{t=0}^{p-1} \left(\cfrac{at}{p}\right) \zeta^{at} = \sum_{t=0}^{p-1} \left(\cfrac{t}{p}\right) \zeta^{t} = g[1]
となります。

(b)

 \displaystyle g[a]g[-a] = \sum_{x=0}^{p-1} \sum_{y=0}^{p-1} \left(\cfrac{x}{p}\right) \left(\cfrac{y}{p}\right) \zeta^{a(x-y)}
 \displaystyle \sum_{a=0}^{p-1} g[a]g[-a] = \sum_{x=0}^{p-1} \sum_{y=0}^{p-1} \left(\cfrac{x}{p}\right) \left(\cfrac{y}{p}\right) \sum_{a=0}^{p-1} \zeta^{a(x-y)}

  •  x≡y \ (\mathrm{mod} \ p) のとき

 \displaystyle \sum_{a=0}^{p-1} \zeta^{a(x-y)} = \sum_{a=0}^{p-1} 1 = p

  •  x≡y \ (\mathrm{mod} \ p) ではないとき

 z = x - y とおき、
 \begin{eqnarray*}
0 & = & \zeta^{zp} - 1 \\
 & = & (\zeta^z - 1)(\zeta^{z(p-1)} + \zeta^{z(p-2)} + … + \zeta^z + 1) \\
 & = & (\zeta^z - 1) \sum_{a=0}^{p-1} \zeta^{az}
\end{eqnarray*}
 ζ^z - 1 ≠ 0 より  \displaystyle \sum_{a=0}^{p-1} \zeta^{a(x-y)} = 0

よって
 \displaystyle \sum_{a=0}^{p-1} g[a]g[-a] = \sum_{x=0}^{p-1} \sum_{y=0}^{p-1} \left(\cfrac{x}{p}\right) \left(\cfrac{y}{p}\right) \sum_{a=0}^{p-1} \zeta^{a(x-y)}
右辺の  \sum x = 0, 1, 2, … , p-1 y = 0, 1, 2, … , p-1 の範囲を動き、かつ  x≡y \ (\mathrm{mod} \ p) のときだけの和となります。よって  x = y として  x = 0, 1, 2, … , p-1 の範囲を動く和となりますが、 \left(\cfrac{0}{p}\right) = 0 なので  x = 1, 2, … , p-1 の範囲の和となります。
 \displaystyle \sum_{a=0}^{p-1} g[a]g[-a] = \sum_{x=0}^{p-1} \left(\cfrac{x}{p}\right) \left(\cfrac{x}{p}\right) p = (p-1)p …(1)

一方(a)より
 \displaystyle \sum_{a=0}^{p-1} g[a]g[-a] = \sum_{a=0}^{p-1} \left(\cfrac{a}{p}\right) g \left(\cfrac{-a}{p}\right) g = \sum_{a=0}^{p-1} \left(\cfrac{-1}{p}\right) g^2 …(2)

(1)(2)より
 (p - 1)p = \left(\cfrac{-1}{p}\right)(p - 1)g^2
 g^2 = \left(\cfrac{-1}{p}\right)p = (-1)^\frac{p-1}{2}p
[証明終わり]

【平方剰余の相互法則】

 p,  q 2ではない異なる素数のとき、 \left(\cfrac{q}{p}\right) \left(\cfrac{q}{p}\right) = (-1)^\frac{(p-1)(q-1)}{4} が成り立ちます。

[証明]
 p^* = \left(\cfrac{-1}{p}\right) p = (-1)^\frac{p-1}{2}p とおきます。定理1(b)より  p^* = g^2 となります。

オイラーの規準より
 g^{q-1} = (g^2)^{ \frac{p-1}{2} } = (p^*)^{ \frac{p-1}{2} } ≡ \left(\cfrac{p^*}{q}\right) \ (\mathrm{mod} \ q) …(1)

一方定理1(a)より
 \displaystyle g^q = \left( \sum_{t=0}^{p-1} \left(\cfrac{t}{p}\right) \zeta^t \right) ^q ≡ \sum_{t=0}^{p-1} \left(\cfrac{t}{p}\right) ^q\zeta^{qt} = \sum_{t=0}^{p-1} \left(\cfrac{t}{p}\right) \zeta^{qt} = g[q] = \left(\cfrac{q}{p}\right) g \ (\mathrm{mod} \ q)
 g^{q-1} ≡ \left(\cfrac{q}{p}\right) \ (\mathrm{mod} \ q) …(2)
( \mathrm{mod} \ q は、 a\zeta^n という形の数の和について、すべての  n に対応する  a の部分が法  q で合同であることをいいます)

(1)(2)より
 \left(\cfrac{q}{p}\right) = \left(\cfrac{p^*}{q}\right) = \left(\cfrac{-1}{q}\right) ^{ \cfrac{p-1}{2} } \left(\cfrac{p}{q}\right) = (-1)^\cfrac{(p-1)(q-1)}{4} \left(\cfrac{p}{q}\right)
となります。
[証明終わり]

これで終わりですが証明はよくわからない部分があるので後で見直してみます。