初等數(shù)論§3同余

第三章同余同余是數(shù)論中的重要概念，同余理論是研究整數(shù)問(wèn)題的重要工作之一.本章介紹同余的基本概念，剩余類和完全剩余系.生活中我會(huì)經(jīng)常遇到與余數(shù)有關(guān)的問(wèn)題，比如：某年級(jí)有將近400名學(xué)生。有一次演出節(jié)目排隊(duì)時(shí)出現(xiàn)：如果每8人站成一列則多余1人；如果改為每9人站成一列則仍多余1人；結(jié)果發(fā)現(xiàn)現(xiàn)成每10人結(jié)成一列，結(jié)果還是多余1人；聰名的你知道該年級(jí)共有學(xué)生多少名嗎？

2024/5/61阜陽(yáng)師范學(xué)院數(shù)科院§3.1同余的概念及其基本性質(zhì)一、問(wèn)題的提出1、今天是星期一，再過(guò)100天是星期幾？3、13511，13903，14589被自然數(shù)m除所得余數(shù)相同，問(wèn)m最大值是多少？

2、3145×92653=291093995的橫線處漏寫(xiě)了一個(gè)數(shù)字，你能以最快的辦法補(bǔ)出嗎？2024/5/62阜陽(yáng)師范學(xué)院數(shù)科院二、同余的定義注：下面的三個(gè)表示是等價(jià)的：2024/5/63阜陽(yáng)師范學(xué)院數(shù)科院三、同余的性質(zhì)TH2設(shè)a，b，c，d，k是整數(shù)，并且

a

b(modm)，

c

d(modm)，

則

①

a

c

b

d(modm)；

②

ac

bd

(modm);

③ak

bk

(modm).注：TH1、TH2是最簡(jiǎn)單、常用的性質(zhì)。2024/5/64阜陽(yáng)師范學(xué)院數(shù)科院2024/5/65阜陽(yáng)師范學(xué)院數(shù)科院TH4下面的結(jié)論成立：①

a

b(modm)，d

m，d>0

a

b(modd)；②

a

b(modm)，k>0，k

N

ak

bk(modmk)；③

a

b(modmi

)，1

i

k

a

b(mod[m1,m2,

,mk])；④

a

b(modm)(a,m)=(b,m)；⑤

ac

bc(modm)，(c,m)=1

a

b(modm);⑥⑦2024/5/66阜陽(yáng)師范學(xué)院數(shù)科院①

a

b(modm)，d

m，d>0

a

b(modd)；②

a

b(modm)，k>0，k

N

ak

bk(modmk)；③

a

b(modmi

)，1

i

k

a

b(mod[m1,m2,

,mk])；④

a

b(modm)(a,m)=(b,m)；2024/5/67阜陽(yáng)師范學(xué)院數(shù)科院⑤

ac

bc(modm)，(c,m)=1

a

b(modm);注：若沒(méi)有條件(c,m)=1，即為T(mén)H2③的逆命題，

不能成立。反例：取m=6,c=2,a=20,b=23.2024/5/68阜陽(yáng)師范學(xué)院數(shù)科院⑥⑦2024/5/69阜陽(yáng)師范學(xué)院數(shù)科院四、一些整數(shù)的整除特征(1)

3、9的整除特征——各位上的數(shù)字之和能被3（9）整除例1檢查5874192、435693能否被3（9）整除。2024/5/610阜陽(yáng)師范學(xué)院數(shù)科院(2)7、11、13的整除特征注：一般地，求

被m除的余數(shù)時(shí)，

首先是求出正整數(shù)k，使得10k

1或1(modm)，

2024/5/611阜陽(yáng)師范學(xué)院數(shù)科院(2)7、11、13的整除特征特別地，由于，所以——奇偶位差法

例2檢查637693、75312289能否被7（11，13）整除。由693－637＝56，所以637693能被7整除，但不能被11，13整除，

當(dāng)然也可以由6+3-7+6-9+3=2知637693不能被11整除；

由75-312+289＝52，所以75312289能被13整除，但不能被7，11整除。

2024/5/612阜陽(yáng)師范學(xué)院數(shù)科院2024/5/613阜陽(yáng)師范學(xué)院數(shù)科院①求出整數(shù)k，使ak

1(modm)；②求出正整數(shù)r，r<k，使得bc

r(modk)；——減小冪指數(shù)2024/5/614阜陽(yáng)師范學(xué)院數(shù)科院例4證明：若n是正整數(shù)，則13

42n+1

3

n+2。解

：42n+1

3

n+2=4×42n

9×3

n

4×3n

9×3

n=13×3

n

0(mod13)=4×16n

9×3

n2024/5/615阜陽(yáng)師范學(xué)院數(shù)科院例5

設(shè)n的十進(jìn)制表示是

且792

n，

求x，y，z.

解

因?yàn)?92=8×9×11，故8

n，9

n及11

n。9

n

9

1

3

x

y

4

5

z=19

x

y

9

x

y

1，

(1)11

n

11

z

5

4

y

x

3

1=3

y

x

11

3

y

x。

(2)即有

x

y

1=9或18，3

y

x=0或11解方程組，得到x=8，y=0，z=6。2024/5/616阜陽(yáng)師范學(xué)院數(shù)科院五、棄九法〔驗(yàn)算計(jì)算結(jié)果〕應(yīng)用這種方法可以驗(yàn)算較大整數(shù)的乘法。例6.驗(yàn)算28997×39495＝1145236415是否正確。注：若結(jié)論成立，其結(jié)果不一定正確；所以結(jié)果不正確。也可以檢查和、差的運(yùn)算。2024/5/617阜陽(yáng)師范學(xué)院數(shù)科院例7.求方程2x

3y=1的正整數(shù)解。

解：顯然y=1，x=2，是原方程的解。若x

3，則

所以

3y

1(mod8)不能成立。故原方程的正整數(shù)解只有x=2,y=1.2024/5/618阜陽(yáng)師范學(xué)院數(shù)科院習(xí)題講解：3.找出整數(shù)能被37、101整除的判別條件。2024/5/619阜陽(yáng)師范學(xué)院數(shù)科院解：依次計(jì)算對(duì)模641的同余數(shù)22

4，24

16，28

256，2024/5/620阜陽(yáng)師范學(xué)院數(shù)科院解：設(shè)a=2m

1，當(dāng)n=1時(shí)，有a2=(2m

1)2=4m(m

1)

1

1(mod23)（*）成立。設(shè)式(*)對(duì)于n=k成立，則有這說(shuō)明式(*)當(dāng)n=k

1也成立。

由歸納法得證.2024/5/621阜陽(yáng)師范學(xué)院數(shù)科院2024/5/622阜陽(yáng)師范學(xué)院數(shù)科院§3.2剩余類與完全剩余系

一、剩余類——按余數(shù)的不同對(duì)整數(shù)分類是模m的一個(gè)剩余類，

即

余數(shù)相同的整數(shù)構(gòu)成m的一個(gè)剩余類。一個(gè)剩余類中任意一個(gè)數(shù)稱為它同類的數(shù)的剩余。一個(gè)整數(shù)被正整數(shù)n除后，余數(shù)有n種情形：0，1，2，3，…，n-1，它們彼此對(duì)模n不同余。這表明，每個(gè)整數(shù)恰與這n個(gè)整數(shù)中某一個(gè)對(duì)模n同余。這樣一來(lái)，按模n是否同余對(duì)整數(shù)集進(jìn)行分類，可以將整數(shù)集分成n個(gè)兩兩不相交的子集。2024/5/623阜陽(yáng)師范學(xué)院數(shù)科院定理1

2024/5/624阜陽(yáng)師范學(xué)院數(shù)科院二、完全剩余系1.定義2

注：①完全剩余系不唯一；②{0,1,2,

,m

1}是模m的最小非負(fù)完全剩余系；③若把剩余系作為一個(gè)集合，則可以把對(duì)模m的余數(shù)相同的整數(shù)——即同一剩余類里的整數(shù)，看作同一元素。2024/5/625阜陽(yáng)師范學(xué)院數(shù)科院完全剩余系舉例：集合{0,6,7,13,24}是模5的一個(gè)完全剩余系，集合{0,1,2,3,4}是模5的最小非負(fù)完全剩余系。都是模m的絕對(duì)最小完全剩余系。是模m的絕對(duì)最小完全剩余系。

2024/5/626阜陽(yáng)師范學(xué)院數(shù)科院2、完全剩余系的構(gòu)造定理2

整數(shù)集合A是模m的完全剩余系的充要條件是①A中含有m個(gè)整數(shù)；②A中任何兩個(gè)整數(shù)對(duì)模m不同余。注：由定理1及定義2易得證。思考：1、既然完全剩余系是不唯一的，不同的剩余系之間存在什么關(guān)系呢？2、一個(gè)完全剩余系的所有元素通過(guò)線性變化后，還是完全剩余系嗎？2024/5/627阜陽(yáng)師范學(xué)院數(shù)科院檢驗(yàn)：設(shè){x1,x2,

,xm}是模m的一個(gè)完全剩余系，那么，{b+x1,b+x2,,b+xm}和

{ax1,ax2,,a

xm}是模m的一個(gè)完全剩余系嗎？2024/5/628阜陽(yáng)師范學(xué)院數(shù)科院定理3

設(shè)m

1，a，b是整數(shù)，(a,m)=1，{x1,x2,

,xm}是模m的一個(gè)完全剩余系，則{ax1

b,ax2

b,

,axm

b}也是模m的完全剩余系。證明

由定理2，只需證明：若xi

xj，

則

axi

b

axj

b(modm)。

假設(shè)

axi

b

axj

b(modm)，則

axi

axj(modm)，

且(a,m)=1，xi

xj(modm)

由§3.1中的結(jié)論,P50第三行知：2024/5/629阜陽(yáng)師范學(xué)院數(shù)科院注意：(1)在定理3中，條件(a,m)=1不可缺少，否則不能成立；(2)定理3也可以敘述為：設(shè)m

1，a，b是整數(shù)，(a,m)=1，若x通過(guò)模m的一個(gè)完全剩余系，則ax+b也通過(guò)模m的一個(gè)完全剩余系；（3）特別地，若x通過(guò)模m的一個(gè)完全剩余系，(a,m)=1，，則ax和x+b也分別通過(guò)模m的一個(gè)完全剩余系。2024/5/630阜陽(yáng)師范學(xué)院數(shù)科院例1

設(shè)p

5是素?cái)?shù)，a

{2,3,

,p

1}，則在數(shù)列a，2a，3a，

，(p

1)a，pa中有且僅有一個(gè)數(shù)b，滿足

b

1(modp)；證

：

因?yàn)椋?，2，3，

，(p

1)，p｝是模p的一個(gè)完全剩余系，所以｛a，2a，3a，

，(p

1)a，pa｝構(gòu)成模p的一個(gè)完全剩余系。因此必有唯一的數(shù)b滿足式b

1(modp)。2024/5/631阜陽(yáng)師范學(xué)院數(shù)科院例2

設(shè)A={x1,x2,

,xm}是模m的一個(gè)完全剩余系，以{x}表示x的小數(shù)部分，證明：若(a,m)=1，則

證：

當(dāng)x通過(guò)模m的完全剩余系時(shí)，ax

b也通過(guò)模m的完全剩余系，

因此對(duì)于任意的i（1

i

m），axi

b一定且只與某個(gè)整數(shù)j（1

j

m）同余，

即存在整數(shù)k，使得

axi

b=km

j，（1

j

m）2024/5/632阜陽(yáng)師范學(xué)院數(shù)科院3、剩余系間的聯(lián)系定理4

設(shè)m1,m2

N，A

Z，(A,m1)=1，分別是模m1與模m2的完全剩余系，

則

R={Ax

m1y：x

X，y

Y

}是模m1m2的一個(gè)完全剩余系。證明

由定理3只需證明：若x

,x

X，y

,y

Y，且Ax

m1y

Ax

m1y

(modm1m2)，

2024/5/633阜陽(yáng)師范學(xué)院數(shù)科院定理4

設(shè)m1,m2

N，A

Z，(A,m1)=1，分別是模m1與模m2的完全剩余系，

則

R={Ax

m1y：x

X，y

Y

}是模m1m2的一個(gè)Ax

Ax

(modm1)

x

x

(modm1)

x

=x

，

m1y

m1y

(modm1m2)

y

y

(modm2)

y

=y

。

證：Ax

m1y

Ax

m1y

(modm1m2)，

Ax

m1y

Ax

m1y

(modm1)，

由x

=x

，

Ax

m1y

Ax

m1y

(modm1m2)，2024/5/634阜陽(yáng)師范學(xué)院數(shù)科院推論

若m1,m2

N，(m1,m2)=1，當(dāng)x1與x2分別通過(guò)

模m1與模m2的完全剩余系時(shí)，

則

m2x1

m1x2通過(guò)模m1m2的完全剩余系。

2024/5/635阜陽(yáng)師范學(xué)院數(shù)科院定理5

設(shè)mi

N，Ai

Z（1

i

n），并且滿足：①(mi,mj)=1，1

i,j

n，i

j；②(Ai,mi)=1，1

i

n；③mi

Aj

，1

i,j

n，i

j

。則當(dāng)xi（1

i

n）通過(guò)模mi的完全剩余系Xi時(shí)，y=A1x1

A2x2

Anxn

通過(guò)模m1m2

mn的完全剩余系。2024/5/636阜陽(yáng)師范學(xué)院數(shù)科院證：

由定理3只需證明，若xi

,xi

Xi，1

i

n，

A1x1

A2x2

Anxn

A1x1

A2x2

Anxn

(modm1

mn)

則可以得到xi

=xi

，1

i

n.事實(shí)上，由條件3假設(shè)易得，

對(duì)于任意的i，1

i

n，有Aixi

Aixi

(modmi)〔證明方法同定理4〕。再利用條件2推得

xi

xi

(modmi)，因此xi

=xi

.

2024/5/637阜陽(yáng)師范學(xué)院數(shù)科院例3

設(shè)m>0是偶數(shù)，{a1,a2,

,am}與{b1,b2,,bm}都是模m的完全剩余系，

則{a1

b1,a2

b2,

,am

bm}不是模m的完全剩余系。

證

由{1,2,

,m}與{a1,a2,,am}都是模m的完全剩余系，

如果{a1

b1,a2

b2,

,am

bm}是模m的完全剩余系，

不可能！2024/5/638阜陽(yáng)師范學(xué)院數(shù)科院例4

設(shè)mi

N（1

i

n），則當(dāng)xi通過(guò)模mi（1

i

n）

的完全剩余系時(shí)，x=x1

m1x2

m1m2x3

m1m2

mn

1xn通過(guò)模m1m2

mn的完全剩余系。證明

對(duì)n施行歸納法。當(dāng)n=2時(shí)，由定理4知定理結(jié)論成立。假設(shè)定理結(jié)論當(dāng)n=k時(shí)成立，

即當(dāng)xi（2

i

k

1）分別通過(guò)模mi的完全剩余系時(shí)，y=x2

m2x3

m2m3x4

m2

mkxk

1通過(guò)模m2m3

mk

1的完全剩余系。

2024/5/639阜陽(yáng)師范學(xué)院數(shù)科院y=x2

m2x3

m2m3x4

m2

mkxk

1通過(guò)模m2m3

mk

1的完全剩余系。

由定理4，當(dāng)x1通過(guò)模m1的完全剩余系，

xi（2

i

k

1）通過(guò)模mi的完全剩余系時(shí)，x1

m1y=x1

m1(x2

m2x3

m2

mkxk

1)=x1

m1x2

m1m2x3

m1m2

mkxk

1通過(guò)模m1m2

mk

1的完全剩余系。

即結(jié)論對(duì)于n=k

1也成立。

2024/5/640阜陽(yáng)師范學(xué)院數(shù)科院三、與抽象代數(shù)的關(guān)系若將模m的剩余類作為元素，則

同余?剩余類的相等，同余的運(yùn)算?元素〔剩余類〕的運(yùn)算，剩余類的集合即是環(huán)。特別地，當(dāng)m為合數(shù)時(shí)，就有：

非零的剩余類的乘積可能為零的剩余類，即存在零因子的環(huán)。上述環(huán)中所有與模m互質(zhì)的剩余類對(duì)乘法構(gòu)成群；當(dāng)m為質(zhì)數(shù)時(shí)，上述的環(huán)又可以構(gòu)成一個(gè)有限域。2024/5/641阜陽(yáng)師范學(xué)院數(shù)科院2024/5/642阜陽(yáng)師范學(xué)院數(shù)科院§3.3簡(jiǎn)化剩余系與歐拉函數(shù)一、基本概念定義1

設(shè)R是模m的一個(gè)剩余類，若有a

R，使得(a,m)=1，則稱R是模m的一個(gè)簡(jiǎn)化剩余類。即與模m互質(zhì)的剩余類。

注：若R是模的簡(jiǎn)化剩余類，則R中的數(shù)都與m互素。例如，模4的簡(jiǎn)化剩余類有兩個(gè)：R1(4)={

,

7,

3,1,5,9,

}，R3(4)={

,

5,

1,3,7,11,

}。2024/5/643阜陽(yáng)師范學(xué)院數(shù)科院定義2

對(duì)于正整數(shù)k，令函數(shù)

(k)的值等于模k的所有簡(jiǎn)化剩余類的個(gè)數(shù)，稱

(k)為Euler函數(shù)。容易驗(yàn)證：

(2)=1，(3)=2，(4)=2，(7)=6。注：

(m)就是在m的一個(gè)完全剩余系中與m互素的

整數(shù)的個(gè)數(shù)，且定義3

對(duì)于正整數(shù)m，從模m的每個(gè)簡(jiǎn)化剩余類中

各取一個(gè)數(shù)xi，構(gòu)成一個(gè)集合{x1,x2,

,x

(m)}，

稱為模m的一個(gè)簡(jiǎn)化剩余系（或簡(jiǎn)稱為簡(jiǎn)化系）。

2024/5/644阜陽(yáng)師范學(xué)院數(shù)科院注：由于選取方式的任意性，模m的簡(jiǎn)化剩余系有無(wú)窮多個(gè)。例如，集合{9,

5,

3,

1}是模8的簡(jiǎn)化剩余系；

集合{1,3,5,7}也是模8的簡(jiǎn)化剩余系.集合{1,3,5,7}稱為最小非負(fù)簡(jiǎn)化剩余系。2024/5/645阜陽(yáng)師范學(xué)院數(shù)科院二、主要性質(zhì)定理1

整數(shù)集合A是模m的簡(jiǎn)化剩余系的充要條件是：①A中含有

(m)個(gè)整數(shù)；②A中的任何兩個(gè)整數(shù)對(duì)模m不同余；③A中的每個(gè)整數(shù)都與m互素。說(shuō)明：簡(jiǎn)化剩余系是某個(gè)完全剩余系中的部分元素構(gòu)成的集合，故滿足條件2；

由定義1易知滿足條件3；由定義3易知滿足條件1。2024/5/646阜陽(yáng)師范學(xué)院數(shù)科院定理2

設(shè)a是整數(shù)，(a,m)=1，B={x1,x2,

,x

(m)}

是模m的簡(jiǎn)化剩余系，則集合

A={ax1,ax2,

,ax

(m)}

也是模m的簡(jiǎn)化剩余系。證明

顯然，集合A中有

(m)個(gè)整數(shù)。

由于(a,m)=1，

對(duì)于任意的xi（1

i

(m)），xi

B，

有(axi,m)=(xi,m)=1。

故A中的每一個(gè)數(shù)都與m互素。

而且，A中的任何兩個(gè)不同的整數(shù)對(duì)模m不同余。

因?yàn)椋粲衳

,x

B，使得

ax

ax

(modm)，那么，

x

x

(modm)，

于是x

=x

。

由以上結(jié)論及定理1可知集合A是模m的一個(gè)簡(jiǎn)化系。

2024/5/647阜陽(yáng)師范學(xué)院數(shù)科院注：在定理2的條件下，若b是整數(shù)，集合{ax1

b,ax2

b,,

,ax

(m)

b}不一定是模m的簡(jiǎn)化剩余系。

例如，取m=4，a=1，b=1，

以及模4的簡(jiǎn)化剩余系{1,3}。但｛2，4｝不是模4的簡(jiǎn)化剩余系。2024/5/648阜陽(yáng)師范學(xué)院數(shù)科院定理3

設(shè)m1,m2

N，(m1,m2)=1，又設(shè)分別是模m1與m2的簡(jiǎn)化剩余系，

則

A={m1y

m2x；x

X，y

Y

}是模m1m2的簡(jiǎn)化剩余系。證明由第二節(jié)定理3推論可知，若以X

與Y

分別表示

模m1與m2的完全剩余系，使得X

X

，Y

Y

，

則A

={m1y

m2x；x

X

，y

Y

}是模m1m2的完全剩余系。

因此只需證明A

中所有與m1m2互素的整數(shù)的集合R

即模m1m2的簡(jiǎn)化剩余系是集合A。

2024/5/649阜陽(yáng)師范學(xué)院數(shù)科院若m1y

m2x

R，則(m1y

m2x,m1m2)=1，

所以(m1y

m2x,m1)=1，

于是

(m2x,m1)=1，(x,m1)=1，x

X。同理可得到y(tǒng)

Y，因此m1y

m2x

A。

這說(shuō)明R

A。

另一方面，若m1y

m2x

A，則x

X，y

Y，

即

(x,m1)=1，(y,m2)=1。由此及(m1,m2)=1得到

(m2x

m1y,m1)=(m2x,m1)=1(m2x

m1y,m2)=(m1y,m2)=1。因?yàn)閙1與m2互素，所以(m2x

m1y,m1m2)=1，

于是m2x

m1y

R。因此A

R。

從而A=R。

2024/5/650阜陽(yáng)師范學(xué)院數(shù)科院推論

設(shè)m,n

N，(m,n)=1，則

(mn)=

(m)

(n)。證

由定理3知，若x,y分別通過(guò)m,n的簡(jiǎn)化剩余系，

則my

nx通過(guò)mn的簡(jiǎn)化剩余系，

即有

my

nx通過(guò)

(mn)個(gè)整數(shù)。

另一方面，x〔nx〕通過(guò)

(m)個(gè)整數(shù)，

y〔my〕通過(guò)

(n)個(gè)整數(shù),

從而my

nx通過(guò)

(m)

(n)個(gè)整數(shù)。故有

(mn)=

(m)

(n)。注：可以推廣到多個(gè)兩兩互質(zhì)數(shù)的情形。2024/5/651阜陽(yáng)師范學(xué)院數(shù)科院定理4

設(shè)n是正整數(shù)，p1,p2,

,pk是它的全部素因數(shù)，

證

設(shè)n的標(biāo)準(zhǔn)分解式是

由定理3推論得到對(duì)任意的素?cái)?shù)p，

(p

)等于數(shù)列1,2,

,p

中與p

互素的整數(shù)的個(gè)數(shù)，

從而定理得證。2024/5/652阜陽(yáng)師范學(xué)院數(shù)科院注：由定理4可知，

(n)=1的充要條件是n=1或2。考慮有重素因子和沒(méi)有重素因子的情形。

三、應(yīng)用舉例注意：有重素因子時(shí)，上述不等式中等號(hào)不成立！2024/5/653阜陽(yáng)師范學(xué)院數(shù)科院例1

設(shè)整數(shù)n

2，證明：

即在數(shù)列1,2,

,n中，與n互素的整數(shù)之和是

證

設(shè)在1,2,

,n中與n互素的個(gè)數(shù)是

(n)，a1,a2,

,a

(n)，(ai,n)=1，1

ai

n

1，1

i

(n)，則

(n

ai,n)=1，1

n

ai

n

1，1

i

(n)，因此，集合{a1,a2,

,a

(n)}故

a1

a2

a

(n)=(n

a1)

(n

a2)

(n

a

(n))，從而，2(a1

a2

a

(n))=n(n)，因此

a1

a2

a

(n)

與集合{n

a1,n

a2,

,n

a

(n)}是相同的，2024/5/654阜陽(yáng)師范學(xué)院數(shù)科院例2

設(shè)n

N，證明：1)若n是奇數(shù)，則

(4n)=2

(n)；的充要條件是n=2k，k

N；的充要條件是n=2k3l，k,l

N；4)若6

n，則

(n)

5)若n

1與n

1都是素?cái)?shù)，n>4，則

(n)

2024/5/655阜陽(yáng)師范學(xué)院數(shù)科院1)若n是奇數(shù)，則

(4n)=2

(n)；

(4n)=

(22n)=

(22)

(n)=2

(n)〔TH4〕2024/5/656阜陽(yáng)師范學(xué)院數(shù)科院的充要條件是n=2k，k

N；若n=2k，

若

(n)=

設(shè)n=2kn1，

由

(n)=

(2kn1)=(2k)

(n1)

=2k

1

(n1)

所以n1=1，即n=2k；2024/5/657阜陽(yáng)師范學(xué)院數(shù)科院的充要條件是n=2k3l，k,l

N；設(shè)n=2k3ln1，

所以n1=1，即n=2k3l；若n=2k3l，則

(n)=

(2k)

(3l)2024/5/658阜陽(yáng)師范學(xué)院數(shù)科院4)若6

n，則

(n)

設(shè)n=2k3ln1，

則

(n)=

(2k)

(3l)

(n1)

2024/5/659阜陽(yáng)師范學(xué)院數(shù)科院5)若n

1與n

1都是素?cái)?shù)，n>4，則

(n)

因?yàn)閚>4，且n

1與n

1都是奇素?cái)?shù)，

所以n是偶數(shù)，且n

1>3.所以n

1與n

1都不等于3，所以3

n，由結(jié)論4，也不能被3整除，因此6

n。即可得到結(jié)論5。若6

n，則

(n)

2024/5/660阜陽(yáng)師范學(xué)院數(shù)科院例3

證明：若m,n

N，則

(mn)=(m,n)

([m,n])；證：

顯然mn與[m,n]有相同的素因數(shù)，

設(shè)它們是pi（1

i

k），則由此兩式及mn=(m,n)[m,n]即可得證。2024/5/661阜陽(yáng)師范學(xué)院數(shù)科院2024/5/662阜陽(yáng)師范學(xué)院數(shù)科院§3.4歐拉定理費(fèi)馬定理及其對(duì)循環(huán)小數(shù)的應(yīng)用本節(jié)主要通過(guò)應(yīng)用簡(jiǎn)化剩余系的性質(zhì)證明數(shù)論中的兩個(gè)重要定理，歐拉定理和費(fèi)馬定理，并說(shuō)明其在理論和解決實(shí)際問(wèn)題中的應(yīng)用。2024/5/663阜陽(yáng)師范學(xué)院數(shù)科院一、兩個(gè)基本定理定理1

Euler

設(shè)m是正整數(shù)，(a,m)=1，

則

a

m)

1(modm).證明：

設(shè){x1,x2,

,x

(m)}是模m的一個(gè)簡(jiǎn)化剩余系，

則{ax1,ax2,

,ax

(m)}也是模m的簡(jiǎn)化剩余系，

所以ax1ax2

ax

(m)

x1x2

x

(m)

(modm)，即a

(m)x1x2

x

(m)

x1x2,

x

(m)

(modm).

得(x1x2

x

(m),m)=1，

所以

a

(m)

1(modm).

2024/5/664阜陽(yáng)師范學(xué)院數(shù)科院定理2(Fermat)

設(shè)p是素?cái)?shù)，

a

p

a(modp)。

注：Fermat定理即是歐拉定理的推論。證：

由于p是素?cái)?shù)，

若(a,p)

1，

則由定理1得到a

p

1

1(modp)

a

p

a(modp)

若(a,p)>1，則p

a，

所以

a

p

0

a(modp)

a

m)

1(modm)2024/5/665阜陽(yáng)師范學(xué)院數(shù)科院二、定理的應(yīng)用舉例例1求313159被7除的余數(shù)。解：313159所以由歐拉定理得a

m)

1(modm)從而

5159=(56)2653

53(mod7)

53=25

5

4

5

6(mod7)。即313159被7除的余數(shù)為6。2024/5/666阜陽(yáng)師范學(xué)院數(shù)科院例2

設(shè)n是正整數(shù)，則51n

2n

3n

4n的充要條件是4

n。證：

因?yàn)?/p>

(5)=4，

由定理1得a

m)

1(modm)k4

1(mod5)，1

k

4。因此，記n=4q

r，0

r

3，

則1n

2n

3n

4n

1r

2r

3r

4r

1r

2r

(

2)r

(

1)r(mod5).

用r=0，1，2，3分別代入即可得出結(jié)論。2024/5/667阜陽(yáng)師范學(xué)院數(shù)科院例3

設(shè){x1,x2,

,x

(m)}是模m的簡(jiǎn)化剩余系，

則

(x1x2

x

(m))2

1

(modm).證：

記P=x1x2

x

(m)，

則(P,m)=1.

1

i

(m)，則{y1,y2,

,y

(m)}也是模m的簡(jiǎn)化剩余系，

再由Euler定理得證.a

m)

1(modm)2024/5/668阜陽(yáng)師范學(xué)院數(shù)科院例4

設(shè)a，b，c，m是正整數(shù)，m>1，(b,m)=1，

并且

b

a

1(modm)，b

c

1(modm)，

記d=(a,c)，則bd

1(modm)。證

利用輾轉(zhuǎn)相除法可以求出整數(shù)x，y，使得ax

cy=d，

顯然xy

<0。若x>0，y<0，

則

1

b

ax=b

db

cy=b

d(b

c)

y

b

d(modm)若x<0，y>0，

則

1

b

cy=b

db

ax=b

d(ba)

x

b

d(modm)。2024/5/669阜陽(yáng)師范學(xué)院數(shù)科院例5

設(shè)n是正整數(shù)，記Fn=

證：

容易驗(yàn)證，當(dāng)n

4時(shí)Fn是素?cái)?shù)，

由Fermat定理可知結(jié)論顯然成立。a

p

a(modp)。

當(dāng)n

5時(shí)，有n

1<2n，

其中Q1與Q2是整數(shù)，

2024/5/670阜陽(yáng)師范學(xué)院數(shù)科院補(bǔ)充說(shuō)明我們已經(jīng)知道，F(xiàn)5是合數(shù)，因此例5表明，

Fermat定理的逆定理不成立。

設(shè)p是素?cái)?shù)，

a

p

a(modp)。

即若有整數(shù)a，(a,n)=1，使得

a

n

1

1(modn)，

并不能保證n是素?cái)?shù)。

例5

設(shè)n是正整數(shù)，記Fn=

Fermat定理2024/5/671阜陽(yáng)師范學(xué)院數(shù)科院例6

如果今天是星期一，再過(guò)101010天是星期幾？即得：再過(guò)101010天是星期五。2024/5/672阜陽(yáng)師范學(xué)院數(shù)科院三、在分?jǐn)?shù)與小數(shù)互化中的應(yīng)用有理數(shù)，即有限小數(shù)和無(wú)限循環(huán)小數(shù)，可以用分?jǐn)?shù)來(lái)表示。利用歐拉定理可以解決分?jǐn)?shù)、小數(shù)的轉(zhuǎn)化問(wèn)題。定義如果對(duì)于一個(gè)無(wú)限小數(shù)則稱之為循環(huán)小數(shù)，并簡(jiǎn)記為注：若找到的t是最小的，則稱

為循環(huán)節(jié)；t稱為循環(huán)節(jié)的長(zhǎng)度；若最小的s＝0，

則稱該小數(shù)為純循環(huán)小數(shù)，否則為混循環(huán)小數(shù)。2024/5/673阜陽(yáng)師范學(xué)院數(shù)科院定理3

有理數(shù)能表示為純循環(huán)小數(shù)即：分母不含質(zhì)因數(shù)2或5。2024/5/674阜陽(yáng)師范學(xué)院數(shù)科院定理3

有理數(shù)能表示為純循環(huán)小數(shù)

(b,10)=1

由Euler定理可知，有正