平方剰余の相互法則

平方剰余（英語版）（へいほうじょうよ、英: quadratic residue）とは、ある自然数を法としたときの平方数のことであり、平方剰余の相互法則（へいほうじょうよのそうごほうそく、英: law of quadratic reciprocity）は、ある整数 a が別の整数 p の平方剰余であるか否かを判定する法則である。

ガウスは『整数論』（1801年）で平方剰余の相互法則の最初の証明を公開した。

定義

整数 a と p とが互いに素であるとする。合同式

${\displaystyle x^{2}\equiv a{\pmod {p}}}$

が解を持つとき、a は p を法として平方剰余であるといい、そうでないとき平方非剰余であるという。

平方剰余記号

奇素数 p と、p と互いに素な整数 a に対して、記号

${\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}}}$

を定める。

a と p が互いに素ではない場合、つまり整数 a が奇素数 p で割り切れる場合には、ｘ=0とすれば a は法ｐでｘの2乗と合同なのでaは平方剰余であるが、その場合にはむしろ記号の値を零とする方が都合の良いことがあるので、

${\displaystyle \left({\frac {a}{p}}\right):=0}$

と定義することがある。

記号 ${\displaystyle \left({\frac {a}{p}}\right)}$ を、平方剰余記号、またはアドリアン＝マリ・ルジャンドルにちなんでルジャンドル記号と呼ぶ。

相互法則

平方剰余の相互法則は整数 a が奇素数 p を法として平方剰余であるか否かを判定する法則である。

p, q を相異なる奇素数とするときに、

${\displaystyle \left({\frac {p}{q}}\right)\left({\frac {q}{p}}\right)=(-1)^{{\frac {p-1}{2}}\cdot {\frac {q-1}{2}}}}$

が成り立つ。

また、このほかに以下の第1補充法則、第2補充法則が知られている。

第1補充法則:

${\displaystyle \left({\frac {-1}{p}}\right)=(-1)^{\frac {p-1}{2}}.}$

第2補充法則:

${\displaystyle \left({\frac {2}{p}}\right)=(-1)^{\frac {p^{2}-1}{8}}.}$

また、p と互いに素な整数 a, b に対して

${\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 型の素数である。そして、二つの平方数の順序を別にすればこの分解は一意的である。

${\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² + B² = rp と表せたならば r より真に小さい r′ ≥ 1 を選んで A′² + B′² = r′p とできるアルゴリズムの存在を示すことで行うことができる。

4k + 1 型の素数は第1補充法則より、A² + 1² = rp と表すことができるため、このアルゴリズムを適用すればいつかは r を 1 にすることができる。

平方剰余の計算

25 以下の自然数 n, 50 以下の素数 p について、n² (mod p) を計算してみると次の表になる。

n² (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
n2	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 の場合

${\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 と異なる奇素数ならば、

${\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}}}$

と表せる。ここで、平方剰余の相互法則を使うと、

${\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}}}$

となり、

${\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補充法則より

${\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² + 3 を割り切るような整数 x が存在することと、q が 6 を法として 1 に合同であることは同値である。

p = 5 の場合

同様にして、q を 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}}}$

ゆえに平方剰余の相互法則から

${\displaystyle {\biggl (}{\frac {5}{q}}{\biggr )}{\biggl (}{\frac {q}{5}}{\biggr )}=(-1)^{{\frac {5-1}{2}}\cdot {\frac {q-1}{2}}}=1}$

となり、よって

${\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}}}$

と求められる。