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

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

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

【平方剰余の相互法則】

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

[証明]
「平方剰余の相互法則 ガウスの全証明」Vに従って証明します。 0 から  pq - 1 までの数  a を以下のように  p×q の長方形の形に並べます。

  • [1] 縦  x, 横  y の位置には、 a p で割った余りが  x a q で割った余りが  y であるような  a が来るようにします。Chinese Remainder Theoremにより、このような並べ方はできます。
  • [2] 先に横方向に  0, 1, 2, … と並べます(縦  x, 横  y の位置には  qx + y)。
  • [3] 先に縦方向に  0, 1, 2, … と並べます(縦  x, 横  y の位置には  py + x)。

 p=11,  q=7 のときは以下の図のようになります。
[1]

0000 00 56 35 14 70 49 28 07 63 42 21
0001 22 01 57 36 15 71 50 29 08 64 43
0002 44 23 02 58 37 16 72 51 30 09 65
0003 66 45 24 03 59 38 17 73 52 31 10
0004 11 67 46 25 04 60 39 18 74 53 32
0005 33 12 68 47 26 05 61 40 19 75 54
0006 55 34 13 69 48 27 06 62 41 20 76

[2]

0000 00 01 02 03 04 05 06 07 08 09 10
0001 11 12 13 14 15 16 17 18 19 20 21
0002 22 23 24 25 26 27 28 29 30 31 32
0003 33 34 35 36 37 38 39 40 41 42 43
0004 44 45 46 47 48 49 50 51 52 53 54
0005 55 56 57 58 59 60 61 62 63 64 65
0006 66 67 68 69 70 71 72 73 74 75 76

[3]

0000 00 07 14 21 28 35 42 49 56 63 70
0001 01 08 15 22 29 36 43 50 57 64 71
0002 02 09 16 23 30 37 44 51 58 65 72
0003 03 10 17 24 31 38 45 52 59 66 73
0004 04 11 18 25 32 39 46 53 60 67 74
0005 05 12 19 26 33 40 47 54 61 68 75
0006 06 13 20 27 34 41 48 55 62 69 76

 0 以外の  1 から  pq - 1 までの数  a を以下のように分類します。

Α Γ Β Δ Ε α β ε δ γ
(*1)
(*2)
(*3)
  • (*1) +は  0 < a < \cfrac{pq}{2} のとき、-は  a > \cfrac{pq}{2} のとき
  • (*2) +は  0 < a \ \mathrm{mod} \ p < \cfrac{p}{2} のとき、-は  a \ \mathrm{mod} \ p > \cfrac{p}{2} のとき、0は  a \ \mathrm{mod} \ p = 0 のとき
  • (*3) +は  0 < a \ \mathrm{mod} \ q < \cfrac{q}{2} のとき、-は  a \ \mathrm{mod} \ q > \cfrac{q}{2} のとき、0は  a \ \mathrm{mod} \ q = 0 のとき

 a \ \mathrm{mod} \ p x p で割った余りを表します( a≡b \ ( \mathrm{mod} \ p) となる  b のうちで 0か正の数の中で最小のもの)。
[1]

0000 × α α α Α Α Α
0001 ε ε δ Γ Γ δ δ
0002 β ε δ δ Γ Γ δ
0003 β ε ε Γ δ δ Γ Γ
0004 Β γ γ Δ Δ γ Ε Ε
0005 Β Δ γ γ Δ Δ Ε
0006 Δ Δ γ γ Δ Ε Ε

[1]の図より

  • ■の個数 = □の個数 (図では 2)
  • Αの個数 = αの個数 (図では 3) (これを  a とおきます)
  • ▲の個数 = △の個数 (図では 1)
  • Βの個数 = βの個数 (図では 2) (これを  b とおきます)
  • ●の個数 = ○の個数 (図では 10)
  • Γの個数 = γの個数 (図では 7) (これを  c とおきます)
  • Δの個数 = δの個数 (図では 8) (これを  d とおきます)
  • Εの個数 = εの個数 (図では 5) (これを  e とおきます)

となります。
ガウス補題より

  • Α(α)の個数が偶数 ⇔  q p を法とする平方剰余
  • Β(β)の個数が偶数 ⇔  p q を法とする平方剰余

よって  \left(\cfrac{q}{p}\right) = (-1)^a \left(\cfrac{p}{q}\right) = (-1)^b
となります。
[1]の図の右上の部分より
Γ(γ)の個数( c) + δ(Δ)の個数( d) =  \cfrac{(p-1)(q-1)}{4} (図では 15)
となります。
[2]

0000 × Δ Δ Ε Α Γ Γ Γ
0001 Β Δ Δ Γ Ε Ε Ε Α
0002 Δ Δ Δ Α Γ Γ Γ Ε
0003 Β Δ δ
0004 β ε γ γ γ α δ δ δ
0005 α ε ε ε γ δ δ
0006 β γ γ γ α ε δ δ

[2]の図の右上の部分より
Α(α)の個数( a) + Γ(γ)の個数( c) + Ε(ε)の個数( e) =  \cfrac{(p-1)(q-1)}{4} (図では 15)
となります。
[3]

0000 × Α Α Α α α α
0001 Γ Γ δ δ ε δ ε
0002 Γ Γ β δ ε δ δ
0003 Γ Γ Γ ε δ ε β δ
0004 Δ Β Ε Δ Ε γ γ γ
0005 Δ Δ Ε Δ Β γ γ
0006 Ε Δ Ε Δ Δ γ γ

[3]の図の右上の部分より
Β(β)の個数( b) + Δ(δ)の個数( d) + Ε(ε)の個数( e) =  \cfrac{(p-1)(q-1)}{4} (図では 15)
となります。
よってγの個数を  c、δの個数を  d、εの個数を  e とすると
 \begin{eqnarray*} a + b & = & (a + c + e) + (b + d + e) - (c + d) - 2e \\
 & = & \cfrac{(p-1)(q-1)}{4} - 2e \end{eqnarray*}
 \left(\cfrac{q}{p}\right) \left(\cfrac{p}{q}\right) = (-1)^{a+b} = (-1)^{ \frac{(p-1)(q-1)}{4} }
となります。
[証明終わり]