初等数论§3同余

第三章同余同余是数论中的重要概念，同余理论是研究整数问题的重要工作之一.本章介绍同余的基本概念，剩余类和完全剩余系.生活中我会经常遇到与余数有关的问题，比如：某年级有将近400名学生。有一次演出节目排队时出现：如果每8人站成一列则多余1人；如果改为每9人站成一列则仍多余1人；结果发现现成每10人结成一列，结果还是多余1人；聪名的你知道该年级共有学生多少名吗？

2024/5/61阜阳师范学院数科院§3.1同余的概念及其基本性质一、问题的提出1、今天是星期一，再过100天是星期几？3、13511，13903，14589被自然数m除所得余数相同，问m最大值是多少？

2、3145×92653=291093995的横线处漏写了一个数字，你能以最快的办法补出吗？2024/5/62阜阳师范学院数科院二、同余的定义注：下面的三个表示是等价的：2024/5/63阜阳师范学院数科院三、同余的性质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是最简单、常用的性质。2024/5/64阜阳师范学院数科院2024/5/65阜阳师范学院数科院TH4下面的结论成立：①

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阜阳师范学院数科院①

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阜阳师范学院数科院⑤

ac

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

a

b(modm);注：若没有条件(c,m)=1，即为TH2③的逆命题，

不能成立。反例：取m=6,c=2,a=20,b=23.2024/5/68阜阳师范学院数科院⑥⑦2024/5/69阜阳师范学院数科院四、一些整数的整除特征(1)

3、9的整除特征——各位上的数字之和能被3（9）整除例1检查5874192、435693能否被3（9）整除。2024/5/610阜阳师范学院数科院(2)7、11、13的整除特征注：一般地，求

被m除的余数时，

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

1或1(modm)，

2024/5/611阜阳师范学院数科院(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整除。

2024/5/612阜阳师范学院数科院2024/5/613阜阳师范学院数科院①求出整数k，使ak

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

r(modk)；——减小幂指数2024/5/614阜阳师范学院数科院例4证明：若n是正整数，则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阜阳师范学院数科院例5

设n的十进制表示是

且792

n，

求x，y，z.

解

因为792=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阜阳师范学院数科院五、弃九法〔验算计算结果〕应用这种方法可以验算较大整数的乘法。例6.验算28997×39495＝1145236415是否正确。注：若结论成立，其结果不一定正确；所以结果不正确。也可以检查和、差的运算。2024/5/617阜阳师范学院数科院例7.求方程2x

3y=1的正整数解。

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

3，则

所以

3y

1(mod8)不能成立。故原方程的正整数解只有x=2,y=1.2024/5/618阜阳师范学院数科院习题讲解：3.找出整数能被37、101整除的判别条件。2024/5/619阜阳师范学院数科院解：依次计算对模641的同余数22

4，24

16，28

256，2024/5/620阜阳师范学院数科院解：设a=2m

1，当n=1时，有a2=(2m

1)2=4m(m

1)

1

1(mod23)（*）成立。设式(*)对于n=k成立，则有这说明式(*)当n=k

1也成立。

由归纳法得证.2024/5/621阜阳师范学院数科院2024/5/622阜阳师范学院数科院§3.2剩余类与完全剩余系

一、剩余类——按余数的不同对整数分类是模m的一个剩余类，

即

余数相同的整数构成m的一个剩余类。一个剩余类中任意一个数称为它同类的数的剩余。一个整数被正整数n除后，余数有n种情形：0，1，2，3，…，n-1，它们彼此对模n不同余。这表明，每个整数恰与这n个整数中某一个对模n同余。这样一来，按模n是否同余对整数集进行分类，可以将整数集分成n个两两不相交的子集。2024/5/623阜阳师范学院数科院定理1

2024/5/624阜阳师范学院数科院二、完全剩余系1.定义2

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

,m

1}是模m的最小非负完全剩余系；③若把剩余系作为一个集合，则可以把对模m的余数相同的整数——即同一剩余类里的整数，看作同一元素。2024/5/625阜阳师范学院数科院完全剩余系举例：集合{0,6,7,13,24}是模5的一个完全剩余系，集合{0,1,2,3,4}是模5的最小非负完全剩余系。都是模m的绝对最小完全剩余系。是模m的绝对最小完全剩余系。

2024/5/626阜阳师范学院数科院2、完全剩余系的构造定理2

整数集合A是模m的完全剩余系的充要条件是①A中含有m个整数；②A中任何两个整数对模m不同余。注：由定理1及定义2易得证。思考：1、既然完全剩余系是不唯一的，不同的剩余系之间存在什么关系呢？2、一个完全剩余系的所有元素通过线性变化后，还是完全剩余系吗？2024/5/627阜阳师范学院数科院检验：设{x1,x2,

,xm}是模m的一个完全剩余系，那么，{b+x1,b+x2,,b+xm}和

{ax1,ax2,,a

xm}是模m的一个完全剩余系吗？2024/5/628阜阳师范学院数科院定理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第三行知：2024/5/629阜阳师范学院数科院注意：(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的一个完全剩余系。2024/5/630阜阳师范学院数科院例1

设p

5是素数，a

{2,3,

,p

1}，则在数列a，2a，3a，

，(p

1)a，pa中有且仅有一个数b，满足

b

1(modp)；证

：

因为｛1，2，3，

，(p

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

，(p

1)a，pa｝构成模p的一个完全剩余系。因此必有唯一的数b满足式b

1(modp)。2024/5/631阜阳师范学院数科院例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）2024/5/632阜阳师范学院数科院3、剩余系间的联系定理4

设m1,m2

N，A

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

则

R={Ax

m1y：x

X，y

Y

}是模m1m2的一个完全剩余系。证明

由定理3只需证明：若x

,x

X，y

,y

Y，且Ax

m1y

Ax

m1y

(modm1m2)，

2024/5/633阜阳师范学院数科院定理4

设m1,m2

N，A

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

则

R={Ax

m1y：x

X，y

Y

}是模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)，2024/5/634阜阳师范学院数科院推论

若m1,m2

N，(m1,m2)=1，当x1与x2分别通过

模m1与模m2的完全剩余系时，

则

m2x1

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

2024/5/635阜阳师范学院数科院定理5

设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

。则当xi（1

i

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

A2x2

Anxn

通过模m1m2

mn的完全剩余系。2024/5/636阜阳师范学院数科院证：

由定理3只需证明，若xi

,xi

Xi，1

i

n，

A1x1

A2x2

Anxn

A1x1

A2x2

Anxn

(modm1

mn)

则可以得到xi

=xi

，1

i

n.事实上，由条件3假设易得，

对于任意的i，1

i

n，有Aixi

Aixi

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

xi

xi

(modmi)，因此xi

=xi

.

2024/5/637阜阳师范学院数科院例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的完全剩余系，

不可能！2024/5/638阜阳师范学院数科院例4

设mi

N（1

i

n），则当xi通过模mi（1

i

n）

的完全剩余系时，x=x1

m1x2

m1m2x3

m1m2

mn

1xn通过模m1m2

mn的完全剩余系。证明

对n施行归纳法。当n=2时，由定理4知定理结论成立。假设定理结论当n=k时成立，

即当xi（2

i

k

1）分别通过模mi的完全剩余系时，y=x2

m2x3

m2m3x4

m2

mkxk

1通过模m2m3

mk

1的完全剩余系。

2024/5/639阜阳师范学院数科院y=x2

m2x3

m2m3x4

m2

mkxk

1通过模m2m3

mk

1的完全剩余系。

由定理4，当x1通过模m1的完全剩余系，

xi（2

i

k

1）通过模mi的完全剩余系时，x1

m1y=x1

m1(x2

m2x3

m2

mkxk

1)=x1

m1x2

m1m2x3

m1m2

mkxk

1通过模m1m2

mk

1的完全剩余系。

即结论对于n=k

1也成立。

2024/5/640阜阳师范学院数科院三、与抽象代数的关系若将模m的剩余类作为元素，则

同余↔剩余类的相等，同余的运算↔元素〔剩余类〕的运算，剩余类的集合即是环。特别地，当m为合数时，就有：

非零的剩余类的乘积可能为零的剩余类，即存在零因子的环。上述环中所有与模m互质的剩余类对乘法构成群；当m为质数时，上述的环又可以构成一个有限域。2024/5/641阜阳师范学院数科院2024/5/642阜阳师范学院数科院§3.3简化剩余系与欧拉函数一、基本概念定义1

设R是模m的一个剩余类，若有a

R，使得(a,m)=1，则称R是模m的一个简化剩余类。即与模m互质的剩余类。

注：若R是模的简化剩余类，则R中的数都与m互素。例如，模4的简化剩余类有两个：R1(4)={

,

7,

3,1,5,9,

}，R3(4)={

,

5,

1,3,7,11,

}。2024/5/643阜阳师范学院数科院定义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的一个简化剩余系（或简称为简化系）。

2024/5/644阜阳师范学院数科院注：由于选取方式的任意性，模m的简化剩余系有无穷多个。例如，集合{9,

5,

3,

1}是模8的简化剩余系；

集合{1,3,5,7}也是模8的简化剩余系.集合{1,3,5,7}称为最小非负简化剩余系。2024/5/645阜阳师范学院数科院二、主要性质定理1

整数集合A是模m的简化剩余系的充要条件是：①A中含有

(m)个整数；②A中的任何两个整数对模m不同余；③A中的每个整数都与m互素。说明：简化剩余系是某个完全剩余系中的部分元素构成的集合，故满足条件2；

由定义1易知满足条件3；由定义3易知满足条件1。2024/5/646阜阳师范学院数科院定理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)），xi

B，

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

故A中的每一个数都与m互素。

而且，A中的任何两个不同的整数对模m不同余。

因为，若有x

,x

B，使得

ax

ax

(modm)，那么，

x

x

(modm)，

于是x

=x

。

由以上结论及定理1可知集合A是模m的一个简化系。

2024/5/647阜阳师范学院数科院注：在定理2的条件下，若b是整数，集合{ax1

b,ax2

b,,

,ax

(m)

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

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

以及模4的简化剩余系{1,3}。但｛2，4｝不是模4的简化剩余系。2024/5/648阜阳师范学院数科院定理3

设m1,m2

N，(m1,m2)=1，又设分别是模m1与m2的简化剩余系，

则

A={m1y

m2x；x

X，y

Y

}是模m1m2的简化剩余系。证明由第二节定理3推论可知，若以X

与Y

分别表示

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

X

，Y

Y

，

则A

={m1y

m2x；x

X

，y

Y

}是模m1m2的完全剩余系。

因此只需证明A

中所有与m1m2互素的整数的集合R

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

2024/5/649阜阳师范学院数科院若m1y

m2x

R，则(m1y

m2x,m1m2)=1，

所以(m1y

m2x,m1)=1，

于是

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

X。同理可得到y

Y，因此m1y

m2x

A。

这说明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。因为m1与m2互素，所以(m2x

m1y,m1m2)=1，

于是m2x

m1y

R。因此A

R。

从而A=R。

2024/5/650阜阳师范学院数科院推论

设m,n

N，(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)。注：可以推广到多个两两互质数的情形。2024/5/651阜阳师范学院数科院定理4

设n是正整数，p1,p2,

,pk是它的全部素因数，

证

设n的标准分解式是

由定理3推论得到对任意的素数p，

(p

)等于数列1,2,

,p

中与p

互素的整数的个数，

从而定理得证。2024/5/652阜阳师范学院数科院注：由定理4可知，

(n)=1的充要条件是n=1或2。考虑有重素因子和没有重素因子的情形。

三、应用举例注意：有重素因子时，上述不等式中等号不成立！2024/5/653阜阳师范学院数科院例1

设整数n

2，证明：

即在数列1,2,

,n中，与n互素的整数之和是

证

设在1,2,

,n中与n互素的个数是

(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阜阳师范学院数科院例2

设n

N，证明：1)若n是奇数，则

(4n)=2

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

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

N；4)若6

n，则

(n)

5)若n

1与n

1都是素数，n>4，则

(n)

2024/5/655阜阳师范学院数科院1)若n是奇数，则

(4n)=2

(n)；

(4n)=

(22n)=

(22)

(n)=2

(n)〔TH4〕2024/5/656阜阳师范学院数科院的充要条件是n=2k，k

N；若n=2k，

若

(n)=

设n=2kn1，

由

(n)=

(2kn1)=(2k)

(n1)

=2k

1

(n1)

所以n1=1，即n=2k；2024/5/657阜阳师范学院数科院的充要条件是n=2k3l，k,l

N；设n=2k3ln1，

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

(n)=

(2k)

(3l)2024/5/658阜阳师范学院数科院4)若6

n，则

(n)

设n=2k3ln1，

则

(n)=

(2k)

(3l)

(n1)

2024/5/659阜阳师范学院数科院5)若n

1与n

1都是素数，n>4，则

(n)

因为n>4，且n

1与n

1都是奇素数，

所以n是偶数，且n

1>3.所以n

1与n

1都不等于3，所以3

n，由结论4，也不能被3整除，因此6

n。即可得到结论5。若6

n，则

(n)

2024/5/660阜阳师范学院数科院例3

证明：若m,n

N，则

(mn)=(m,n)

([m,n])；证：

显然mn与[m,n]有相同的素因数，

设它们是pi（1

i

k），则由此两式及mn=(m,n)[m,n]即可得证。2024/5/661阜阳师范学院数科院2024/5/662阜阳师范学院数科院§3.4欧拉定理费马定理及其对循环小数的应用本节主要通过应用简化剩余系的性质证明数论中的两个重要定理，欧拉定理和费马定理，并说明其在理论和解决实际问题中的应用。2024/5/663阜阳师范学院数科院一、两个基本定理定理1

Euler

设m是正整数，(a,m)=1，

则

a

m)

1(modm).证明：

设{x1,x2,

,x

(m)}是模m的一个简化剩余系，

则{ax1,ax2,

,ax

(m)}也是模m的简化剩余系，

所以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阜阳师范学院数科院定理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，则p

a，

所以

a

p

0

a(modp)

a

m)

1(modm)2024/5/665阜阳师范学院数科院二、定理的应用举例例1求313159被7除的余数。解：313159所以由欧拉定理得a

m)

1(modm)从而

5159=(56)2653

53(mod7)

53=25

5

4

5

6(mod7)。即313159被7除的余数为6。2024/5/666阜阳师范学院数科院例2

设n是正整数，则51n

2n

3n

4n的充要条件是4

n。证：

因为

(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分别代入即可得出结论。2024/5/667阜阳师范学院数科院例3

设{x1,x2,

,x

(m)}是模m的简化剩余系，

则

(x1x2

x

(m))2

1

(modm).证：

记P=x1x2

x

(m)，

则(P,m)=1.

1

i

(m)，则{y1,y2,

,y

(m)}也是模m的简化剩余系，

再由Euler定理得证.a

m)

1(modm)2024/5/668阜阳师范学院数科院例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

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阜阳师范学院数科院例5

设n是正整数，记Fn=

证：

容易验证，当n

4时Fn是素数，

由Fermat定理可知结论显然成立。a

p

a(modp)。

当n

5时，有n

1<2n，

其中Q1与Q2是整数，

2024/5/670阜阳师范学院数科院补充说明我们已经知道，F5是合数，因此例5表明，

Fermat定理的逆定理不成立。

设p是素数，

a

p

a(modp)。

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

a

n

1

1(modn)，

并不能保证n是素数。

例5

设n是正整数，记Fn=

Fermat定理2024/5/671阜阳师范学院数科院例6

如果今天是星期一，再过101010天是星期几？即得：再过101010天是星期五。2024/5/672阜阳师范学院数科院三、在分数与小数互化中的应用有理数，即有限小数和无限循环小数，可以用分数来表示。利用欧拉定理可以解决分数、小数的转化问题。定义如果对于一个无限小数则称之为循环小数，并简记为注：若找到的t是最小的，则称

为循环节；t称为循环节的长度；若最小的s＝0，

则称该小数为纯循环小数，否则为混循环小数。2024/5/673阜阳师范学院数科院定理3

有理数能表示为纯循环小数即：分母不含质因数2或5。2024/5/674阜阳师范学院数科院定理3

有理数能表示为纯循环小数

(b,10)=1

由Euler定理可知，有正