logo

二次剰余と非二次剰余 📂整数論

二次剰余と非二次剰余

定義 1

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

説明

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

例えば、素数 77 を考えると 121(mod7)224(mod7)322(mod7)422(mod7)524(mod7)621(mod7) 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,41,2,4 はQRであり、3,5,63,5,6 はNRである。素数1111 を考えると 121(mod11)224(mod11)329(mod11)425(mod11)523(mod11)623(mod11)725(mod11)829(mod11)924(mod11)1021(mod11) 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,91,3,4,5,9 がQRであり、残りの2,6,7,8,102,6,7,8,10 はNRである。面白いことに、QRは対象的に現れるが、事実 (pq)2p22pq+q2q2(modp) (p-q)^2 \equiv p^2-2pq+q^2 \equiv q^2 \pmod{p} であるため当然である。また、常にQRとNRは正確に同じ数だけ現れる。

定理

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

証明

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

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


  1. Silverman. (2012). 『Number Theoryへのやさしい導入 (第4版)』: p143. ↩︎