平方剰余の相互法則

平方剰余（へいほうじょうよ）とは、ある自然数を法としたときの平方数のことであり、平方剰余の相互法則（へいほうじょうよのそうごほうそく、quadratic reciprocity）は、ある整数 a が平方剰余であるか否かを見いだす法則である。

定義

a と p とが互いに素であるとき、合同式

$x^2 \equiv a\pmod p$

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

(p, a) を a と p の最大公約数とするとき、次の記号

$\left( \frac{a}{p} \right) = \left\{\begin{matrix} 1 & \mbox{if }(p,a)=1,&x^2 \equiv a \mbox{ (mod }p) \mbox{ for some } x\ \\ 0 & \mbox{if }(p,a)\neq 1\ &\\ -1 & \mbox{if }(p,a)=1,&x^2\ \not\equiv\ a \mbox{ (mod }p) \mbox{ for any } x \quad \end{matrix}\right.$

を、アドリアン＝マリ・ルジャンドルにちなんでルジャンドル記号と呼ぶ。

相互法則

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

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

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

が成り立つ。

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

第1補充法則:

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

第2補充法則:

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

またpとa、bが素であれば、

$\left( \frac{ab}{p} \right) = \left( \frac{a}{p} \right) \left( \frac{b}{p} \right)$

が成立する。一般にZ_p^x={1,2,...,p-1}はpを法として乗法に関して群になることが知られているが、この式はZ_p^xより{-1, 1}への準同型写像が存在することを示している。故にその写像の核は位数(p-1)/2の部分群となり、Z_p^xの要素の半分は平方剰余であり半分は平方非剰余であることが分かる。

この法則は、レオンハルト・オイラーによって予想され、カール・フリードリッヒ・ガウスによって証明された（ガウス日誌によれば、1796年4月8日。発表されたのは1801年の『整数論』において）。ガウスはこの法則に対して生涯で7つの異なる証明を与えた。その一つの動機は、三次や四次の相互法則を証明することにあった。現在では200近くもの証明が知られている。しかし、どれもそれほど簡単ではない。

三次や四次の相互法則は、ヤコビ、アイゼンシュタインによって独立に証明された（1844年にアイゼンシュタインが証明を公表）。より高次のまた一般的な代数的整数における一般的な相互法則の証明は（ヒルベルトの第9問題）、高木貞治やエミール・アルティンによってなされた。

平方剰余の相互法則の応用

4k+1型の素数は二個の平方数の和で表すことができる。また逆にある奇素数が二つの平方数の和で表すことができるならば、4k+1型の素数である。

$\begin{alignat}{2} 5 &= 1^2 + 2^2\\ 13 &= 2^2 + 3^2\\ 17 &= 1^2 + 4^2\\ 29 &= 2^2 + 5^2\\ 37 &= 1^2 + 6^2\\ 41 &= 4^2 + 5^2\\ 53 &= 2^2 + 7^2\\ 61 &= 5^2 + 6^2 \end{alignat}$

証明はある素数pに対して $A^2+B^2=r p$ と表せたとすれば、より小さい$r' (\ge 1)$を選び $A'^2+B'^2=r' p$ とすることができるアルゴリズムが存在することで行うことができる。

4k+1型の素数は第1補充法則より、$A^2+1^2=r p$と表すことができるため、このアルゴリズムを適用すればいつかは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 の場合

$\left( \frac{a}{3} \right) = \left\{\begin{matrix} 1 &a \equiv 1 \mbox{ (mod }3) \\ -1 &a \equiv 2 \mbox{ (mod }3) \\ 0 &a \equiv 0 \mbox{ (mod }3) \\ \end{matrix}\right.$

となることが分かる。qを3と異なる奇素数とすると、

$\left( \frac{q}{3} \right) = \left\{\begin{matrix} 1 &q \equiv 1 \mbox{ (mod }6) \\ -1 &q \equiv 5 \mbox{ (mod }6) \\ \end{matrix}\right.$

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

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

となり、

$\left( \frac{3}{q} \right) = \left\{\begin{matrix} 1 &q \equiv \pm 1 \mbox{ (mod }12) \\ -1 &q \equiv \pm 5 \mbox{ (mod }12) \\ \end{matrix}\right.$

と求めることができる。
ここで、第1補充法則より、

$\left( \frac{3}{q} \right) \left( \frac{q}{3} \right) = (-1)^{ \frac{q-1}{2} } = \left( \frac{-1}{q} \right)$

したがって、

$\left( \frac{-3}{q} \right) = \left( \frac{3}{q} \right) \left( \frac{-1}{q} \right) = \left( \frac{q}{3} \right) = \left\{\begin{matrix} 1 &q \equiv 1 \mbox{ (mod }6) \\ -1 &q \equiv 5 \mbox{ (mod }6) \\ \end{matrix}\right.$

p=5 の場合

同様にして、qを5と異なる奇素数とすると、

$\left( \frac{q}{5} \right) = \left\{\begin{matrix} 1 &q \equiv \pm 1 \mbox{ (mod }5) \\ -1 &q \equiv \pm 2 \mbox{ (mod }5) \\ \end{matrix}\right.$

平方剰余の相互法則を使うと、

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

となり、

$\left( \frac{5}{q} \right) = \left\{\begin{matrix} 1 &q \equiv \pm 1 \mbox{ (mod }5) \\ -1 &q \equiv \pm 2 \mbox{ (mod }5) \\ \end{matrix}\right.$

と求めることができる。

関連項目

• 三次剰余の相互法則
• 四次剰余の相互法則