p为奇素数,证明同余式x^2=3(mod p)充要条件p=±1(mod 12)

计算legendre符号(3/p)呀!
任意奇素数p,
必为如下形式之一：
p==±1 mod 12,p==±5 mod 12
计算知 当p==±1 mod 12,(3/p)=1,即xx==3 mod p有解.
否则,即p==±5 mod 12时,(3/p)=-1,即xx==3 mod p无解.
于是得证.
附录：
我的博文：二次剩余及其速算法
百度可搜到,或者在我空间很容易就找到了.
摘录：
定义 amr 表示绝对最小剩余,即abs min remainder.或在r后添加下标|min|来表示.
如 2 ==-1 mod 3,写成 2 amr 3=-1； 3 ==-1 mod 4,写成 3 amr 4=-1.
注：被除数dividend=除数divisor*商quotient+ 绝对最小剩余amr,其中 |amr|