平方剰余の相互法則
ガウス は『整数論 』（1801年）で平方剰余の相互法則の最初の証明を公開した。平方剰余 （英語版 ） 英 : quadratic residue 自然数 を法としたときの平方数 のことであり、平方剰余の相互法則 （へいほうじょうよのそうごほうそく、英 : law of quadratic reciprocity 整数 a が別の整数 p の平方剰余であるか否かを判定する法則 である。
整数 a と p とが互いに素 であるとする。合同式
x
2
≡ ≡ -->
a
(
mod
p
)
{\displaystyle x^{2}\equiv a{\pmod {p}}}
が解を持つとき、a は p を法として平方剰余 であるといい、そうでないとき平方非剰余 であるという。
奇素数 p と、p と互いに素な整数 a に対して、記号
(
a
p
)
:=
{
1
if
∃ ∃ -->
x
∈ ∈ -->
Z
[
x
2
≡ ≡ -->
a
(
mod
p
)
]
− − -->
1
if
∀ ∀ -->
x
∈ ∈ -->
Z
[
x
2
≢
a
(
mod
p
)
]
{\displaystyle \left({\frac {a}{p}}\right):={\begin{cases}1&{\text{if }}\exists x\in \mathbb {Z} [x^{2}\equiv a{\pmod {p}}]\\-1&{\text{if }}\forall x\in \mathbb {Z} [x^{2}\not \equiv a{\pmod {p}}]\end{cases}}}
を定める。
奇素数 p で割り切れるような整数 a に対しても
(
a
p
)
:=
0
{\displaystyle \left({\frac {a}{p}}\right):=0}
と定めておくことがある。
記号
(
a
p
)
{\displaystyle \left({\frac {a}{p}}\right)}
平方剰余記号 、またはアドリアン＝マリ・ルジャンドル にちなんでルジャンドル記号
平方剰余の相互法則 は整数 a が奇素数 p を法として平方剰余であるか否かを判定する法則 である。
p , q を相異なる奇素数とするときに、
(
p
q
)
(
q
p
)
=
(
− − -->
1
)
p
− − -->
1
2
⋅ ⋅ -->
q
− − -->
1
2
{\displaystyle \left({\frac {p}{q}}\right)\left({\frac {q}{p}}\right)=(-1)^{{\frac {p-1}{2}}\cdot {\frac {q-1}{2}}}}
が成り立つ。 また、このほかに以下の第1補充法則、第2補充法則が知られている。
第1補充法則:
(
− − -->
1
p
)
=
(
− − -->
1
)
p
− − -->
1
2
.
{\displaystyle \left({\frac {-1}{p}}\right)=(-1)^{\frac {p-1}{2}}.}
第2補充法則:
(
2
p
)
=
(
− − -->
1
)
p
2
− − -->
1
8
.
{\displaystyle \left({\frac {2}{p}}\right)=(-1)^{\frac {p^{2}-1}{8}}.}
また、p と互いに素な整数 a , b に対して
(
a
b
p
)
=
(
a
p
)
(
b
p
)
{\displaystyle \left({\frac {ab}{p}}\right)=\left({\frac {a}{p}}\right)\left({\frac {b}{p}}\right)}
が成立する。一般に素数 p に対して F p × = {1, 2, ..., p − 1}p を法とする乗法に関して群 をなすが、この式はルジャンドル記号が F p × {−1, 1} への群準同型 を与えることを示している。この写像の核 は位数 (p − 1)/2 の部分群であり、F p ×
この法則は、レオンハルト・オイラー によって予想され、カール・フリードリッヒ・ガウス によって証明された（ガウス日誌によれば、1796年 4月8日 。発表されたのは1801年 の『整数論 』において）。ガウスはこの法則に対して生涯で7つ（または8つ）の異なる証明を与えた[ 1] [ 1]
三次や四次の相互法則は、ヤコビ 、アイゼンシュタイン によって独立に証明された（1844年 にアイゼンシュタインが証明を公表）。より高次のまた一般的な代数的整数における一般的な相互法則の証明は（ヒルベルトの第9問題 ）、高木貞治 やエミール・アルティン によってなされた。（アルティン相互法則 を参照）
4k + 1 型の素数は二個の平方数の和 で表すことができる。また逆にある奇素数が二つの平方数の和で表すことができるならば、4k + 1 型の素数である。そして、二つの平方数の順序を別にすればこの分解は一意的である。
5
=
1
2
+
2
2
,
113
=
7
2
+
8
2
,
277
=
9
2
+
14
2
,
421
=
14
2
+
15
2
,
13
=
2
2
+
3
2
,
137
=
4
2
+
11
2
,
281
=
5
2
+
16
2
,
433
=
12
2
+
17
2
,
17
=
1
2
+
4
2
,
149
=
7
2
+
10
2
,
293
=
2
2
+
17
2
,
449
=
7
2
+
20
2
,
29
=
2
2
+
5
2
,
157
=
6
2
+
11
2
,
313
=
12
2
+
13
2
,
457
=
4
2
+
21
2
,
37
=
1
2
+
6
2
,
173
=
2
2
+
13
2
,
317
=
11
2
+
14
2
,
461
=
10
2
+
19
2
,
41
=
4
2
+
5
2
,
181
=
9
2
+
10
2
,
337
=
9
2
+
16
2
,
509
=
5
2
+
22
2
,
53
=
2
2
+
7
2
,
193
=
7
2
+
12
2
,
349
=
5
2
+
18
2
,
521
=
11
2
+
20
2
,
61
=
5
2
+
6
2
,
197
=
1
2
+
14
2
,
353
=
8
2
+
17
2
,
541
=
10
2
+
21
2
,
73
=
3
2
+
8
2
,
229
=
2
2
+
15
2
,
373
=
7
2
+
18
2
,
557
=
14
2
+
19
2
,
89
=
5
2
+
8
2
,
233
=
8
2
+
13
2
,
389
=
10
2
+
17
2
,
569
=
13
2
+
20
2
,
97
=
4
2
+
9
2
,
241
=
4
2
+
15
2
,
397
=
6
2
+
19
2
,
577
=
1
2
+
24
2
,
101
=
1
2
+
10
2
,
257
=
1
2
+
16
2
,
401
=
1
2
+
20
2
,
593
=
8
2
+
23
2
,
109
=
3
2
+
10
2
,
269
=
10
2
+
13
2
,
409
=
3
2
+
20
2
,
601
=
5
2
+
24
2
.
{\displaystyle {\begin{aligned}5&=1^{2}+2^{2},&113&=7^{2}+8^{2},&277&=9^{2}+14^{2},&421&=14^{2}+15^{2},\\13&=2^{2}+3^{2},&137&=4^{2}+11^{2},&281&=5^{2}+16^{2},&433&=12^{2}+17^{2},\\17&=1^{2}+4^{2},&149&=7^{2}+10^{2},&293&=2^{2}+17^{2},&449&=7^{2}+20^{2},\\29&=2^{2}+5^{2},&157&=6^{2}+11^{2},&313&=12^{2}+13^{2},&457&=4^{2}+21^{2},\\37&=1^{2}+6^{2},&173&=2^{2}+13^{2},&317&=11^{2}+14^{2},&461&=10^{2}+19^{2},\\41&=4^{2}+5^{2},&181&=9^{2}+10^{2},&337&=9^{2}+16^{2},&509&=5^{2}+22^{2},\\53&=2^{2}+7^{2},&193&=7^{2}+12^{2},&349&=5^{2}+18^{2},&521&=11^{2}+20^{2},\\61&=5^{2}+6^{2},&197&=1^{2}+14^{2},&353&=8^{2}+17^{2},&541&=10^{2}+21^{2},\\73&=3^{2}+8^{2},&229&=2^{2}+15^{2},&373&=7^{2}+18^{2},&557&=14^{2}+19^{2},\\89&=5^{2}+8^{2},&233&=8^{2}+13^{2},&389&=10^{2}+17^{2},&569&=13^{2}+20^{2},\\97&=4^{2}+9^{2},&241&=4^{2}+15^{2},&397&=6^{2}+19^{2},&577&=1^{2}+24^{2},\\101&=1^{2}+10^{2},&257&=1^{2}+16^{2},&401&=1^{2}+20^{2},&593&=8^{2}+23^{2},\\109&=3^{2}+10^{2},&269&=10^{2}+13^{2},&409&=3^{2}+20^{2},&601&=5^{2}+24^{2}.\end{aligned}}}
証明は、ある素数 p に対して A 2 + B 2 = rp r より真に小さい r ′ ≥ 1A ′2 + B ′2 = r′p アルゴリズム の存在を示すことで行うことができる。
4k + 1 型の素数は第1補充法則より、A 2 + 12 = rp r を 1 にすることができる。
25 以下の自然数 n , 50 以下の素数 p について、n 2 (mod p )
n 2 (mod p ) の計算表
n
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
n 2
1
4
9
16
25
36
49
64
81
100
121
144
169
196
225
256
289
324
361
400
441
484
529
576
625
mod 3
1
1
0
1
1
0
1
1
0
1
1
0
1
1
0
1
1
0
1
1
0
1
1
0
1
mod 5
1
4
4
1
0
1
4
4
1
0
1
4
4
1
0
1
4
4
1
0
1
4
4
1
0
mod 7
1
4
2
2
4
1
0
1
4
2
2
4
1
0
1
4
2
2
4
1
0
1
4
2
2
mod 11
1
4
9
5
3
3
5
9
4
1
0
1
4
9
5
3
3
5
9
4
1
0
1
4
9
mod 13
1
4
9
3
12
10
10
12
3
9
4
1
0
1
4
9
3
12
10
10
12
3
9
4
1
mod 17
1
4
9
16
8
2
15
13
13
15
2
8
16
9
4
1
0
1
4
9
16
8
2
15
13
mod 19
1
4
9
16
6
17
11
7
5
5
7
11
17
6
16
9
4
1
0
1
4
9
16
6
17
mod 23
1
4
9
16
2
13
3
18
12
8
6
6
8
12
18
3
13
2
16
9
4
1
0
1
4
mod 29
1
4
9
16
25
7
20
6
23
13
5
28
24
22
22
24
28
5
13
23
6
20
7
25
16
mod 31
1
4
9
16
25
5
18
2
19
7
28
20
14
10
8
8
10
14
20
28
7
19
2
18
5
mod 37
1
4
9
16
25
36
12
27
7
26
10
33
21
11
3
34
30
28
28
30
34
3
11
21
33
mod 41
1
4
9
16
25
36
8
23
40
18
39
21
5
32
20
10
2
37
33
31
31
33
37
2
10
mod 43
1
4
9
16
25
36
6
21
38
14
35
15
40
24
10
41
31
23
17
13
11
11
13
17
23
mod 47
1
4
9
16
25
36
2
17
34
6
27
3
28
8
37
21
7
42
32
24
18
14
12
12
14
p = 3
(
a
3
)
=
{
1
if
a
≡ ≡ -->
1
(
mod
3
)
− − -->
1
if
a
≡ ≡ -->
2
(
mod
3
)
0
if
a
≡ ≡ -->
0
(
mod
3
)
{\displaystyle \left({\frac {a}{3}}\right)={\begin{cases}1&{\text{if }}a\equiv 1{\pmod {3}}\\-1&{\text{if }}a\equiv 2{\pmod {3}}\\0&{\text{if }}a\equiv 0{\pmod {3}}\end{cases}}}
となる。q が 3 と異なる奇素数 ならば、
(
q
3
)
=
{
1
if
q
≡ ≡ -->
1
(
mod
6
)
− − -->
1
if
q
≡ ≡ -->
5
(
mod
6
)
{\displaystyle \left({\frac {q}{3}}\right)={\begin{cases}1&{\text{if }}q\equiv 1{\pmod {6}}\\-1&{\text{if }}q\equiv 5{\pmod {6}}\end{cases}}}
と表せる。ここで、平方剰余の相互法則 を使うと、
(
3
q
)
(
q
3
)
=
(
− − -->
1
)
3
− − -->
1
2
⋅ ⋅ -->
q
− − -->
1
2
=
(
− − -->
1
)
q
− − -->
1
2
{\displaystyle {\biggl (}{\frac {3}{q}}{\biggr )}{\biggl (}{\frac {q}{3}}{\biggr )}=(-1)^{{\frac {3-1}{2}}\cdot {\frac {q-1}{2}}}=(-1)^{\frac {q-1}{2}}}
となり、
(
3
q
)
=
{
1
if
q
≡ ≡ -->
± ± -->
1
(
mod
12
)
− − -->
1
if
q
≡ ≡ -->
± ± -->
5
(
mod
12
)
{\displaystyle \left({\frac {3}{q}}\right)={\begin{cases}1&{\text{if }}q\equiv \pm 1{\pmod {12}}\\-1&{\text{if }}q\equiv \pm 5{\pmod {12}}\end{cases}}}
と求められる。今 q は 3 とも −1 とも互いに素であり、このことと第1補充法則より
(
− − -->
3
q
)
=
(
− − -->
1
q
)
(
3
q
)
=
(
− − -->
1
)
q
− − -->
1
2
⋅ ⋅ -->
2
(
q
3
)
=
(
q
3
)
=
{
1
if
q
≡ ≡ -->
1
(
mod
6
)
− − -->
1
if
q
≡ ≡ -->
5
(
mod
6
)
{\displaystyle \left({\frac {-3}{q}}\right)=\left({\frac {-1}{q}}\right)\left({\frac {3}{q}}\right)=(-1)^{{\frac {q-1}{2}}\cdot 2}{\biggl (}{\frac {q}{3}}{\biggr )}={\biggl (}{\frac {q}{3}}{\biggr )}={\begin{cases}1&{\text{if }}q\equiv 1{\pmod {6}}\\-1&{\text{if }}q\equiv 5{\pmod {6}}\end{cases}}}
と求められる。即ち、3 と異なる奇素数 q に対して、q が x 2 + 3x が存在することと、q が 6 を法として 1 に合同であることは同値である。
p = 5同様にして、q を 5 と異なる奇素数 とすると、
(
q
5
)
=
{
1
if
q
≡ ≡ -->
± ± -->
1
(
mod
5
)
− − -->
1
if
q
≡ ≡ -->
± ± -->
2
(
mod
5
)
.
{\displaystyle \left({\frac {q}{5}}\right)={\begin{cases}1&{\text{if }}q\equiv \pm 1{\pmod {5}}\\-1&{\text{if }}q\equiv \pm 2{\pmod {5}}.\end{cases}}}
ゆえに平方剰余の相互法則 から
(
5
q
)
(
q
5
)
=
(
− − -->
1
)
5
− − -->
1
2
⋅ ⋅ -->
q
− − -->
1
2
=
1
{\displaystyle {\biggl (}{\frac {5}{q}}{\biggr )}{\biggl (}{\frac {q}{5}}{\biggr )}=(-1)^{{\frac {5-1}{2}}\cdot {\frac {q-1}{2}}}=1}
となり、よって
(
5
q
)
=
{
1
if
q
≡ ≡ -->
± ± -->
1
(
mod
5
)
− − -->
1
if
q
≡ ≡ -->
± ± -->
2
(
mod
5
)
{\displaystyle \left({\frac {5}{q}}\right)={\begin{cases}1&{\text{if }}q\equiv \pm 1{\pmod {5}}\\-1&{\text{if }}q\equiv \pm 2{\pmod {5}}\end{cases}}}
と求められる。
![{\displaystyle \left({\frac {a}{p}}\right):={\begin{cases}1&{\text{if }}\exists x\in \mathbb {Z} [x^{2}\equiv a{\pmod {p}}]\\-1&{\text{if }}\forall x\in \mathbb {Z} [x^{2}\not \equiv a{\pmod {p}}]\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/575cd9645c711d7e7e14e6688897076a34abb651)
