■フェルマーの小定理とウィルソンの定理(その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)

===================================