数论与有限域

第三章 二次剩余

数论与有限域

第一节 二次剩余一、二次剩余的定义 二、二次剩余的性质

数论与有限域

一、二次剩余的定义定义3.1.1 设整数a与正整数m互素， 若同余式x2 a(modm)有解，则称a为模m的二次剩余； 若同余式x2 a(modm)无解，则称a为模m的非二次剩余。

例3.1.1 确定哪些整数是模10的二次剩余。 解：首先由于对任意的整数n,由带余数除法，存在唯一 的整数k与n1,使得 n=10k+n1,其中0≤n1<10,则 n2=100k2+20k·1+n12,于是 n n2≡n12(mod10),0≤n1<10, 因而为了确定哪些整数是模10的二次剩余，只需要关注整 数1,2,3,…,9的平方。

数论与有限域

一、二次剩余的定义例3.1.1 确定哪些整数是模10的二次剩余。 解：首先为了确定哪些整数是模10的二次剩余，只需要关 注整数1,2,3,…,9的平方。而 12≡92≡1 (mod 10), 22≡82≡4 (mod 10), 32≡72≡9 (mod 10), 42≡62≡6 (mod 10), 52≡5 (mod 10), 同时，由于在整数1,4,5,6,9中与10互素的整数只有1 和9,因而 只有1和9是模10的二次剩余， 而整数2,3,7,8中与10互素的整数只有3和7,因而 只有3和7是模10的二次非剩余。

数论与有限域

一、二次剩余的定义例3.1.2确定哪些整数是模11的二次剩余。 解：只需要关注整数1,2,3,…,10的平方。而 12≡102≡1 (mod 11), 22≡92≡4 (mod 11), 32≡82≡9 (mod 11), 42≡72≡5 (mod 11), 52≡62≡3 (mod 11), 同时由于整数1,2,3,…,10均与11互素，因而 整数1,3,4,5,9是模11的二次剩余， 而整数2,6,7,8,10是模11的二次非剩余。

数论与有限域

一、二次剩余的定义

例3.1.3确定哪些整数是模13的二次剩余。

解：类似于例3.1.1的讨论，这里我们只需要关注整数1,2, 3,…,12的平方。而 12≡122≡1 (mod 13), 22≡112≡4 (mod 13), 32≡102≡9 (mod 13), 42≡92≡3 (mod 13), 52≡82≡12 (mod 13), 62≡72≡10 (mod 13), 同时由于整数1,2,3,…,12均与13互素，因而 整数1,3,4,9,10,12是模13的二次剩余， 而整数2,5,6,7,8,11是模13的二次非剩余。

数论与有限域

二、二次剩余的性质引理3.1.1 设p是奇素数，a是整数，且p a,则同余式x2≡a (mod p)或者没有解或者恰有两个模p不同余的解。

证明：若同余式x2≡a(mod p)有一个解x=x0,则由于 (-x0)2=x02≡a(mod p), 因而可以同时找到同余式的另一个解 x=-x0。 用反证法来证明解x=-x0与x=x0不同余，假设 x0≡-x0 (mod p),即2x0≡0 (mod p)。 此时由x02≡a(modp),得到 p|(x02-a), 又p a,因而p x0;又p是奇数，进而 p 2x0,这与2x0≡0 (mod p)矛盾，

数论与有限域

二、二次剩余的性质引理3.1.1 设p是奇素数，a是整数，且p a,则同余式x2≡a (mod p) 或者没有解或者恰有两个模p不同余的解。 证明：接下来证明同余式x2≡a(mod p)的解不多于两个。假设 x=x0与x=x1都是同余式x2≡a (

mod p)的解，则 x02≡x12≡a (mod p),即 x02-x12=(x0+x1)(x0-x1)≡0 (mod p)。 因而 p|(x0+x1)或者p|(x0-x1),即 x0≡x1 (mod p)或x0≡-x1 (mod p)。 综上，若同余式x2≡a (mod p)有解，则恰有两个模p不同余的解。

数论与有限域

二、二次剩余的性质

定理3.1.1 若p是奇素数，则在整数1,2,…,p-1中恰有 (p-1)/2个模p的二次剩余，(p-1)/2个模p的二次非剩余。 证明：p-1个同余式 x2≡a (mod p),x=1, 2, …, p-1, 或者没有解 或者恰有两个模p不同余的解xi与p-xi,0≤xi≤p-1。 即1,2,…,p-1能且仅能为(p-1)/2个同余式提供解； 即1与p-1,2与p-2,3与p-3,…,(p-1)/2与(p+1)/2分别为 (p-1)/2个同余式的解， 因而整数1,2,…,p-1中恰有(p-1)/2个模p的二次剩 余，剩余的p-1-(p-1)/2=(p-1)/2个小于p-1的整数是模p 的二次非剩余。

数论与有限域

第二节 勒让德符号一、勒让德符号的定义

二、欧拉判别法三、高斯引理

数论与有限域

一、勒让德符号的定义定义3.2.1 设p是奇素数，a是整数，且p a,则 a 勒让德(Legendre)符号 定义为 p

若a是模p的二次剩余; a 1 p , 1 若a是模p的二次非剩余 . a 例3.2.1 由例3.1.3知道，勒让德符号 , a 1,2, ,12 13

的值如下 1 3 4 9 10 12 1 13 13 13 13 13 13

2 5 6 7 8 11 1 13 13 13 13 13 13

数论与有限域

二、欧拉判别法定理3.2.1(欧拉判别法)设p是奇素数，a是整数，且 a a ( p 1) / 2 (mod p ) p a,则 p a 证明：由于勒让德符号 的取值只有±1,因而 p

下面我们可以分两种情形来讨论. a 首先，若 =1,则a是模p的二次剩余，即 p

同余式x2≡a (mod p)有解，设其解为x=x0,即 x02≡a (mod p)。

数论与有限域

二、欧拉判别法证明： 由费马小定理，有 x02≡a (mod p)。

2 a ( p 1) / 2 ( x0 )( p 1) / 2 x0p 1 1(mod p).

a a 因而若 =1,则 a ( p 1) / 2 (mod p ) p p a 其次，若 =-1,则a是模p的二次非剩余，即 p 同余式x2≡a (mod p)无解。

数论与有限域

二、欧拉判别法又对每一个与p互素的整数i,线性同余式ix≡a (mod p) 都存在一个整数解j,即 ij≡a (mod p)。而 同余式x2≡a (mod p)无解，则 线性同余式ij≡a (mod p)中 i≠j,进而 可以将1,2,…,p-1中的整数划分成(p-1)/2对， 使得每对的乘积为a,将所有这些整数对乘在一起， 得到 (p-1)!≡a(p-1)/2(mod p)。 由Wil

son定理，有 -1≡a(p-1)/2(mod p)。

数论与有限域

二、欧拉判别法

例3.2.2 设p=13,a=132,由于 1326 (mod 13) ≡26 ≡-1 (mod 13), 132 由欧拉判别法有 13 =-1,因而132是模13的二次非剩余。

定理3.2.2 设p是奇素数，a,b是整数，p a且p b,则 (i) 若a≡b(mod p),则 a b ; p p a b ab (ii) ; p p p a2 (iii) =1。 p

数论与有限域

二、欧拉判别法 证明： 若a≡b(mod p),则同余式x2≡a (mod p)有解 同余式x2≡b

a b (mod p)有解，因而 。 p p b (p-1)/2 ≡b (mod p), p ab (mod p). p

(ii) 由欧拉判别法， a ≡a(p-1)/2(mod p), p

且

a b (p-1)/2 (p-1)/2 ≡a b =(ab) (p-1)/2≡ p p

ab p

≡(ab)(p-1)/2(mod p),因而

由于勒让德符号的值只有±1,因而结论成立。

数论与有限域

a (iii) 由于 =±1,由(ii)的结果得到 p

二、欧拉判别法 a 2 a a 1 p p p

由定理3.2.2的(ii)知： 一个素数的两个二次剩余或两个二次非剩余的乘 积是一个二次剩余，而一个素数的一个二次剩余 与一个二次非剩余的乘积是一个二次非剩余。 a a a n p1 1 p2 2 ps s 同时，任意给定正整数n的素分解式 由定理3.2.2可知要确定勒让德符号 n 的值， p

1 2 q 只需确定勒让德符号 , 以及 (其中q p p p 是一奇素数)的值。

数论与有限域

二、欧拉判别法若p 1(mod 4); 1 1 定理3.2.3 设p是奇素数，则 p 1 若p 1(mod 4). p 1 1 ( 1) 2 (mod p ) 证明：由欧拉判别法， p

由于p是奇素数，故p只能取 p=4k+1与p=4k+3,其中k为整数。 若p=4k+1,即p≡1(mod 4),则 1 (p-1)/2=(-1)2k=1,因而此时 p 1 (-1) 若p=4k+3,即p≡3(mod 4),则 1 (p-1)/2=(-1)2k+1=-1,因而此时 (-1) p 1

数论与有限域

三、高斯引理定理3.2.4(高斯引理)令奇素数p不整除整数n,同时设 在(p-1)/2个数n, 2n,…, (p-1)n/2对p取模得到的最小正 剩余中有m个大于p/2,则 n 1 m p

例3.2.3 p=13,n=63,则63,126,189,252,315,378 对13取模的最小剩余11,9,4,5,3,1中有两个大 63 于13/2,即m=2,进而由高斯引理有 1

13

例3.2.4 p=17,n=10,则10,20,30,40,50,60,70, 80对17取模的最小剩余10,3,13,6,16,9,2, 12中有5个大于17/2,即m=5,进而由高斯引理有 10 5 1 1 17

数论与有限域

三、高斯引理 2 ( p 2 1 ) / 8 定理3.2.5 若p是奇素数，则 1 p p 1(mod 8,则2为模p的二次剩余； ) 因而若 p 3(mod 8),则2为模p的二次非剩余。 若

证明：由于p是奇素数，可令 p=8a+r,r=1,3,5,7。 接下来计数(p-1)/2个整数2, 2×2,…, (p-1)×2/2对p取模 得到的最小正剩余中大于p/2的个数， 由于这(p-1)/2个整数已经在0和p之间，因而m的值是 满足不等式p/2<2k<p的k的个数，

数论与有限域

三、高斯引理 2 ( p 2 1 ) / 8 定理3.2.5 若p是奇素数，则 1 p

) 因而若 p 1(mod 8,则2为模p的二次剩余； 若 p 3(mod 8),则2为模p的二次非剩余。 证明：m的值是满足不等式p/2<2k<p的k的个数，即 m=[p/2]-[p/4]=[(8a+r)/2]-[(8a+r)]/4]=2a+[r/2]-[r/4] 当r分别取1,3,5,7时，m≡0, 1, 1, 0 (mod2)。 2 1 0 1 时， 故当p=8a+1或p=8a+7,即 p

2为模p的二次剩余； 2 1 1 1时， 而当p=8a+3或p=8a+5,即 p 2为模p的二次非剩余。