初等數(shù)論-第5章-二次同余式與平方剩余

2024/11/291第五章二次同余式與平方剩余§5.1一般二次同余式2024/11/292一、一般二次同余式的轉(zhuǎn)化二次同余式的一般形式為ax2

bx

c

0(modm)。(1)對(1)的討論可以轉(zhuǎn)化為對素數(shù)冪為模的同余式的討論。2024/11/293二、同余式(2)解的討論由§4.3－TH2〔P82〕知

(2)有解

ax2

bx

c

0(modp)有解

bx

c

0(modp)有解

2024/11/294代換即得2024/11/295(2)有解由§4.3－TH2〔P82〕知(2)有解2024/11/296三、同余式

解的討論一般地，對同余式(2)的求解，最終可以轉(zhuǎn)化為同余式

2024/11/2972024/11/2982024/11/299四、平方剩余和平方非剩余若

有解，則a稱為模m的平方剩余；否則，稱a為模m的平方非剩余?！嗄?的平方剩余為1；平方非剩余為2(或-1).2024/11/2910∴模5的平方剩余為±1；平方非剩余為±2.2024/11/2911∴模7的平方剩余為1，2，-3；平方非剩余為-1，-2，3.∴模11的平方剩余為1，-2，3，4，5；平方非剩余為-1，2，-3，-4，-5.2024/11/2912§5.2單質(zhì)數(shù)的平方剩余與平方非剩余本節(jié)討論形如的同余式的解。2024/11/2913定理１〔歐拉判別條件〕若(a,p)=1，則（1）a是模p的二次剩余的充要條件是（2）若a是模p的二次剩余，則方程(1)有兩個解；（3）a是模p的二次非剩余的充要條件是2024/11/2914可以驗證：∴模11的平方剩余為1，-2，3，4，5；平方非剩余為-1，2，-3，-4，-5.2024/11/2915模11的平方剩余為1，-2，3，4，5.2024/11/2916

a是模p的二次剩余的充要條件是若a是模p的二次剩余，

2024/11/2917若a是模p的二次剩余，則方程(1)有兩個解；根據(jù)§4.4-TH5[P86]知，

方程(1)有兩個解。定理5設(shè)n

p，則同余方程f(x)=xn

an

1xn

1

a1x

a0

0(modp)有n個解的充要條件是

存在整數(shù)多項式q(x)和r(x)，r(x)的次數(shù)<n，使得

x

p

x=f(x)q(x)

p

r(x)。

2024/11/2918a是模p的二次非剩余的充要條件是證明：由(a,p)=1

由（1）a是模p的二次剩余的充要條件是2024/11/2919定理2

模p的簡化系中，二次剩余與二次非剩余的個數(shù)都是且模p的每個二次剩余與且僅與數(shù)列中的一個數(shù)同余。模7的平方剩余為1，2，-3；平方非剩余為-1，-2，3.2024/11/2920定理2的證明：由定理1知，平方剩余的個數(shù)等于同余式的解數(shù)，所以據(jù)§4.4-TH5[P86]知，平方剩余的個數(shù)等于

又模p的簡化系中含有p-1個元素，從而平方非剩余的個數(shù)等于易證其兩兩對p不同余.得證.2024/11/2921§5.3勒讓德符號利用歐拉判別條件雖然可以判定x2

a(modp)

的解的存在性，但對較大的質(zhì)數(shù)模，實際運用很困難。通過引入勒讓德符號，本節(jié)給出了較方便的判別方法。2024/11/2922一、Legendre符號定義給定奇素數(shù)p，對于整數(shù)n，定義Legendre符號為如,1與4是模5的平方剩余，2與3是模5的平方非剩余，2024/11/2923二、基本性質(zhì)2024/11/2924(1)的特例.2024/11/29252024/11/2926的取值只有0，±1，

且p>2，故得證。2024/11/29272024/11/2928引理設(shè)(n,p)=1，對于整數(shù)k

以rk表示nk對模p的最小非負剩余,

a是模p的二次剩余的充要條件是2024/11/29292024/11/2930引理的證明：且對任意的i，j，1

i

m，1

j

t，

否則，將有整數(shù)k1與k2，

使得

nk1

nk2

0(modp)，即p

n(k1+k2)，由于(n,p)=1，于是p

k1

k2，這是不可能的。

由式(*)推出下略2024/11/2931定理1

下面的結(jié)論成立：注：定理1給出了判斷平方剩余的另一方法。2024/11/29322024/11/2933證明：使用引理中的符號rk，ai，bi，m與t，

2024/11/2934若n=2，

2024/11/2935定理2(二次互反律)設(shè)p與q是不同的兩個奇素數(shù)，則2024/11/2936由定理1，有考察有序數(shù)對(u,v)所成的集合S={(u,v)；u=py，v=qx，1

x

p1，1

y

q1}顯然S中有p1q1

個元素。

由于(p,q)=1，

所以，對于任何(u,v)

S，u

v

記S1={(u,v)；(u,v)

S，u>v}，S2={(u,v)；(u,v)S，v>u}有

S1

S2

=，S1

S2=S。

2024/11/2937記S1={(u,v)；(u,v)

S，u>v}，S2={(u,v)；(u,v)S，v>u}有

S1

S2

=，S1

S2=S.

對于(u,v)

S1，有u>v，

即py>xq，

1

y

q1，

S={(u,v)；u=py，v=qx，1

x

p1，1

y

q1}S中有p1q1

個元素。由定理1得證.2024/11/2938注意：利用第二節(jié)和本節(jié)中的定理，可以判定素數(shù)模的二次同余方程的可解性。例1

已知563是素數(shù)，方程x2

429(mod563)是否有解。方程有解。2024/11/2939一般地，若p是素數(shù)，計算可按以下步驟進行：

(1)求出n0

n(modp)，1

n0

p；(2)將n0寫成n0=Q2q1q2

qk的形式，其中Q

Z，q1,q2,

,qk是互不相同的素數(shù)；(3)若有某個qi=2，用定理1推論判定之值；

(4)若qi

2，利用定理2將的計算轉(zhuǎn)化為計算

(5)重復(fù)以上步驟，直至求出每個

2024/11/2940例2

判斷方程x2

137(mod227)是否有解。2024/11/2941例3證明：形如8k

7（k

Z）的素數(shù)有無窮多個。解用反證法，假設(shè)只有有限個素數(shù)p1,p2,

,pt.記N=(p1p2

pt)2

2，設(shè)q是N的一個奇素因數(shù)，

則(p1p2

pt)2

2(modq)，因此，由定理1有q

1或7(mod8)。若N的所有奇素因數(shù)都具有8k

1的形式，

則N也是8k

1的形式，

但是，由于任何奇數(shù)的平方對模8與1同余，

所以應(yīng)有N

1

2

1(mod8)。這個矛盾說明，N至少有一個形如8k

7的奇素因數(shù)q。

2024/11/2942例4求以11為其二次剩余的所有奇素數(shù)p.2024/11/2943§5.4雅可比符號對于奇素數(shù)p，利用計算Legendre符號可以判定方程x2

a(modp)(1)是否有解。對于一般的正整數(shù)m，

如何判定方程是否有解呢？x2

a(modm)(2)

2024/11/2944對于一般的正整數(shù)m，如果它的標準分解式是那么判定方程x2

a(modm)(2)是否有解，可歸結(jié)為對形如方程x2

a(modp)(1)的可解性判定。

因此，在理論上，利用Legendre符號可以判定方程(2)是否有解。

但是，寫出正整數(shù)的標準分解式常會遇到實際困難，所以利用Legendre符號判定方程(2)的可解性并不容易實現(xiàn)。2024/11/2945定義1

給定正奇數(shù)m>1，m=p1p2

pk，其中pi（1

i

k）是奇素數(shù)，對于任意的整數(shù)a，

（1

i

k）是Legendre符號，

稱是Jacobi符號。

例如，取m=45=3

3

5，則2024/11/2946（1）當m是奇素數(shù)時，Jacobi符號就是Legendre符號。前者是后者的推廣。（2）如果m是奇素數(shù)，當=1時，方程(2)有解。

當m不是奇素數(shù)時，這個結(jié)論不一定成立。

例如，方程x2

5(mod9)無解，顯然，若則方程(2)必無解。補充說明2024/11/2947定理1

使用定義1中的符號，下面的結(jié)論成立：(1)若a

a1(modm)，則(3)對于任意的整數(shù)a1,a2,

,at，有(4)對于任意的整數(shù)a，b，(a,m)=1，有

2024/11/29482024/11/2949定理2

設(shè)m=p1p2

pk是奇數(shù)，其中p1,p2,pk是素數(shù)，則下面的結(jié)論成立：2024/11/2950定理3

設(shè)m，n是大于1的奇整數(shù)，則利用以上定理，我們可以很容易地計算Jacobi符號，特別是Legendre符號的數(shù)值。但是，必須注意，如同在定義1的注2中指出的，在判斷方程(2)的可解性時，Legendre符號和Jacobi的作用是不一樣的。

方程(2)有解。對于一般的正奇數(shù)m來說，=1并不能保證2024/11/2951例1

已知3371是素數(shù)，判斷方程x2

12345(mod3371)是否有解。解:利用Jacobi符號的性質(zhì)，有因此，方程無解。2024/11/2952例2

設(shè)a與b是正奇數(shù)，求的關(guān)系。2024/11/2