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

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

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

以前別のところで書いたことがあるものですがここにも書いておきます。

【平方剰余】

ある整数  x の平方を整数  a で割ったときの余りが  b であるとき、 b を法  a に関する平方剰余といいます。

ルジャンドルの記号】

  •  b が法  a に関する平方剰余であるとき  \left(\cfrac{b}{a}\right) = 1
  •  b が法  a に関する平方剰余ではないとき  \left(\cfrac{b}{a}\right) = -1

 \left(\cfrac{b}{a}\right) を定義します。

この記法を拡張したものもあるようなので書いておきます。奇素数  a と 整数  b に対して

  •  b a の倍数ではなく、ある整数  x に対して  x^2 \equiv b \ (\mathrm{mod} \ a) であるとき  \left(\cfrac{b}{a}\right) = 1
  •  b a の倍数ではなく、任意の整数  x に対して  x^2 \not \equiv b \ (\mathrm{mod} \ a) であるとき  \left(\cfrac{b}{a}\right) = -1
  •  b a の倍数であるとき  \left(\cfrac{b}{a}\right) = 0

と定義します。

【平方剰余の相互法則】

 p,  q 2ではない素数のとき、( p,  q は奇数なので、 4で割ると 1余るか 3余るかのどちらかとなります)

  •  p 4で割ると 1余るか、または、 q 4で割ると 1余るときは、 \left(\cfrac{p}{q}\right) = \left(\cfrac{q}{p}\right)
  •  p 4で割ると 3余り、かつ、 q 4で割ると 3余るときは、 \left(\cfrac{p}{q}\right) = -\left(\cfrac{q}{p}\right)

が成り立ちます。これを平方剰余の相互法則といいます。

以下の表は縦に  p、横に  q をとったとき q が法 p に関する平方剰余のとき●、そうでないとき○とした表です。

0003
0005
0007
0011
0013
0017
0019
0023
0029
0031
0037
0041
0043
0047

 p 4で割ると 3余り、かつ、 q 4で割ると 3余るときに対角線より右上の部分の●と○を入れ替えたら、以下のように対角線に関して対称になります。

0003
0005
0007
0011
0013
0017
0019
0023
0029
0031
0037
0041
0043
0047

以下の表は縦に  p、横に  a = 1, 2, 3, … をとったとき  a が法  p に関する平方剰余のとき●、そうでないとき○とした表です。

0003 ●○
0005 ●○○●
0007 ●●○●○○
0011 ●○●●●○○○●○
0013 ●○●●○○○○●●○●
0017 ●●○●○○○●●○○○●○●●
0019 ●○○●●●●○●○●○○○○●●○
0023 ●●●●○●○●●○○●●○○●○●○○○○
0029 ●○○●●●●○●○○○●○○●○○○●○●●●●○○●
0031 ●●○●●○●●●●○○○●○●○●●●○○○○●○○●○○
0037 ●○●●○○●○●●●●○○○●○○○○●○○○●●●●○●○○●●○●
0041 ●●○●●○○●●●○○○○○●○●○●●○●○●○○○○○●●●○○●●○●●
0043 ●○○●○●○○●●●○●●●●●○○○●○●●●○○○○○●○○○●●○●○●●○
0047 ●●●●○●●●●○○●○●○●●●○○●○○●●○●●○○○●○●○●●○○○○●○○○○

 p 4で割ると 3余るときに中央より右の部分の●と○を入れ替えたら、以下のように左右対称になります。

0003
0005
0007
0011
0013
0017
0019
0023
0029
0031
0037
0041
0043
0047

【平方剰余の相互法則・第1補充法則】

 p 2ではない素数のとき、( p は奇数なので、 4で割ると 1余るか 3余るかのどちらかとなります)

  •  p 4で割ると 1余るときは、 -1 は法  p に関する平方剰余であり、
  •  p 4で割ると 3余るときは、 -1 は法  p に関する平方剰余ではありません。

以下の表は縦に  p をとったとき  -1 が法  p に関する平方剰余のとき■、そうでないとき□としたものを1列目に、 p 4で割ると 3余るときは、■と□を入れ替えたものを2列目に書いたものです。

0003
0005
0007
0011
0013
0017
0019
0023
0029
0031
0037
0041
0043
0047

【平方剰余の相互法則・第2補充法則】

 p 2ではない素数のとき、( p は奇数なので、 8で割ると余りは 1,  3,  5,  7のどれかになります)

  •  p 8で割ると 1または 7余るときは、 2 は法  p に関する平方剰余であり、
  •  p 4で割ると 3または 5余るときは、 2 は法  p に関する平方剰余ではありません。

以下の表は縦に  p をとったとき  2 が法  p に関する平方剰余のとき■、そうでないとき□としたものを1列目に、 p 8で割ると 1または 7余るときは、■と□を入れ替えたものを2列目に書いたものです。

0003
0005
0007
0011
0013
0017
0019
0023
0029
0031
0037
0041
0043
0047

オイラーの規準】

 p 2ではない素数 a p と素な整数のとき、

  •  a が法  p に関する平方剰余のとき、 a (p-1)/2 乗を  p で割ったときの余りは  1
  •  a が法  p に関する平方剰余ではないとき、 a (p-1)/2 乗を  p で割ったときの余りは  p-1 になります。

以下の表は縦に  p、横に  a = 1, 2, 3, … をとったとき  a (p-1)/2 乗を  p で割ったときの余りが  1 のとき■、 -1 のとき□とした表です。

0003 ■□
0005 ■□□■
0007 ■■□■□□
0011 ■□■■■□□□■□
0013 ■□■■□□□□■■□■
0017 ■■□■□□□■■□□□■□■■
0019 ■□□■■■■□■□■□□□□■■□
0023 ■■■■□■□■■□□■■□□■□■□□□□
0029 ■□□■■■■□■□□□■□□■□□□■□■■■■□□■
0031 ■■□■■□■■■■□□□■□■□■■■□□□□■□□■□□
0037 ■□■■□□■□■■■■□□□■□□□□■□□□■■■■□■□□■■□■
0041 ■■□■■□□■■■□□□□□■□■□■■□■□■□□□□□■■■□□■■□■■
0043 ■□□■□■□□■■■□■■■■■□□□■□■■■□□□□□■□□□■■□■□■■□
0047 ■■■■□■■■■□□■□■□■■■□□■□□■■□■■□□□■□■□■■□□□□■□□□□