第五講-二次剩余

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

定義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求滿(mǎn)足同余式的所有的點(diǎn)。解：模7的二次剩余是：1，2，4；二次非剩余是：3，5，6。對(duì)，分別求出對(duì)應(yīng)的的值為無(wú)解無(wú)解二、模為奇素?cái)?shù)的平方剩余與平方非剩余

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

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

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

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

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

(2)

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

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

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

定義設(shè)是奇素?cái)?shù)的乘積。對(duì)任意整數(shù)，定義雅可比(Jacobi)符號(hào)為

因?yàn)?，而同余式組的每個(gè)同余式都無(wú)解，所以3是模119的平方非剩余。當(dāng)m為奇素?cái)?shù)時(shí)，則上式為勒讓德符號(hào)。

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

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