《离散数学教程》第4章 初等数论

离散数学第4章初等数论离散数学第4章初等数论

第10章特殊图10.1整除和素数

10.4同余离散数学第4章初等数论

4.1.1整除定义4.1

设a,b是整数，a

0，如果存在整数c，使得b=a*c成立（这里*为数乘运算，下同。我们也会像初等数学学习时那样，很多时候省略乘运算符号），则称a整除b，或b可被a整除，使用记号ab表示之。这时又称b是a的倍数，a是b的因子（约数、因数或除数）。如果不存在整数c使得b=ac成立，则称a不整除b，b不可被a整除，记为ab。例4.18|48，13|200，23|09|54，(5|4)，(3|14)例4.26的因子有1，2，3和6，13的因子只有1和13。4.1整除和素数离散数学第4章初等数论

4.1.1整除定义4.2

若整数a

0，a

1，并且除平凡因子1和a外没有其他因子，则称a是素数（或质数）；否则称a为合数。素数在数论中有着极其重要的地位。以后若无特别说明，素数总是指正素数。2是第一个素数，其后还有3，5，7，11，等等，对它们我们还要做更深入的讨论。4.1整除和素数离散数学第4章初等数论

4.1.1整除定理4.1

a，b，c是整数，则有：（1）ab

当且仅当ab；（2）若ab，bc

，则ac；（3）若bai，i=1,2,,k,则ba1x1a2x2akxk，此处xi(i

=1,2,,k)是任意的整数；（4）若ba

，则bcac，此处c是任意的非零整数；（5）若ba，a0则|b||a|；（6）若ba且|a|<|b|，则a=0。4.1整除和素数离散数学第4章初等数论

4.1.1整除证(3)

因为bai，故存在整数ci使得ai=bci

,i=1,2,,k，则，

a1x1a2x2akxk=bc1x1bc2x2bckxk=b(c1x1c2x2ckxk)其中c1x1c2x2ckxk是整数。因此，ba1x1a2x2akxk。(5)

因为ba，a

0，故有整数c

0，使得a=bc；从而|a|=|b||c|，又由|c|≥1，故|b||a|。(6)

若ba且|a|<|b|，故有整数c0，使得a=bc，从而|a|=|b||c|。由于|a|<|b|，可知|c|=0，故c=0，从而a=0。4.1整除和素数离散数学第4章初等数论

4.1.1整除整除的定义和性质很简单，但却是数论的基础，有广泛的应用，且其应用往往具有很强的趣味性和技巧性。

例4.3

求证：若n是奇数，则8(n2

1)。解设n=2k

1，k是整数，则n2

1=(2k

1)2

1=4k(k

1)。由于在k和k

1中必有一个是偶数，所以8n2

1。4.1整除和素数离散数学第4章初等数论

4.1.1整除例4.4

证明：下列方程无整数解：x12x22x32=1999解若x1

,x2,x3都是奇数，据例4.3，存在整数A1,A2,A3,使得

x12=8A1

1，x22=8A2

1，x32=8A3

1，

x12

x22

x32=8(A1

A2

A3)

3，它被8除的余数是3，而1999被8除的余数是7。故x1，x2，x3不可能都是奇数。

4.1整除和素数离散数学第4章初等数论

4.1.1整除例4.4

证明：下列方程无整数解：x12x22x32=1999

解(续)另，由式x12x22x32=1999，知x1,x2,x3中只能有且仅有一个奇数。设x1为奇数，x2，x3为偶数，则存在整数A1，A2，A3，使得x12=8A11，x22=8A2r，x32=8A3s，其中r和s是整数，而且只能取值0或4（因为x22，x32是4的倍数）。于是x12x22x32=8(A1A2A3)1rs，这样x12x22x32被8除的余数只可能是1或5，但1999被8除的余数是7，因此这样的x1，x2，x3也不能使x12x22x32=1999成立。综上证得所需要的结论。4.1整除和素数离散数学第4章初等数论

4.1.1整除定理4.2（带余除法）设a与b是两个整数，b

0，则存在唯一确定的一对整数q和r，使得

a=bq

r，0

r<|b|（4-1）其中q称为a被b除的商，r称为a被b除的余数。例4.5

a=13，b=5，则a被b除时，商q=2，余数r=3

a=151，b=31，则a被b除时，商q=4，余数r=27

a=15，b=4，则a被b除时，商q=4，余数r=14.1整除和素数离散数学第4章初等数论

4.1.1整除例4.6

求证：在任意给定的五个整数中，必有三个数之和被3整除。证

设这五个数是ai，i=1,2,3,4,5，记

ai=3qiri，0ri<3，i=1,2,3,4,5。分别考虑以下两种情形：(a)若在r1,r2,,r5中数0,1,2都出现，不妨设r1=0,r2=1,r3=2，此时,a1a2a3=3(q1q2q3)3，可以被3整除；(b)若在r1,r2,,r5中数0,1,2至少有一个不出现，根据鸽笼原理，至少有三个ri要取相同的值，不妨设r1=r2=r3=r（r=0,1或2），此时,a1a2a3=3(q1q2q3)3r，可以被3整除。综上所述，五个整数中必有三个之和可被3整除，命题得证。4.1整除和素数离散数学第4章初等数论

4.1.2最大公因子定义4.3

如果整数k整除a,b，那么称k为非零整数a，b的公因子。

a,b的公因子中最大的一个称为最大公因子(或最大公因数)，记为gcd(a,b)。如下可推广定义多个非零整数的最大公因子：

gcd(a1,a2,a3)=gcd(gcd(a1,a2),a3)

gcd(a1,a2,…,an)=gcd(gcd(a1,a2,…,an-1),an)。4.1整除和素数定义4.4

如果gcd(a1,a2,,ak)=1，称a1,a2,,ak是互素的(或互质的)；如果

gcd(ai,aj)=1，1

i,j

k，i

j，则称a1,

a2,,ak是两两互素的（或两两互质的）。离散数学第4章初等数论

4.1.2最大公因子定理4.3

若a=bq

r，则gcd(a,b)=gcd(b,r)证

由定理4.1可知，如果da，db，则有dr，因为r=a

bq；反之，若db，dr，则da

，因为a=bq

r。因此，a与b的全体公因子的集合就是b与r的全体公因子的集合，这两个集合中的最大正数当然相等，即gcd(a,b)=gcd(b,r)。证毕。例4.8

由22=4*5+2，可知gcd(22,4)=gcd(4,2)=2。4.1整除和素数离散数学第4章初等数论

4.1.2最大公因子定义4.5

如果a，b是整数，那么具有形式ma+nb的数称为它们的线性组合，其中m，n也都是整数。定理4.4

如果整数a,b不全为零，最大公因子为d，则存在整数m,n使得d=am+bn。4.1整除和素数证

令S={ax+by>0|x,yI},显然S非空,那么S中存在最小的正整数，设为e,令e=am+bn,这里m,n是整数，下面证明e即为最大公因子d。先证e≤d。用e除a，由带余除法，我们有a=qe+r，0≤r<e，所以

r=aqe=aq(ma+nb)=(1qm)aqnb如果r≠0，则r

S,与e是S中最小整数矛盾，故r=0，因此e|a。同理可证e|b，故e是a,b的一个公约数，这就证明了e≤d

。再证d≤e。由gcd(a,b)=d，知d|a，d|b，知d|(am+bn)，即d|e，故

d≤e。因此，e=d，证毕。离散数学第4章初等数论

4.1.2最大公因子推论4.4.1

设d是a，b的一个公因子，则dgcd(a,b)。证

由定理4.4存在整数m,n使得

gcd(a,b)=am+bn，因为d是a，b的一个公因子，所以d|a，d|b，故由定理4.1，d|gcd(a,b)。

4.1整除和素数离散数学第4章初等数论

4.1.2最大公因子定理4.5

对于任意的整数a，b，c，下面的结论成立：（1）由bac及gcd(a,b)=1可以推出bc；（2）由bc，ac及gcd(a,b)=1可以推出abc。证

（1）若gcd(a,b)=1，由定理4.4，存在整数x与y，使得

axby=1。因此，acxbcy=c，再由bac便得到bc。（2）若gcd(a,b)=1，则存在整数x，y使得式axby=1成立，进而有acxbcy=c。由bc与ac得到abac，abbc，再由式acx

bcy=c得到abc。4.1整除和素数离散数学第4章初等数论

4.1.2最大公因子推论4.5.1

若p是素数，那么下述结论成立：（1）若pab

则pa或pb；（2）若pa2

则pa。依据定理4.5可得（1）的证明，留作习题。（2）显然是（1）得简单推论。4.1整除和素数离散数学第4章初等数论

4.1.2最大公因子推论4.5.2

若gcd(a,b)=1，则gcd(a,bc)=gcd(a,c)。证

若gcd(a,b)=1，由定理4.4，存在整数x与y，使得axby=1，因此acxbcy=c。下面证明“a与c的公因子的集合等同a与bc的公因子的集合”。设d是a与bc的一个公因子，则da，dbc，由acxbcy=c得到，d|c,即d是a与c的公因子。另一面，若d是a与c的公因子，则它也是a与bc的公因子。因此，a与c的公因子的集合，就是a与bc的公因子的集合，因而它们的最大者也相同，即gcd(a,bc)=gcd(a,c)。4.1整除和素数离散数学第4章初等数论

4.1.2最大公因子定理4.6（辗转相除法）非零正整数a,b，设a≥b＞0，令r0=a,r1=b，如果我们做带余除法得到rj=rj+1qj+1+rj+2,且rj+1＞rj+2＞0，

j=0,1,2,…,n2且有rn+1=0，那么gcd(a,b)=rn。证

对任意a=bq+r,

a,b,q,r为整数，令d=gcd(a,b),e=gcd(b,r),则d|a,d|b,e|b,e|r，由a=bq+r得到e|a，即e是a，b的因子，故e|d；由

r=abq得到d|r，即d是r,b的因子，故d|e。因此gcd(a,b)=gcd(b,r)对于带余除法得到的一系列rj=rj+1qj+1+rj+2，rj+1＞rj+2＞0，由于r1=b是固定的，而且r1>r2>…>rn>rn+1，所以最终一定会有一个余数为零，假设为rn+1=0。于是

gcd(a,b)=gcd(r0,r1)=gcd(r1,r2)=gcd(r2,r3)=…=gcd(rn,0)=rn故gcd(a,b)=rn。

4.1整除和素数离散数学第4章初等数论

4.1.2最大公因子例4.11

用欧几里得算法求gcd(126,27)，以及x，y，使得126x

27y=gcd(126,27)。解用辗转相除法依次得到：126=4*27+18，27=1*18+9，18=2*9，

所以gcd(126,27)=9倒推求整数x，y：

9=271*18=271*(1264*27)=1*126+5*27因此，x=1，y=5，满足126x27y=gcd(126,27)。4.1整除和素数离散数学第4章初等数论

4.1.3算术基本定理定理4.7

任何大于1的整数a都至少有一个素因子。证

若a是素数，则定理是显然的。若a不是素数，那么它有两个以上的正的非平凡因子，设它们是d1,d2,…,dk

。不妨设d1是其中最小的。若d1不是素数，则存在e1>1，e2>1，使得d1=e1e2，因此，e1和e2也是a的正的非平凡约数。这与d1的最小性矛盾。因此，d1是素数。证毕。4.1整除和素数离散数学第4章初等数论

4.1.3算术基本定理定理4.8

任何大于1的正整数n，或为一质数，或可以写成若干素数的积，即有pi（1

i

m）是素数，使得

n=p1p2pm

(4-2)证

（回忆练习3.2之8）当n=2时，结论显然成立。假设对于2nk，式(4-2)成立，证明式(4-2)对于n=k1也成立，从而由归纳法推出式(4-2)对任何大于1的整数n成立。如果k1是素数，式(4-2)显然成立。如果k1是合数，则存在素数p与整数d，使得k1=pd。由于2dk，由归纳假定知存在素数q1,q2,,qi，使得

d=q1q2qi从而k1=pq1q2qi。4.1整除和素数离散数学第4章初等数论

4.1.3算术基本定理定理4.9(算术基本定理)

任何大于1的整数n可以唯一地表示成

(4-3)其中p1,p2,,pk是素数，p1<p2<<pk，1,2,,k是正整数。证

由定理4.8，我们只需证明表示式(4-3)的唯一性。假设pi（1ik）与qj（1jl）都是素数，

p1p2pk，q1q2

ql

(4-4)并且

n=p1p2pk=q1q2ql(4-5)则必有某个qj（1jl），使得p1qj，所以p1=qj，又有某个pi（1ik），使得q1pi，所以q1=pi。于是，由式(4-4)可知p1=q1，从而由式(4-5)得到p2pk=q2ql

重复上述这一过程，得到k=l，pi=qi

，1ik。4.1整除和素数离散数学第4章初等数论

4.1.3算术基本定理定义4.6

若p1,p2,,pk是素数，p1<p2<<pk，1,2,,k是正整数，那么，称是n的素幂分解式。4.1整除和素数定理4.10

任何大于1的合数a必有一个不超过的素约数。证

由定理4.8，合数a可以表示成若干个素数之积，假设a=da，其中d>1是最小的素约数，显然

d2

a。证毕。例4.14

对合数18，有不超过的素约数3。

离散数学第4章初等数论

4.1.4素数的性质定理4.11

素数有无限多个。证

假设只有k个素数，设它们是p1,p2,…,pk

。记

M=p1p2…pk

1。由定理4.8可知，M有素因数p，我们要说明p

pi

，1

i

k，从而得出矛盾。事实上，若有某个i，1

i

k，使得p=pi

，则由

pM

，M=p1p2…pk

1推出p1，这是不可能的。因此在p1,p2,…,pk之外还有一个素数p，这与假设是矛盾的。因此，素数不可能是有限个。4.1整除和素数离散数学第4章初等数论

4.1.4素数的性质定义4.7

对于正实数x，以(x)表示不超过x的素数个数。对于正整数m，以pm表示第m个素数。例如，(15)=6，(10.4)=4，(50)=15。p1=2，p4=7，p6=13。定理4.12

对于正整数n

，m

（1）

(pm)=m

。（2）

(n)log2n；（3）

pm

22m

。4.1整除和素数离散数学第4章初等数论

定理4.12（1）(pm)=m

。（2）

(n)log2n；（3）

pm

22m

证.（1）据定义立得。（2）设n是大于1的正整数。由算术基本定理，对于任意的整数k，1

kn，都有整数a和b，使得k=a2b，其中整数b不能被任何大于1的整数的平方整除。现在，我们来看k=a2b，1kn,即1a2bn成立的整数a,b有多少对。首先，整数a的个数；其次，由于b

n并且不含有平方因数，所以，整数b的因数只可能是不超过n的不同的素数的乘积，因此，整数b的个数

2(n)。这样，使得式(4-7)成立的整数a和b至多是2(n)对，故n

2(n)，即(n)log2n。（3）以pm表示第m个素数，在结论(1)中取n=pm，我们得到(pm)=m

log2pm，由此即可得到2mlog2pm，故结论（3）真。4.1整除和素数4.1.4素数的性质离散数学第4章初等数论

4.1.4素数的性质定理4.13(素数定理)

对任意正实数x，我们有

(x)，(x)，此处logx是以e为底的x的对数，

表示“与为同阶无穷大”。4.1整除和素数离散数学第4章初等数论

4.1.4素数的性质推论4.13.1

以pn表示第n个素数，则

pn

nlogn（n）。证

由定理4.13，当n

时，有

n(4-8)因此，当n

时，有

nlogpn

pn，logn

log(logpn)

logpn，logn

logpn

nlogn

nlogpn由上式与式(4-8)得pn

nlogn(n)。证毕。4.1整除和素数离散数学第4章初等数论

Eratosthenes筛法按以下步骤进行删除：(ⅰ)删去1，剩下的后面的第一个数是2，2是素数；(ⅱ)删去2后面的被2整除的数，剩下的2后面的第一个数是3，3是素数；(ⅲ)再删去3后面的被3整除的数，剩下的3后面的第一个数是5，5是素数；(ⅳ)再删去5后面的被5整除的数，剩下的5后面的第一个数是7，7是素数；

……照以上步骤可以依次得到素数2,3,5,7,11,…。4.1整除和素数离散数学第4章初等数论

Eratosthenes筛法例4.15

写出不超过100的所有的素数。解将不超过100的正整数排列如下然后进行必要的删除：

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991004.1整除和素数离散数学第4章初等数论

Eratosthenes筛法

例4.15

写出不超过100的所有的素数。解将不超过100的正整数排列如下然后进行必要的删除：235791113151719212325272931333537394143454749515355575961636567697173757779818385878991939597994.1整除和素数离散数学第4章初等数论

Eratosthenes筛法例4.15

写出不超过100的所有的素数。解将不超过100的正整数排列如下然后进行必要的删除：23571113171923252931353741434749535559616567717377798385899195974.1整除和素数离散数学第4章初等数论

Eratosthenes筛法例4.15

写出不超过100的所有的素数。解将不超过100的正整数排列如下然后进行必要的删除：23571113171923293137414347495359616771737779838991974.1整除和素数离散数学第4章初等数论

Eratosthenes筛法

例4.15

写出不超过100的所有的素数。解将不超过100的正整数排列如下然后进行必要的删除：23571113171923293137414347535961677173798389974.1整除和素数离散数学第4章初等数论

4.1.4素数的性质证明：存在无穷多个正整数a，使得

n4

a(n=1,2,3,…)都是合数。解取a=4k4(k是大于的1正整数)，那么对于任意的nN，有n44k4=(n22k2)24n2k2=(n22k22nk)(n22k22nk)因为n22k22nk=(nk)2k2

k2，所以，对于任意的k=2,3,…以及任意的nN，(n2

2k2

2nk)h和(n2

2k2

2nk)都是n4

4k4

的大于1的因子，故n44k4是合数。4.1整除和素数离散数学第4章初等数论

4.1.4素数的性质例4.17

求证：若a>1，an

1是素数，则a=2，并且n是素数。证

若a>2，则由

an

1=(a

1)(an

1

an

2

…1)可知an

1是合数。因此别无选择，a=2。若n是合数，则n=xy，x>1，y>1，于是由2xy

1=(2x

1)(2x(y1)

2x(y

2)

…1)以及2x

1>1可知2n

1是合数，与前提“an

1是素数”矛盾。因此，2n

1是素数时，n必是素数。4.1整除和素数离散数学第4章初等数论

4.1.5实数的取整[x]与取另{x}定义4.8

实数的取整运算[x]：取不超过实数x的最大整数，[x]为实数x的整数部分。取另运算{x}：{x}=x－[x]，{x}是实数x的小数部分。显然0≤{x}<1且x=[x]+{x}例4.18[3]=3，[－4]=－4，[－π]=－4{3}=0，{－4}=0，

{1.41}=0.41，{－3.14}=0.864.1整除和素数离散数学第4章初等数论

4.1.5实数的取整[x]与取另{x}定理4.14

实数的取整、取另运算[x]与{x}有下列性质（1）取整[x]是不减函数。即x≤y时，[x]≤[y]。（2）等式[x+m]=[x]+m,当且仅当m为整数时成立。（3）对任意实数x,y，[x]+[y]≤[x+y]。（4）设n为整数，x为实数，则=[x]。（5）设m,n为正整数，且m<n，在1，2，…，(n－1),n中,m的倍数有[]个。（6）若b是正整数，那么对于任意的整数a，有4.1整除和素数离散数学第4章初等数论

4.1.5实数的取整[x]与取另{x}定理4.15

设n是正整数，n!=是n!的标准分解式，pi为

素数，i=1,2,,k,则pi的幂指数

i

=(4-9)证

对于任意固定的素数p(p=pi,i=1,2,…,k)，在1,2,,n中有p为其因子的数一共有[n/p]个，这样可从中提取[n/p]个因子p；将这[n/p]个数同除因子p，则依然包含有因子p的数的个数等于1,2,

,n中有p2为其因子的数的个数，一共有[n/p2]个，这样又可在1,2,,n中提取[n/p2]个因子p，依次类推，我们可不断提取得到[n/p3]个因子p，[n/p4]个因子p，…。故n!中p(p=pi

,i=1,2,…,k)的指数应为=[n/p]+[n/p2]+[n/p3]+…=4.1整除和素数离散数学第4章初等数论

4.1.5实数的取整[x]与取另{x}例4.19

求最大的正整数k，使得10k199!解

10的因子为5和2，由于199!中以2为因子的数比以5为因子的数多，所以我们得到了199!中5的因子数也便得到了199!中10的因子数。由定理4.16，199!的标准分解式中所含的5的幂指数是因此，10的因子数为47，故所求的最大整数k=47。4.1整除和素数离散数学第4章初等数论

4.1.5实数的取整[x]与取另{x}例4.20

求方程的整数解。解

因为，所以，解该不等式得1＜x≤4。据方程，且x为整数，故方程的解为x=2，3，4。4.1整除和素数离散数学第4章初等数论

4.2.1同余的基本性质定义4.9

给定正整数m，如果整数a与b之差能被m整除，则称a与

b是模m同余，或称a与b同余，模为m，记为

a

b(modm)此时也称b是a对模m的同余。如果整数a与b之差不能被m整除，则称a与b对于模m不同余，或称a与b不同余，模为m，记为

ab(modm)。4.2同余离散数学第4章初等数论

4.2.1同余的基本性质定理4.16

对于整数a,b,c,正整数m，模m同余具有下面的性质：（1）a

a(modm)； （2）a

b(modm)则b

a(modm)；（3）a

b，b

c(modm)则a

c(modm)；（4）a

b(modm)充分必要条件是存在整数k使a=b+km；（5）a

b(modm)充分必要条件是a,b除m后有相同的余数。4.2同余离散数学第4章初等数论

4.2.1同余的基本性质定理4.17

设a,b,c,d是整数，若a

b(modm)，c

d(modm)，则：（1）

a

c

b

d(modm)，a

c

b

d(modm)；（2）

ac

bd

(modm)。定理4.18

设ai，bi(0

i

n)以及x，y都是整数，并且

x

y(modm)，ai

bi(modm)，0

i

n，则(modm)。4.2同余离散数学第4章初等数论

4.2.1同余的基本性质定理4.19

若ac

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

则

a

b(modm/d)。证

由ac

bc(modm)，得到m|c(ab)，故存在k使得

c(ab)=km。再由(c,m)=d得到(c/d)(ab)=km/d，又因为(c/d,m/d)=1，所以m/d|ab，即

a

b(modm/d)。推论4.19.1

ac

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

a

b(modm)4.2同余离散数学第4章初等数论

4.2.1同余的基本性质例4.24

设p是素数，a是整数，则由a2

1(mod

p)可以推出

a

1(modp)或a

1(modp)。解由a2

1(modp)可知pa2

1=(a

1)(a

1)，由于p是素数，故必是

p(a

1)或p(a

1)，即a

1(modp)或a

1(modp)。4.2同余离散数学第4章初等数论

4.2.1同余的基本性质例4.25

计算2644（mod645）解对于计算这类高次幂的同余，如果我们先计算2644则将得到一个

194位的十进制数，显然不合理。因此先采用逐个平方法计算22(mod645)，22

4(mod645)，24

16(mod645)，28

256(mod645)，216

391(mod645)，23216(mod645)，264

256(mod645)，2128

391(mod645)，2256

16(mod645)，2512

256(mod645)；再利用644的二进制数为1010000100，即644=512+128+4，得到26442512+128+42512212824256×391×1616015361(mod645)4.2同余离散数学第4章初等数论

4.2.2剩余系定义4.10

给定正整数m，对于每个整数i，0i

m1，称集合

Ri(m)={n︱n

i(modm)，nI}。是模m的一个剩余类（或同余类）。4.2同余例4.26

模5的五个剩余类是

R0(5)={,10,5,0,5,10,}

R1(5)={,9,4,1,6,11,}

R2(5)={,8,3,2,7,12,}

R3(5)={,7,2,3,8,13,}

R4(5)={,6,1,4,9,14,}离散数学第4章初等数论

4.2.2剩余系定义4.11

设R是模m的一个剩余类，若有aR，使得(a,m)=1，则称R是模m的一个简化剩余类。若R是模m的简化剩余类，则R中的每个整数都与m互素。显然，模m的简化剩余类就是少于或等于m的数中与m互质的正整数的数目，称为

欧拉函数，记作(m)。例4.27

模5的简化剩余类有四个R1(5)，R2(5)，R3(5)，R4(5)。模4的简化剩余类只有两个：

R1(4)={,7,3,1,5,9,}，

R3(4)={,5,1,3,7,11,}。4.2同余离散数学第4章初等数论

4.2.2剩余系定义4.12

设m是正整数，从模m的每一个剩余类中各取一个数xi(0

i

m

1)，构成集合{x0,x1,,xm1}，称为模m的一个

完全剩余系(或简称为完全系)，称{0,1,2,,m

1}是模m

的最小非负完全剩余系。定义4.13

对于正整数m，从模m的每个简化剩余类中各取一个数

xi，构成一个集合{x1,x2,,x(m)}，称为模m的一个简化剩余系(或简称为简化系)。4.2同余离散数学第4章初等数论

4.2.2剩余系由于xi的选取是任意的，所以模m的完全剩余系有无穷多个，模m的简化剩余系也有无穷多个。在模m的简化剩余系中，每个元素与m互素。例4.28

{0,6,7,13,24}模5的一个完全剩余系

{0,1,2,3,4}模5的最小非负完全剩余系{6,7,13,24}模5的一个简化剩余系

{9,5,3,1}模8的简化剩余系

{1,3,5,7}模8的简化剩余系（最小非负简化剩余系）

4.2同余离散数学第4章初等数论

4.2.2剩余系定理4.20

如果{r1,r2,…,rm}是完全剩余系，(a,m)=1，则{ar1+b,ar2+b,…,arm+b}也是完全剩余系。证

首先,ar1+b,ar2+b,…,arm+b中没有两个数模m同余，因为若存在两个数模m同余，不妨设为ari+b

arj+b(modm)，则ari

arj

(mod

m)由(a,m)=1有ri

rj(modm)，与{r1,r2,…,rm}是完全剩余系矛盾。如果{ar1+b,ar2+b,…,arm+b}不是完全剩余系，则至少有一个数x不同余这个集合中的任何一个数，因此这个集合中没有数与x模m同余。这样，ar1+b,ar2+b,…,arm+b分别除以m

，至多只能产生m1个不同的余数，由鸽笼原理，它们中至少有两个数模m同余，与证明的前半部分矛盾。故{ar1+b,ar2+b,…,arm+b}是完全剩余系。4.2同余离散数学第4章初等数论

4.2.3一次同余方程定义4.14

称ax

b(modm)是关于未知数x的模m一次同余方程，本书中简称为模m同余方程。设x0是整数，当x=x0时式ax

b(modm)成立，则称x0是同余方程的解。凡对于模m同余的解，被视为同一个解。同余方程的解的个数是指它的关于模m互不同余的所有解的个数，亦即在模m的一个完全剩余系中的解的个数。4.2同余定理4.21

设a,b是整数，a0(modm)。则同余方程

ax

b(modm)有解的充要条件是(a,m)b。若有解，则恰有(a,m)=d个解。离散数学第4章初等数论

4.2.3一次同余方程例4.30

求9x12(mod15)的解。解

因为(9,15)=3，3|12，因此本方程有解，且有3个不同余解。首先求出1个特殊解，然后加上15/3=5的倍数求出其余解。先用辗转相除法来求(9,15)

15=1*9+6，9=1*6+3，6=3*2，得到(9,15)=3。由倒退得3=91*(151*9)=2*915。由最大公因子的求法知存在x、y使得9x15y=3，因而存在x、y使得9x15y=12。由于12=8*94*15，可求得x0=8是其1个解，然后在xx0+(15/3)t(modm)中分别取t=1，2，进而得x1=8+5=13，x2(8+10)(mod15)，即x2=34.2同余离散数学第4章初等数论

4.2.3一次同余方程定义4.15

给定正整数m和整数a，(a,m)=1，称ax1(modm)的最小正整数解为整数a的模m的逆。例4.31

方程5x1(mod9)的解为x2(mod9)，2是5的模9的逆，5*21(mod9)。显然，5也是2的模9的逆。例4.32

利用模的逆求同余方程7x22(mod31)的解。解

因为(7,31)=1，所以只有一个不同余的解。由7*91(mod31)，得到9是7的模31的逆。在7x22(mod31)两边乘9，有7*9x22*9(mod31)，因为7*91(mod31)，故其唯一不同余解是x22*9(mod31)，因此x19812(mod31)为原方程的解。4.2同余离散数学第4章初等数论

4.2.4同余式组定义4.16

同余方程组（4-10）称为同余式组，满足每个同余方程的x称为同余式组的解。4.2同余离散数学第4章初等数论

4.2.4同余式组定理4.22

设m1,m2,,mk是两两互素的正整数，那么同余式组(4-10)有唯一的以M=m1m2mk为模的解。证

首先，构造一个联立解，该解满足同余式组(1)的每个同余方程。记Mi=M/mi,1i

k，由于m1,m2,,mk两两互素，显然(Mi,mi)=1。由定理8，我们可求出Mi的模mi的逆yi，Miyi1(modmi)。令x=a1M1y1+a2M2y2+…+akMkyk。对任意的1ik，因为i≠j

时mi|Mj，所以有Mjyj0(mod

mi)，因此有xaiMiyiai(mod

mi)，所以x就是所有同余方程的公共解。4.2同余离散数学第4章初等数论

4.2.4同余式组定理4.22

设m1,m2,,mk是两两互素的正整数，那么同余式组（4-10）有唯一的以M=m1m2mk为模的解。证

其次我们证明任何两个解模M同余，假设x0，x1是任意两个同余式组的解，因此对任何1ik，x0x1

ai(mod

mi)，所以mi|(x0-x1)，因为mi两两互素，所以M|(x0-x1),即xx0(mod

M)，故同余式组(1)的模M不同余的解是唯一的。4.2同余离散数学第4章初等数论

4.2.4同余式组例4.33

求整数n，它被3，5，7除的余数分别是1，2，3。解

设n是以下同余方程组的解

根据定理4.22，取m1=3，m2=5，m3=7，M=357=105，因而,M