数论与有限域-第三章.pptVIP

第三章 二次剩余 第一节 二次剩余 定义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≤n110，则 n2=100k2+20k·n1+n12，于是 n2≡n12(mod10)，0≤n110， 因而为了确定哪些整数是模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，则 勒让德（Legendre）符号 定义为 又对每一个与p互素的整数i，线性同余式ix≡a (mod p)都存在一个整数解j，即 ij≡a (mod p)。而