数论与有限域 第三章

数论与有限域

第三章 二次剩余

数论与有限域

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

数论与有限域

一、二次剩余的定义定义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 …… 此处隐藏：2630字，全部文档内容请下载后查看。喜欢就下载吧 ……