平方剰余の相互法則

平方剰余（英語版）（へいほうじょうよ、英: 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 に対して Zp× = {1, 2, ..., p − 1} は p を法とする乗法に関して群をなすが、この式はルジャンドル記号が Zp× から{−1, 1} への群準同型を与えることを示している。この写像の核は位数 (p − 1)/2 の部分群であり、Zp× の元のちょうど半分が平方剰余、残り半分が平方非剰余となる。 この法則は、レオンハルト・オイラーによって予想され、カール・フリードリッヒ・ガウスによって証明された（ガウス日誌によれば、1796年4月8日。発表されたのは1801年の『整数論』において）。ガウスはこの法則に対して生涯で7つ（または8つ）の異なる証明を与えた。その一つの動機は、三次や四次の相互法則を証明することにあった。現在では240以上もの証明が知られている。 三次や四次の相互法則は、ヤコビ、アイゼンシュタインによって独立に証明された（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 に対して A2 + B2 = rp と表せたならば r より真に小さい r′ ≥ 1 を選んで A′2 + B′2 = r′p とできるアルゴリズムの存在を示すことで行うことができる。 4k + 1 型の素数は第1補充法則より、A2 + 12 = rp と表すことができるため、このアルゴリズムを適用すればいつかは r を 1 にすることができる。 25 以下の自然数 n, 50 以下の素数 p について、n2 (mod p) を計算してみると次の表になる。 ( 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 が x2 + 3 を割り切るような整数 x が存在することと、q が 6 を法として 1 に合同であることは同値である。 同様にして、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}}} と求められる。