オイラーの判定法

(a/p)=a^(p-1)/2 　(modp)

(-1/p)=(-1)^(p-1)/2 　(modp)・・・第1補充法則

pを奇素数とする

(-1/p)=1←→p=1 (mod4)

(-1/p)=-1←→p=3 (mod4)

p=A^2+B^2と表せる←→p=1 (mod4)またはp=2

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

(2/p)=(2)^(p-1)/2=(-1)^(p^2-1)/8 　(modp)・・・第2補充法則

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

(q/p)(p/q)=(-1)^(p-1)/2(q-1)/2・・・平方剰余の相互法則

ｐを3でない素数とする

(-3/p)=(-1/p)(3/p)==(-1)^(p-1)/2(-1)^(p-1)/2(p/3)=(p/3)

(-3/p)=1←→p=1 (mod3)

(-3/p)=-1←→p=2 (mod3)

p=A^2+3B^2と表せる←→p=1 (mod3)またはp=3

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

p=A^2+2B^2と表せる←→p=1、3 (mod8)またはp=2

p=A^2-2B^2と表せる←→p=1、7 (mod8)またはp=2

p=A^2+5B^2と表せる←→p=1、9 (mod20)またはp=5

2p=A^2+2B^2と表せる←→p=3，7 (mod20)またはp=5

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝