📂整数論

平方剰余と非平方剰余

定義 ¹

素数$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}$個存在する。

■