📂整数論

二次剰余と非二次剰余

定義 ¹

素数$p \ne 2$ および $a < p$ に関して、合同方程式 $x^{2} \equiv a \pmod{p}$ の解が存在すれば、$a$ を $p$ の二次剰余 QRと呼ぶ。$a$ が二次剰余でない場合は、非二次剰余 NRと呼ばれる。

説明

簡単に言えば、二次剰余とは $\pmod{p}$で平方根が存在する数を意味する。

例えば、素数 $7$ を考えると $$ 1^2 \equiv 1 \pmod{7} \\ 2^2 \equiv 4 \pmod{7} \\ 3^2 \equiv 2 \pmod{7} \\ 4^2 \equiv 2 \pmod{7} \\ 5^2 \equiv 4 \pmod{7} \\ 6^2 \equiv 1 \pmod{7} $$ $1,2,4$ はQRであり、$3,5,6$ はNRである。素数$11$ を考えると $$ 1^2 \equiv 1 \pmod{11} \\ 2^2 \equiv 4 \pmod{11} \\ 3^2 \equiv 9 \pmod{11} \\ 4^2 \equiv 5 \pmod{11} \\ 5^2 \equiv 3 \pmod{11} \\ 6^2 \equiv 3 \pmod{11} \\ 7^2 \equiv 5 \pmod{11} \\ 8^2 \equiv 9 \pmod{11} \\ 9^2 \equiv 4 \pmod{11} \\ 10^2 \equiv 1 \pmod{11} $$ $1,3,4,5,9$ がQRであり、残りの$2,6,7,8,10$ はNRである。面白いことに、QRは対象的に現れるが、事実 $$ (p-q)^2 \equiv p^2-2pq+q^2 \equiv q^2 \pmod{p} $$ であるため当然である。また、常にQRとNRは正確に同じ数だけ現れる。

定理

$2$ より大きな素数$p$ に対して、QRとNRは正確に$\displaystyle {(p-1) \over 2}$ 個存在する。

証明

$1$ から$p-1$ までの全ての数を平方したリストは次のようになる。 $$ 1^2, 2^2, \cdots , (p-1)^2 $$ しかし、先に見たように $$ (p-q)^2 \equiv p^2-2pq+q^2 \equiv q^2 \pmod{p} $$ であるため、$1$ を見ても$p-1$ を見ても同じであり、$2$ を見ても$p-2$ を見ても同じである。従って、元の数の半分だけを見れば十分である。 $$ 1^2, 2^2, \cdots , \left( {{ p-1 } \over { 2 }} \right)^2 $$ これらの数は全てQRの定義によりQRであるため、これらの数が全て異なることを示せば、QRが正確に$\displaystyle {(p-1) \over 2}$ 個存在すると言えるだろう。同様に、$\pmod{p}$ で$p$ より小さい自然数はQRでなければNRであるため、QRが正確に$\displaystyle {(p-1) \over 2}$ 個存在するならば、NRも正確に$\displaystyle {(p-1) \over 2}$ 個存在するだろう。本格的な証明は背理法を用いる。$b_1$ と$b_2$ を$\displaystyle {{(p-1)} \over {2}}$ より小さい異なる二つの自然数とする。

${b_1}^2 \equiv {b_2}^2 \pmod{p}$ が成り立つと仮定すると $$ {b_1}^2 - {b_2}^2 \equiv 0 \pmod{p} $$ したがって、ある整数$k$ に対して${b_1}^2 - {b_2}^2 = pk$ であり、素数$p$ は$({b_1} + {b_2})({b_1} - {b_2})$ の約数である。しかし、$b_1$ と$b_2$ が$\displaystyle {{(p-1)} \over {2}}$ より小さいとしたので、$({b_1} + {b_2})$ は$(p-1)$ より小さい。従って、$p$ が$({b_1} + {b_2})$ の約数になることはできず、必然的に$({b_1} - {b_2})$ の約数でなければならない。しかし、同じ理由で$|{b_1} - {b_2}|$ は$(p-1)$ より小さいため、$0$ になって初めて$p$ で割り切れる。つまり、${b_1} = {b_2}$ なのだが、$b_1$ と$b_2$ を$\displaystyle {{(p-1)} \over {2}}$ より小さい異なる二つの自然数と仮定したので、これは矛盾である。従って、${b_1}^2 \neq {b_2}^2 \pmod{p}$ であり、QRは正確に$\displaystyle {(p-1) \over 2}$ 個存在する。

■