第5講二次剩余教師：李艷俊本講內(nèi)容一、二次剩余的概念二、模為奇素數(shù)的平方剩余與平方非剩余三、勒讓德符號四、雅可比符號五、小結(jié)一、二次剩余的概念二次同余式的一般形式是其中m是正整數(shù)，。上式等價于同余式

定義1設(shè)m是正整數(shù)，若同余式有解，則a叫做模m的平方剩余(或二次剩余)；否則a叫做模m的平方非剩余(或二次非剩余)。例1分別求出模11，12的二次剩余和二次非剩余。解：模11的二次剩余是：1，3，4，5，9；二次非剩余是：2，6，7，8，10。模12的二次剩余是：1；二次非剩余是：5，7，11。例2求滿足同余式的所有的點。解：模7的二次剩余是：1，2，4；二次非剩余是：3，5，6。對，分別求出對應(yīng)的的值為無解無解二、模為奇素數(shù)的平方剩余與平方非剩余

定理1(歐拉判別條件)設(shè)p是奇素數(shù)，，則

(1)a是模p的平方剩余的充分必要條件是

(2)a是模p的平方非剩余的充分必要條件是當(dāng)a是模p的平方剩余時，同余式恰有兩解。解:例判斷137是否為模227平方剩余。

定理2設(shè)p是奇素數(shù)，則模p的簡化剩余系中平方剩余與平方非剩余的個數(shù)各為，且個平方剩余與序列中的一個數(shù)同余，且僅與一個數(shù)同余。所以137是模227平方非剩余。三、勒讓德符號由此定義，歐拉判別法則可以表示成如下形式：

定義設(shè)p是素數(shù)，定義勒讓德符號如下：定理設(shè)p是奇素數(shù)，則對任意整數(shù)a，有設(shè)p是奇素數(shù)，則勒讓德符號有如下性質(zhì)：(2)，進(jìn)一步，若，則；(3)，進(jìn)一步，若，則，若，則；(1)，；(5)若是互素的奇素數(shù)，則。(4)；例1計算如下勒讓德符號的值。(1)

(2)

(3)m是否為素數(shù)q=0q=1q=-1q=2out:01停止否是，計算nmodm=q返回為奇數(shù)；為偶數(shù)。例2

判斷同余式是否有解？有解時，求出其解數(shù)。例3判斷同余式是否有解？有解時，求出其解數(shù)。

注意：雅可比符號為1時，不能判斷a是否為模m的平方剩余。例如四、雅可比符號

定義設(shè)是奇素數(shù)的乘積。對任意整數(shù)，定義雅可比(Jacobi)符號為

因為，而同余式組的每個同余式都無解，所以3是模119的平方非剩余。當(dāng)m為奇素數(shù)時，則上式為勒讓德符號。

如果，則；設(shè)m是奇數(shù)，則雅可比符號有以下性質(zhì)：

，如果，則；(3)(2)；(1)，(4)(5)設(shè)m,n都是奇數(shù)，則。例判斷同余式是否有解？解：不用考慮563是否為素數(shù)，直接計算雅可比符號:所以同余式無解。當(dāng)n是合數(shù)的時候，若（a/n）=1，則a不一定是模n的二次剩余。定義則有。集合中的數(shù)稱為模n的偽二次剩余。124581011131617192014164116161416411-11-1-11-111-11-1111-11-11-11-1-1-11-111-1-1-1-111-11例：a結(jié)論：猜想二次剩余問題的難度與因子分解難度相當(dāng)。定理3.12若n=pq，且n的素因子p和q已知，則整數(shù)a為模n的二次剩余，當(dāng)且僅當(dāng)五、小結(jié)1、m是正整數(shù)a是m的二次剩余。2、歐拉判別條件p是奇素