数论

定义：∀ n,m ,(n,m)=1,m≥2，若n是模m的二次剩余《==》x**2 ≡ n (mod m)有解

例：

若n=2,m=3，x**2 ≡ 2 (mod 3)无解，则2是模3的二次非剩余

若n=2,m=7，x**2 ≡ 2 (mod 7)在x=3时成立，有解，故2是模7的二次剩余

Th1:在模p(奇素数)的缩系{1,2,3,...,p-1}中，有(p-1)/2个二次剩余和(p-1)/2个二次非剩余，且其中二次剩余为A:{,,...,}

证明：

（A中元素两两不同）

假设 ∃i,j i≠j ,1≤i≤(p-1)/2有

 ≡

故 ≡ i**2 (mod p)

 ≡ j**2 (mod p)

∴i**2 ≡ j**2 (mod p)

∴p|(i**2-j**2)即p | (i+j)*(i-j)

∵2 （n/p）=1）

∵n**((p-1)/2) ≡ 1 (mod p)，且1 ≠ 0 (mod p)

根据拉格朗日定理，可知对于同余式，解数≤(p-1)/2

又∵对于集合A={,,...,}

取i∈A,则有()**(p-1)/2 ≡ (i**2)**(p-1)/2 ≡ i**(p-1)  ≡ 1 (mod p)

∴A中元素为同余式n**((p-1)/2) ≡ 1 (mod p)的解

又∵A中元素恰为(p-1)/2个∴A中元素就是同余式n**((p-1)/2) ≡ 1 (mod p)的解，也就是说n的取值在集合A中

∴(n/p)=1

若(n/p)=-1，则(n/p)≠1

∴n**(p-1)/2 ≠ 1 (mod p)

∵(n,p)=1 ∴n**(p-1)  ≡ 1 (mod p)

∴(n**(p-1)/2)**2  ≡ 1(mod p)

∴((n**(p-1)/2)**2)-1 ≡ 0 (mod p)

∴p | (n**(p-1)/2)**2-1 即p | ((n**(p-1)/2)+1)*((n**(p-1)/2)-1)

∵n**(p-1)/2 ≠ 1 (mod p) ∴ p | (n**(p-1)/2)+1 即 (n**(p-1)/2) ≡ -1 (mod p)

得证，综上所述，n**(p-1)/2  ≡ (n/p) (mod p)

推论：若p 不整除于 m*n,则((m*n)/p)=(m/p)*(n/p)

证明：

(m/p)=m**(p-1)/2 (mod p)

(n/p)=n**(p-1)/2 (mod p)

故(m/p)*(n/p)=m**(p-1)/2 * n**(p-1)/2  (mod p)

                     = (m*n)**((p-1)/2) (mod p)=((m*n)/p) (mod p),得证

高斯引理：

若(p,n)=1,,...,中有m个数>p/2,则(n/p)=(-1)**m

证明：设集合A={,,...,}={a1,a2,...,al,b1,b2,...,bm}，其中1≤aip/2,l+m=p-1,A∈{1,2,...,p-1}

则p-bj≠ ai (mod p)

(

证明p-bj≠ ai (mod p):

p/2