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

8/4/20231皖西學院數理系第三章同余同余是數論中的重要概念，同余理論是研§3.1同余的概念及其基本性質一、問題的提出1、今天是星期一，再過100天是星期幾？3、13511，13903，14589被自然數m除所得余數相同，問m最大值是多少？

2、3145×92653=291093995的橫線處漏寫了一個數字，你能以最快的辦法補出嗎？8/4/20232皖西學院數理系§3.1同余的概念及其基本性質一、問題的提出1、今天是星二、同余的定義注：下面的三個表示是等價的：8/4/20233皖西學院數理系二、同余的定義注：下面的三個表示是等價的：8/1/20233三、同余的性質TH2設a，b，c，d，k是整數，并且a

b(modm)，

c

d(modm)，則①

a

c

b

d(modm)；

②

ac

bd(modm);

③ak

bk(modm).注：TH1、TH2是最簡單、常用的性質。8/4/20234皖西學院數理系三、同余的性質TH2設a，b，c，d，k是整數，并且a8/4/20235皖西學院數理系8/1/20235皖西學院數理系TH4下面的結論成立：①

a

b(modm)，dm，d>0

a

b(modd)；②

a

b(modm)，k>0，kN

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);⑥⑦8/4/20236皖西學院數理系TH4下面的結論成立：①ab(modm)，①

a

b(modm)，dm，d>0

a

b(modd)；②

a

b(modm)，k>0，kN

ak

bk(modmk)；③

a

b(modmi

)，1

i

k

a

b(mod[m1,m2,,mk])；④

a

b(modm)(a,m)=(b,m)；8/4/20237皖西學院數理系①ab(modm)，dm，d>0a⑤

ac

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

a

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

不能成立。反例：取m=6,c=2,a=20,b=23.8/4/20238皖西學院數理系⑤acbc(modm)，(c,m)=1⑥⑦8/4/20239皖西學院數理系⑥⑦8/1/20239皖西學院數理系四、一些整數的整除特征(1)

3、9的整除特征——各位上的數字之和能被3（9）整除例1檢查5874192、435693能否被3（9）整除。8/4/202310皖西學院數理系四、一些整數的整除特征(1)3、9的整除特征——各位(2)7、11、13的整除特征注：一般地，求

被m除的余數時，

首先是求出正整數k，使得10k

1或1(modm)，

8/4/202311皖西學院數理系(2)7、11、13的整除特征注：一般地，求被m除的(2)7、11、13的整除特征特別地，由于，所以——奇偶位差法

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

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

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

8/4/202312皖西學院數理系(2)7、11、13的整除特征特別地，由于8/4/202313皖西學院數理系8/1/202313皖西學院數理系①求出整數k，使ak

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

r(modk)；——減小冪指數8/4/202314皖西學院數理系①求出整數k，使ak1(modm)；②求出正例4證明：若n是正整數，則1342n+13

n+2。解：42n+1

3

n+2=4×42n9×3

n

4×3n9×3

n=13×3

n0(mod13)=4×16n9×3

n8/4/202315皖西學院數理系例4證明：若n是正整數，則1342n+13n例5設n的十進制表示是

且792n，

求x，y，z.

解因為792=8×9×11，故8n，9n及11n。9n913

x

y45

z=19

x

y9x

y1，(1)11n11z54

y

x31=3

y

x113

y

x。(2)即有

x

y1=9或18，3

y

x=0或11解方程組，得到x=8，y=0，z=6。8/4/202316皖西學院數理系例5設n的十進制表示是且792n，求x，y，z.五、棄九法〔驗算計算結果〕應用這種方法可以驗算較大整數的乘法。例6.驗算28997×39495＝1145236415是否正確。注：若結論成立，其結果不一定正確；所以結果不正確。也可以檢查和、差的運算。8/4/202317皖西學院數理系五、棄九法〔驗算計算結果〕應用這種方法可以驗算較大整數的乘法例7.求方程2x

3y=1的正整數解。

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

3，則

所以

3y1(mod8)不能成立。故原方程的正整數解只有x=2,y=1.8/4/202318皖西學院數理系例7.求方程2x3y=1的正整數解。解：顯然習題講解：3.找出整數能被37、101整除的判別條件。8/4/202319皖西學院數理系習題講解：3.找出整數能被37、101整除的判別條件。8/1解：依次計算對模641的同余數22

4，2416，28256，8/4/202320皖西學院數理系解：依次計算對模641的同余數224，2416，解：設a=2m

1，當n=1時，有a2=(2m

1)2=4m(m1)11(mod23)（*）成立。設式(*)對于n=k成立，則有這說明式(*)當n=k

1也成立。

由歸納法得證.8/4/202321皖西學院數理系解：設a=2m1，當n=1時，有a2=(28/4/202322皖西學院數理系8/1/202322皖西學院數理系§3.2剩余類與完全剩余系

一、剩余類——按余數的不同對整數分類是模m的一個剩余類，

即余數相同的整數構成m的一個剩余類。一個剩余類中任意一個數稱為它同類的數的剩余。一個整數被正整數n除后，余數有n種情形：0，1，2，3，…，n-1，它們彼此對模n不同余。這表明，每個整數恰與這n個整數中某一個對模n同余。這樣一來，按模n是否同余對整數集進行分類，可以將整數集分成n個兩兩不相交的子集。8/4/202323皖西學院數理系§3.2剩余類與完全剩余系一、剩余類——按余數的不同定理1

8/4/202324皖西學院數理系定理18/1/202324皖西學院數理系二、完全剩余系1.定義2

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

1}是模m的最小非負完全剩余系；③若把剩余系作為一個集合，則可以把對模m的余數相同的整數——即同一剩余類里的整數，看作同一元素。8/4/202325皖西學院數理系二、完全剩余系1.定義2注：①完全剩余系不唯一；②{完全剩余系舉例：集合{0,6,7,13,24}是模5的一個完全剩余系，集合{0,1,2,3,4}是模5的最小非負完全剩余系。都是模m的絕對最小完全剩余系。是模m的絕對最小完全剩余系。

8/4/202326皖西學院數理系完全剩余系舉例：集合{0,6,7,13,24}是模52、完全剩余系的構造定理2

整數集合A是模m的完全剩余系的充要條件是①A中含有m個整數；②A中任何兩個整數對模m不同余。注：由定理1及定義2易得證。思考：1、既然完全剩余系是不唯一的，不同的剩余系之間存在什么關系呢？2、一個完全剩余系的所有元素通過線性變化后，還是完全剩余系嗎？8/4/202327皖西學院數理系2、完全剩余系的構造定理2整數集合A是模m的完全剩余系的檢驗：設{x1,x2,,xm}是模m的一個完全剩余系，那么，{b+x1,b+x2,,b+xm}和{ax1,ax2,,a

xm}是模m的一個完全剩余系嗎？8/4/202328皖西學院數理系檢驗：設{x1,x2,,xm}是模m的一個完全剩余系定理3

設m

1，a，b是整數，(a,m)=1，{x1,x2,,xm}是模m的一個完全剩余系，則{ax1

b,ax2

b,,axm

b}也是模m的完全剩余系。證明由定理2，只需證明：若xi

xj，

則axi

b

axj

b(modm)。

假設axi

b

axj

b(modm)，則axi

axj(modm)，且(a,m)=1，xi

xj(modm)

由§3.1中的結論,P50第三行知：8/4/202329皖西學院數理系定理3設m1，a，b是整數，(a,m)=1，{注意：(1)在定理3中，條件(a,m)=1不可缺少，否則不能成立；(2)定理3也可以敘述為：設m

1，a，b是整數，(a,m)=1，若x通過模m的一個完全剩余系，則ax+b也通過模m的一個完全剩余系；（3）特別地，若x通過模m的一個完全剩余系，(a,m)=1，，則ax和x+b也分別通過模m的一個完全剩余系。8/4/202330皖西學院數理系注意：(1)在定理3中，條件(a,m)=1不可缺少，否例1設p5是素數，a{2,3,,p

1}，則在數列a，2a，3a，，(p

1)a，pa中有且僅有一個數b，滿足b1(modp)；證：

因為｛1，2，3，，(p

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

1)a，pa｝構成模p的一個完全剩余系。因此必有唯一的數b滿足式b1(modp)。8/4/202331皖西學院數理系例1設p5是素數，a{2,3,,p例2設A={x1,x2,,xm}是模m的一個完全剩余系，以{x}表示x的小數部分，證明：若(a,m)=1，則

證：當x通過模m的完全剩余系時，ax

b也通過模m的完全剩余系，

因此對于任意的i（1

i

m），axi

b一定且只與某個整數j（1

j

m）同余，

即存在整數k，使得axi

b=km

j，（1

j

m）8/4/202332皖西學院數理系例2設A={x1,x2,,xm}是模m的一個3、剩余系間的聯系定理4

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

則R={Ax

m1y：xX，yY}是模m1m2的一個完全剩余系。證明由定理3只需證明：若x

,x

X，y

,y

Y，且Ax

m1y

Ax

m1y

(modm1m2)，

8/4/202333皖西學院數理系3、剩余系間的聯系定理4設m1,m2N，AZ，(A定理4

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

則R={Ax

m1y：xX，yY}是模m1m2的一個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)，8/4/202334皖西學院數理系定理4設m1,m2N，AZ，(A,m1)=1推論若m1,m2N，(m1,m2)=1，當x1與x2分別通過

模m1與模m2的完全剩余系時，

則

m2x1

m1x2通過模m1m2的完全剩余系。

8/4/202335皖西學院數理系推論若m1,m2N，(m1,m2)=1，當x1定理5

設miN，AiZ（1

i

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

i,j

n，i

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

i

n；③miAj

，1

i,j

n，i

j

。則當xi（1

i

n）通過模mi的完全剩余系Xi時，y=A1x1

A2x2

Anxn

通過模m1m2mn的完全剩余系。8/4/202336皖西學院數理系定理5設miN，AiZ（1in），并證：由定理3只需證明，若xi,xiXi，1

i

n，

A1x1

A2x2

Anxn

A1x1

A2x2

Anxn

(modm1mn)

則可以得到xi=xi，1

i

n.事實上，由條件3假設易得，

對于任意的i，1

i

n，有Aixi

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

xi(modmi)，因此xi=xi.

8/4/202337皖西學院數理系證：由定理3只需證明，若xi,xiXi，1例3

設m>0是偶數，{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的完全剩余系，

不可能！8/4/202338皖西學院數理系例3設m>0是偶數，{a1,a2,,am}與例4

設miN（1

i

n），則當xi通過模mi（1

i

n）

的完全剩余系時，x=x1

m1x2

m1m2x3

m1m2mn

1xn通過模m1m2mn的完全剩余系。證明對n施行歸納法。當n=2時，由定理4知定理結論成立。假設定理結論當n=k時成立，

即當xi（2

i

k1）分別通過模mi的完全剩余系時，y=x2

m2x3

m2m3x4

m2mkxk

1通過模m2m3mk

1的完全剩余系。

8/4/202339皖西學院數理系例4設miN（1in），則當xi通過模miy=x2

m2x3

m2m3x4

m2mkxk

1通過模m2m3mk

1的完全剩余系。

由定理4，當x1通過模m1的完全剩余系，

xi（2

i

k1）通過模mi的完全剩余系時，x1

m1y=x1

m1(x2

m2x3

m2mkxk

1)=x1

m1x2

m1m2x3

m1m2mkxk

1通過模m1m2mk

1的完全剩余系。

即結論對于n=k

1也成立。

8/4/202340皖西學院數理系y=x2m2x3m2m3x4m三、與抽象代數的關系若將模m的剩余類作為元素，則同余?剩余類的相等，同余的運算?元素〔剩余類〕的運算，剩余類的集合即是環(huán)。特別地，當m為合數時，就有：

非零的剩余類的乘積可能為零的剩余類，即存在零因子的環(huán)。上述環(huán)中所有與模m互質的剩余類對乘法構成群；當m為質數時，上述的環(huán)又可以構成一個有限域。8/4/202341皖西學院數理系三、與抽象代數的關系若將模m的剩余類作為元素，則同余?剩余8/4/202342皖西學院數理系8/1/202342皖西學院數理系§3.3簡化剩余系與歐拉函數一、基本概念定義1

設R是模m的一個剩余類，若有aR，使得(a,m)=1，則稱R是模m的一個簡化剩余類。即與模m互質的剩余類。

注：若R是模的簡化剩余類，則R中的數都與m互素。例如，模4的簡化剩余類有兩個：R1(4)={,7,3,1,5,9,}，R3(4)={,5,1,3,7,11,}。8/4/202343皖西學院數理系§3.3簡化剩余系與歐拉函數一、基本概念定義1設R是定義2

對于正整數k，令函數(k)的值等于模k的所有簡化剩余類的個數，稱(k)為Euler函數。容易驗證：(2)=1，(3)=2，(4)=2，(7)=6。注：(m)就是在m的一個完全剩余系中與m互素的

整數的個數，且定義3

對于正整數m，從模m的每個簡化剩余類中

各取一個數xi，構成一個集合{x1,x2,,x(m)}，

稱為模m的一個簡化剩余系（或簡稱為簡化系）。

8/4/202344皖西學院數理系定義2對于正整數k，令函數(k)的值等于模k的所有簡化注：由于選取方式的任意性，模m的簡化剩余系有無窮多個。例如，集合{9,5,3,1}是模8的簡化剩余系；

集合{1,3,5,7}也是模8的簡化剩余系.集合{1,3,5,7}稱為最小非負簡化剩余系。8/4/202345皖西學院數理系注：由于選取方式的任意性，模m的簡化剩余系有無窮多個。例如，二、主要性質定理1

整數集合A是模m的簡化剩余系的充要條件是：①A中含有(m)個整數；②A中的任何兩個整數對模m不同余；③A中的每個整數都與m互素。說明：簡化剩余系是某個完全剩余系中的部分元素構成的集合，故滿足條件2；

由定義1易知滿足條件3；由定義3易知滿足條件1。8/4/202346皖西學院數理系二、主要性質定理1整數集合A是模m的簡化剩余系的充要條定理2

設a是整數，(a,m)=1，B={x1,x2,,x(m)}

是模m的簡化剩余系，則集合

A={ax1,ax2,,ax(m)}

也是模m的簡化剩余系。證明顯然，集合A中有(m)個整數。

由于(a,m)=1，

對于任意的xi（1

i

(m)），xiB，

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

故A中的每一個數都與m互素。

而且，A中的任何兩個不同的整數對模m不同余。

因為，若有x

,x

B，使得ax

ax

(modm)，那么，

x

x

(modm)，

于是x

=x

。

由以上結論及定理1可知集合A是模m的一個簡化系。

8/4/202347皖西學院數理系定理2設a是整數，(a,m)=1，B={x注：在定理2的條件下，若b是整數，集合{ax1

b,ax2

b,,,ax(m)

b}不一定是模m的簡化剩余系。

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

以及模4的簡化剩余系{1,3}。但｛2，4｝不是模4的簡化剩余系。8/4/202348皖西學院數理系注：在定理2的條件下，若b是整數，集合{ax1b,a定理3

設m1,m2N，(m1,m2)=1，又設分別是模m1與m2的簡化剩余系，

則

A={m1y

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

與Y

分別表示

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

X

，Y

Y

，

則A

={m1y

m2x；xX

，yY

}是模m1m2的完全剩余系。

因此只需證明A

中所有與m1m2互素的整數的集合R

即模m1m2的簡化剩余系是集合A。

8/4/202349皖西學院數理系定理3設m1,m2N，(m1,m2)=1，若m1y

m2xR，則(m1y

m2x,m1m2)=1，

所以(m1y

m2x,m1)=1，

于是

(m2x,m1)=1，(x,m1)=1，xX。同理可得到y(tǒng)Y，因此m1y

m2xA。

這說明R

A。

另一方面，若m1y

m2xA，則xX，yY，

即

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

(m2x

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

m1y,m2)=(m1y,m2)=1。因為m1與m2互素，所以(m2x

m1y,m1m2)=1，

于是m2x

m1yR。因此A

R。

從而A=R。

8/4/202350皖西學院數理系若m1ym2xR，則(m1ym2x,m1m2推論設m,nN，(m,n)=1，則(mn)=(m)(n)。證由定理3知，若x,y分別通過m,n的簡化剩余系，

則my

nx通過mn的簡化剩余系，

即有my

nx通過(mn)個整數。

另一方面，x〔nx〕通過(m)個整數，

y〔my〕通過(n)個整數,

從而my

nx通過(m)

(n)個整數。故有(mn)=(m)(n)。注：可以推廣到多個兩兩互質數的情形。8/4/202351皖西學院數理系推論設m,nN，(m,n)=1，則(mn)定理4設n是正整數，p1,p2,,pk是它的全部素因數，

證設n的標準分解式是

由定理3推論得到對任意的素數p，

(p)等于數列1,2,

,p中與p互素的整數的個數，

從而定理得證。8/4/202352皖西學院數理系定理4設n是正整數，p1,p2,,pk是它的全部注：由定理4可知，(n)=1的充要條件是n=1或2?？紤]有重素因子和沒有重素因子的情形。

三、應用舉例注意：有重素因子時，上述不等式中等號不成立！8/4/202353皖西學院數理系注：由定理4可知，(n)=1的充要條件是n=1或2例1設整數n2，證明：

即在數列1,2,,n中，與n互素的整數之和是

證設在1,2,,n中與n互素的個數是(n)，a1,a2,,a(n)，(ai,n)=1，1

ai

n1，1

i

(n)，則(n

ai,n)=1，1

n

ai

n1，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)}是相同的，8/4/202354皖西學院數理系例1設整數n2，證明：即在數列1,2,,例2設nN，證明：1)若n是奇數，則(4n)=2(n)；的充要條件是n=2k，kN；的充要條件是n=2k3l，k,lN；4)若6n，則(n)

5)若n

1與n1都是素數，n>4，則(n)

8/4/202355皖西學院數理系例2設nN，證明：1)若n是奇數，則(4n)=1)若n是奇數，則(4n)=2(n)；(4n)=(22n)=(22)(n)=2(n)〔TH4〕8/4/202356皖西學院數理系1)若n是奇數，則(4n)=2(n)；(4n)的充要條件是n=2k，kN；若n=2k，

若(n)=

設n=2kn1，

由(n)=(2kn1)=(2k)(n1)

=2k

1(n1)

所以n1=1，即n=2k；8/4/202357皖西學院數理系的充要條件是n=2k，kN；若n=2k，若(n的充要條件是n=2k3l，k,lN；設n=2k3ln1，

所以n1=1，即n=2k3l；若n=2k3l，則(n)=(2k)(3l)8/4/202358皖西學院數理系的充要條件是n=2k3l，k,lN；設n=2k4)若6n，則(n)

設n=2k3ln1，

則(n)=(2k)(3l)(n1)

8/4/202359皖西學院數理系4)若6n，則(n)設n=2k3ln1，5)若n

1與n1都是素數，n>4，則(n)

因為n>4，且n

1與n1都是奇素數，

所以n是偶數，且n

1>3.所以n

1與n1都不等于3，所以3n，由結論4，也不能被3整除，因此6n。即可得到結論5。若6n，則(n)

8/4/202360皖西學院數理系5)若n1與n1都是素數，n>4，則(n例3證明：若m,nN，則(mn)=(m,n)([m,n])；證：顯然mn與[m,n]有相同的素因數，

設它們是pi（1

i

k），則由此兩式及mn=(m,n)[m,n]即可得證。8/4/202361皖西學院數理系例3證明：若m,nN，則(mn)=(m,n)8/4/202362皖西學院數理系8/1/202362皖西學院數理系§3.4歐拉定理費馬定理及其對循環(huán)小數的應用本節(jié)主要通過應用簡化剩余系的性質證明數論中的兩個重要定理，歐拉定理和費馬定理，并說明其在理論和解決實際問題中的應用。8/4/202363皖西學院數理系§3.4歐拉定理費馬定理及其對循環(huán)小數的應用一、兩個基本定理定理1Euler

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

則

am)

1(modm).證明：設{x1,x2,,x(m)}是模m的一個簡化剩余系，

則{ax1,ax2,,ax(m)}也是模m的簡化剩余系，

所以ax1ax2ax(m)

x1x2

x(m)

(modm)，即a(m)x1x2x(m)

x1x2,x(m)

(modm).

得(x1x2x(m),m)=1，

所以a(m)

1(modm).

8/4/202364皖西學院數理系一、兩個基本定理定理1Euler設m是正整數，(定理2(Fermat)

設p是素數，

a

p

a(modp)。

注：Fermat定理即是歐拉定理的推論。證：由于p是素數，

若(a,p)1，

則由定理1得到a

p

1

1(modp)

a

p

a(modp)

若(a,p)>1，則pa，

所以a

p

0

a(modp)

am)

1(modm)8/4/202365皖西學院數理系定理2(Fermat)設p是素數，apa二、定理的應用舉例例1求313159被7除的余數。解：313159所以由歐拉定理得am)

1(modm)從而5159=(56)2653

53(mod7)

53=255456(mod7)。即313159被7除的余數為6。8/4/202366皖西學院數理系二、定理的應用舉例例1求313159被7除的余數。解：例2設n是正整數，則51n

2n3n4n的充要條件是4n。證：因為(5)=4，

由定理1得am)

1(modm)k4

1(mod5)，1

k4。因此，記n=4q

r，0

r3，

則1n

2n3n4n1r2r3r4r

1r2r(2)r(1)r(mod5).

用r=0，1，2，3分別代入即可得出結論。8/4/202367皖西學院數理系例2設n是正整數，則51n2n3n例3設{x1,x2,,x(m)}是模m的簡化剩余系，

則

(x1x2x(m))2

1

(modm).證：記P=x1x2x(m)，

則(P,m)=1.

1

i

(m)，則{y1,y2,,y(m)}也是模m的簡化剩余系，

再由Euler定理得證.am)

1(modm)8/4/202368皖西學院數理系例3設{x1,x2,,x(m)}是模m的簡化剩例4設a，b，c，m是正整數，m>1，(b,m)=1，

并且

b

a

1(modm)，b

c

1(modm)，

記d=(a,c)，則bd

1(modm)。證利用輾轉相除法可以求出整數x，y，使得ax

cy=d，

顯然xy<0。若x>0，y<0，

則1

b

ax=b

dbcy=b

d(b

c)y

b

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

則1

b

cy=b

dbax=b

d(ba)x

b

d(modm)。8/4/202369皖西學院數理系例4設a，b，c，m是正整數，m>1，(b,m)例5設n是正整數，記Fn=

證：容易驗證，當n

4時Fn是素數，

由Fermat定理可知結論顯然成立。a

p

a(modp)。

當n5時，有n1<2n，

其中Q1與Q2是整數，

8/4/202370皖西學院數理系例5設n是正整數，記Fn=證：容易驗證，當n補充說明我們已經知道，F5是合數，因此例5表明，

Fermat定理的逆定理不成立。

設p是素數，

a

p

a(modp)。

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

a

n

1

1(modn)，

并不能保證n是素數。

例5設n是正整數，記Fn=

Fermat定理8/4/202371皖西學院數理系補充說明我們已經知道，F5是合數，因此例5表明，Ferma例6如果今天是星期一，再過101010天是星期幾？即得：再過101010天是星期五。8/4/202372皖西學院數理系例6如果今天是星期一，再過101010天是星期幾？即得：三、在分數與小數互化中的應用有理數，即有限小數和無限循環(huán)小數，可以用分數來表示。利用歐拉定理可以解決分數、小數的轉化問題。定義如果對于一個無限小數則稱之為循環(huán)小數，并簡記為注：若找到的t是最小的，則稱

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

則稱該小數為純循環(huán)小數，否則為混循環(huán)小數。8/4/202373皖西學院數理系三、在分數與小數互化中的應用有理數，即有限小數和無限定理3

有理數能表示為純循環(huán)小數即：分母不含質因數2或5。8/4/202374皖西學院數理系定理3有理數能表示為純循環(huán)小數即：分母不含質因數2或5定理3

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

(b,10)=1

由Euler定理可知，有正整數k，使得10k

1(modb)，0

k

(b)，因此存在整數q使得

而且ak,,a1不能都等于0，也不能都等于9。

=0.ak