平方剰余の相互法則
平方剰余の相互法則は整数 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 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}}}
となり、
同様にして、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}}}
と求められる。
4k + 1 型の素数は二個の平方数の和で表すことができる。また逆にある奇素数が二つの平方数の和で表すことができるならば、4k + 1 型の素数である。そして、二つの平方数の順序を別にすればこの分解は一意的である。