二次剰余と非二次剰余
📂整数論二次剰余と非二次剰余
定義
素数p=2 および a<p に関して、合同方程式 x2≡a(modp) の解が存在すれば、a を p の二次剰余 QRと呼ぶ。a が二次剰余でない場合は、非二次剰余 NRと呼ばれる。
説明
簡単に言えば、二次剰余とは (modp)で平方根が存在する数を意味する。
例えば、素数 7 を考えると
12≡1(mod7)22≡4(mod7)32≡2(mod7)42≡2(mod7)52≡4(mod7)62≡1(mod7)
1,2,4 はQRであり、3,5,6 はNRである。素数11 を考えると
12≡1(mod11)22≡4(mod11)32≡9(mod11)42≡5(mod11)52≡3(mod11)62≡3(mod11)72≡5(mod11)82≡9(mod11)92≡4(mod11)102≡1(mod11)
1,3,4,5,9 がQRであり、残りの2,6,7,8,10 はNRである。面白いことに、QRは対象的に現れるが、事実
(p−q)2≡p2−2pq+q2≡q2(modp)
であるため当然である。また、常にQRとNRは正確に同じ数だけ現れる。
定理
2 より大きな素数p に対して、QRとNRは正確に2(p−1) 個存在する。
証明
1 からp−1 までの全ての数を平方したリストは次のようになる。
12,22,⋯,(p−1)2
しかし、先に見たように
(p−q)2≡p2−2pq+q2≡q2(modp)
であるため、1 を見てもp−1 を見ても同じであり、2 を見てもp−2 を見ても同じである。従って、元の数の半分だけを見れば十分である。
12,22,⋯,(2p−1)2
これらの数は全てQRの定義によりQRであるため、これらの数が全て異なることを示せば、QRが正確に2(p−1) 個存在すると言えるだろう。同様に、(modp) でp より小さい自然数はQRでなければNRであるため、QRが正確に2(p−1) 個存在するならば、NRも正確に2(p−1) 個存在するだろう。本格的な証明は背理法を用いる。b1 とb2 を2(p−1) より小さい異なる二つの自然数とする。
b12≡b22(modp) が成り立つと仮定すると
b12−b22≡0(modp)
したがって、ある整数k に対してb12−b22=pk であり、素数p は(b1+b2)(b1−b2) の約数である。しかし、b1 とb2 が2(p−1) より小さいとしたので、(b1+b2) は(p−1) より小さい。従って、p が(b1+b2) の約数になることはできず、必然的に(b1−b2) の約数でなければならない。しかし、同じ理由で∣b1−b2∣ は(p−1) より小さいため、0 になって初めてp で割り切れる。つまり、b1=b2 なのだが、b1 とb2 を2(p−1) より小さい異なる二つの自然数と仮定したので、これは矛盾である。従って、b12=b22(modp) であり、QRは正確に2(p−1) 個存在する。
■