■フェルマーの小定理とウィルソンの定理(その14)
aがpで割り切れないとする.ルジャンドル記号を用いて
aがpを法とする平方剰余であるとき,(a/p)=1
aがpを法とする平方非剰余であるとき,(a/p)=−1
===================================
【1】平方剰余と非剰余
素数pを法とする剰余表を作るとき,1からp−1までの数を平方する必要はない.k^2=(p−k)^2 (mod p)であるから,1から(p−1)/2までの数を平方すれば十分である.
たとえば,p=31を法とする剰余は1から15までの整数を平方して31で割った余りは
1,4,9,16,25,5,18,2,19,7,28,20,14,10,8
となる.p=31を法とする平方剰余は15個 → 一般に(p−1)/2個
非剰余
3,6,11,12,13,15,17,21,22,23,24,26,27,29,30
も15個ある. → 一般に(p−1)/2個
===================================
(ab/p)=(a/p)(b/p)
は
剰余×剰余=剰余
剰余×非剰余=非剰余
非剰余×剰余=非剰余
非剰余×非剰余=剰余
を意味する. →23・12=28 (mod 31)
===================================