平方剰余 (英語版 ) (へいほうじょうよ、英 : quadratic residue )とは、ある自然数 を法としたときの平方数 のことであり、平方剰余の相互法則 (へいほうじょうよのそうごほうそく、英 : law of quadratic reciprocity )は、ある整数 a が別の整数 p の平方剰余であるか否かを判定する法則 である。
ガウス は『整数論 』(1801年)で平方剰余の相互法則の最初の証明を公開した。
整数 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] 。その一つの動機は、三次や四次の相互法則を証明することにあった。現在では240以上もの証明が知られている[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 ′ ≥ 1 を選んで A ′ 2 + B ′ 2 = r′ p とできるアルゴリズム の存在を示すことで行うことができる。
4k + 1 型の素数は第1補充法則より、A 2 + 12 = rp と表すことができるため、このアルゴリズムを適用すればいつかは r を 1 にすることができる。
平方剰余の計算
25 以下の自然数 n , 50 以下の素数 p について、n 2 (mod p ) を計算してみると次の表になる。
さらに見る n, n2 ...
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 + 3 を割り切るような整数 x が存在することと、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}}}
と求められる。