第5章初 等 数 论[*4/5]5.1整除关系与素数习题5.1及参考答案
1. 分别讨论下述集合上的整除关系具有何种性质.
(1) 整数集Z.
(2) 自然数集N.
(3) 正整数n的正因数集Dn.
解 (1) 整数集Z上的整除关系具有自反性和传递性.
(2) 自然数集N上的整除关系具有自反性、反对称性和传递性.
(3) 正整数n的正因数集Dn上的整除关系与n的值有关.当n≥2时,该集合上的整除关系具有自反性、反对称性和传递性；当n=1时,该集合上的整除关系具有自反性、对称性、反对称性和传递性.
2. 写出35的所有因数集合及所有正因数集合D35.
解35的所有因数集合为{-35，-7，-5，-1，1，5，7，35}.D35 ={1，5，7，35}.
3. 证明： 若关于λ的整系数方程anλn+an－1λn－1+…+a1λ+a0=0(n∈Z+)有有理数根rs，其中gcd(r，s)=1，则r|a0且s|an.
证根据题意，有anrsn+an－1rsn－1+…+a1rs+a0=0去掉分母，得anrn+an－1srn－1+…+a1sn－1r+a0sn=0于是a0sn=－anrn－an－1srn－1－…－a1sn－1r,进而r|a0sn.类似地，有s|anrn.由于gcd(r，s)=1，因而r|a0且s|an.
4. 证明： 若a为正奇数，则8|a2-1.
证设a=2k+1，则a2－1=(a－1)(a+1)=4k(k+1).由于k和k+1中必有一个偶数，故有8|a2-1.
5.令m=8，分别求出下述n除以m的商和余数.
(1) n=7.
(2) n=-7.
(3) n=58.
(4) n=-48.
解(1) 7=0×8+7.
(2) －7=(－1)×8+1.
(3) 58=7×8+2.
(4) －49=(－7)×8+7.
6. 分别计算以下各式.
(1) 2019 mod 19.
(2) -2019 mod 19.
解(1) 因为 2019=106×19+5，所以2019 mod 19=5.
(2) 因为-2019=(-107)×19+14，所以-2019 mod 19=14.
7. 计算12345的八进制数.
解因为12345=1543×8+1，1543=192×8+7，192=24×8+0，24=3×8+0，3=0×8+3，所以12345=(30071)8.
8. 分别计算以下各式.
(1) φ（6）.
(2) φ（8）.
(3) φ(10).
解(1) φ(6)=2.
(2) φ(8)=4.
(3) φ(10)=8.
9. 证明：存在无限多个素数且它们是可列的.
证假设只有有限个素数，分别为p1,p2,…,pk.令n=p1p2…pk+1∈N.根据素因数分解定理，必存在1≤i≤k，使得pi|n，进而pi|1，不可能.结论得证.
因为自然数是可列的，由上面的结论可知，素数是可列的(但无法用列举法给出).
10. 对2015进行素因数分解.
解 容易知道，5是2015的素因数，即2015=5×403.若403是合数，则其必有一个小于或等于403（<21）的素因数，即2，3，5，7，11，13，17，19.易验证13是403的素因数，即403=13×31.显然，31是素数，故2015的素因数分解为2015=5×13×3111. 计算gcd(2035，2019)，并给出贝祖系数s和t，使得gcd(2035,2019)=2035s+2019t.
解因为2035=1×2019+16，2019=126×16+3，16=5×3+1，3=3×1+0，所以gcd(2015，2019)=1.由于 1=16-5×3，3=2019-126×16，16=2035-1×2019，于是1=16-5× (2019-126×16)=631× 16-5×2019=631×(2035-1×2019)-5×2019=631×2035-636×2019.所以s=631，t=-636.
12. 证明： 对于任意不全为0的整数m和n，若存在整数s和t使得gcd(n，m)=ns+mt，则gcd(s，t)=1.
证设gcd(m，n)=d，gcd(s，t)=k，则存在n′,m′,s′,t′∈Z，使得m=dm′,n=dn′，s=ks′,t=kt′，进而d=ns+mt=dk(n′s′+m′t′)，于是dk|d，进而k=1，即gcd(s，t)=1.
13. 证明：若gcd(m,n1)=1且gcd(m,n2)=1，则gcd(m,n1n2)=1.
证因为gcd(m,n1)=1，存在整数s1,t1使得s1m+t1n1=1.类似地，因为gcd(m,n2)=1，存在整数s2,t2使得s2m+t2n2=1.于是，有(s1m+t1n1)(s2m+t2n2)=1，进而(s1s2m+s1t2n2+s2t1n1)m+t1t2·n1n2=1因此，gcd(m,n1n2)=1.
14. 证明: 在偏序集(Z+,|)中，任意两个元素均存在下确界，其中|是整除关系.
证对于任意x,y∈Z+，根据公因数的定义知，gcd(x，y)|x且gcd(x，y)|y，所以gcd(x，y)是{x,y}的下界.假定z是{x,y}的下界，则z|x且z|y，即z是x与y的公因数.根据欧几里得算法知，存在整数s和t使得gcd(x,y)=xs+yt，于是z| gcd(x，y)，即gcd(x，y)是{x,y}的下确界.
5.2模同余关系
习题5.2及参考答案
1. 下述结论是否成立?
(1) 2019≡1983(mod 18).
(2) 362≡-1(mod 15) .
解(1) 成立，因为2019-1983=38=2×18.
(2) 不成立，因为362－(－1)=1297=86×15+7，不是15的倍数.
2. 设p是素数.证明： 对于任意整数n，若n2≡1（mod p)，则n≡1(mod p)或n≡－1(mod p).
证由已知n2≡1(mod p)，有p|n2－1，即p|(n－1)(n+1).因为p是素数，于是p|n－1或p|n+1，因而n≡1(mod p)或n≡－1(mod p).
3. 设m是正整数，对于任意整数x 和y，判断下列结论是否成立，并给出理由.
(1) 若x2≡y2(mod m)，则x≡y(mod m)或x≡－y(mod m).
(2) 若x2≡y2(mod m2)，则x≡y(mod m)或x≡－y(mod m).
解(1) 不成立.例如，52≡32(mod 16)，但5≡3(mod 16)或5≡－3(mod 16)均不成立.
(2) 不成立.例如，172≡82(mod 152)，但17≡8(mod 15)或17≡－8(mod 15)均不成立.
4. 分别写出Z5={0，1，2，3，4}关于模5加法运算+5和模5乘法运算·5的运算表.
解Z5关于模5加法运算+5和模5乘法运算·5的运算表分别如表51和表52所示.表51
+501234001234112340223401334012440123表52
·50123400000010123420241330 31424043215. 证明： 若gcd(m，n)=1，则a≡b(mod m)当且仅当an≡bn(mod m).
证( )因为a≡b(mod m)，于是m|a－b,进而m|(a－b)n，所以an≡bn(mod m).
(  )因为an≡bn(mod m)，于是m|(a－b)n.因为gcd(m，n)=1，所以m|a－b，即a≡b(mod m).
6. 计算下列幂模.
(1) 22019 mod 7.
(2) 72019 mod 11.
解(1) 由于gcd(2,7)=1，根据费马小定理，有26≡1(mod 7).因为2019=6×336+3，于是22019=26×336+3=26336×23≡1336×23≡1(mod 7)，即22019 mod 7=1.
(2) 由于gcd(7,11)=1，根据费马小定理，有710≡1(mod 11).因为2019=10×201+9，于是72019=710×201+9=（710）201×79≡1201×79≡79(mod 11).又因为72=49≡5(mod 11)
74=722≡52≡3(mod 11)
78=742≡32≡9(mod 11)因而，79=78×7≡9×7≡8(mod 11)，即72019 mod 11=8.
7. 证明:
(1) 15是7模26的乘法逆元，并求解线性同余方程15x≡1(mod 26).
(2) 937是13模2436的乘法逆元，并求解线性同余方程13x≡1(mod 2436).
解(1) 由于15×7≡1(mod 26)，所以15是7模26的乘法逆元.由已知15x≡1(mod 26)，得到15×7x≡7(mod 26)，进而x≡7(mod 26)=7.
(2) 由于937×13≡1(mod 2436)，所以937是13模2436的乘法逆元.由已知13x≡1(mod 2436)，得到937×13x≡937(mod 2436)，进而x≡937(mod 2436)=937.
8. 求解下列线性同余方程.
(1) 8x≡2(mod 6).
(2) 4x≡－1(mod 6).
(3) 3x≡4(mod 7).
(4) 256x≡158(mod 337).
解(1) 由于gcd(8，6)=2|2，所以8x≡2(mod 6)有两个解.容易验证，Z6={0，1，2，3，4，5}中的1和4是其解.
(2) 由于gcd(4，6)=2  -1，所以4x≡-1(mod  6)没有解.
(3) 由于gcd(3，7)=1|2，所以3x≡4(mod 7)只有一个解.容易验证，Z7={0，1，2，3，4，5，6}中的6是其解.
(4)由于gcd(256，337)=1|158，所以256x≡158(mod 337)只有一个解.由欧几里得算法知337=1×256+81
256=3×81+13
81=6×13+3
13=4×3+1
3=3×1+0进而1=13－4×3
3=81－6×13
13=256－3×81
81=337－1×256于是，有1=13－4×3=13－481－6×13
=25×13－4×81
=25×(256－3×81)－4×81
=25×256－79×81
=25×256－79(337－1×256)
=104×256－79×337进而s=104.由于k=b/gcd(a,m)=158/gcd(256,337)=158，故x=ks mod 337=158×104 mod 337=2569. 利用中国剩余定理求解下列线性同余方程组.x≡1(mod 5)
x≡5(mod 6)
x≡4(mod 7)
x≡10(mod 11)解令m1=5，m2=6，m3=7，m4=11,于是m=m1m2m3m4=5×6×7×11=2310，进而M1=mm1=462，M2=mm2=385，M3=mm3=330，M4=mm4=210根据Mixi≡1(mod mi),i=1,2,3,4，分别求得x1=3，x2=1，x3=1，x4=1.由于a1=1，a2=5，a3=4，a4=10，取x=a1M1x1+a2M2x2+a3M3x3+a4M4x4=6731则所给线性同余方程组的解为6731 mod 2310=2111，所有解为x=2111+2310k，k∈Z.
10. 证明(Wilson定理): 设p > 1，则p是素数的充要条件是(p-1)!≡-1(mod  p).
证( )当p=2，3时，结论显然成立.下面设p>3并考虑集合S={2，3，…，p-2}.任取a∈S，则gcd(a，p)=1，于是存在整数x和y使得ax+py=1，进而ax≡1(mod p).令b≡x(mod  p)，由于a∈S，于是b≠1，p-1，因此b∈S且ab≡1(mod  p).
下面证明a≠b.若a=b，则a2≡ 1(mod  p)，进而p|(a-1)(a+1).因为p是素数，于是p|(a-1)或p|(a+1)，这都是不可能的.
由上面的讨论知，S中的数可分成(p-3)/2对，每对数a和b满足ab≡1(mod  p).因此2×3×…×(p－2)≡1(mod p)，进而(p-1)!≡-1(mod  p).
(  )若p=ab(1<a，b<p)，由于1<a<p，显然a|(p-1)!.根据(p-1)!≡-1(mod  p)，知p|(p-1)!+1，由p=ab可得出a|(p-1)!+1，于是a|((p－1)!+1)－(p－1)!即a|1，不可能.
5.3RSA密码算法
习题5.3及参考答案
1. 说明: 若已知n及φ(n)，其中n是两个素数p和q的乘积，则容易求出p和q.
解由于n=pq，φ(n)=(p-1)(q-1)=pq-(p+q)+1，于是p+q=n-φ(n)+1，这时p和q是一元二次方程x2-(n-φ(n)+1)x+n=0的两个根，已知n及φ(n)即可求出p和q.
2. 用00~25分别表示A~Z，每个字母用两位数字表示，在RSA密码算法中，取(n，e)=(35，7).
(1) 把STOP加密.
(2) 把32 14 32解密.
解(1) STOP表示为18 19 14 15.由于7=(111)2=22+2+1，使用逐次平方法有182≡9(mod 35)，184≡92(mod 35)≡11(mod 35)所以187=184×182×18≡11×9×18(mod 35)≡32(mod 35).类似地，有197≡19(mod 35)，147≡14(mod 35)，157≡15(mod 35).因此，使用RSA密码算法将18 19 14 15（即STOP）加密为32 19 14 15.
(2) 显然，7×7≡1(mod  24)，于是d=7=(111)2=22+2+1，使用逐次平方法有327 ≡18(mod 35)，147≡14(mod 35).使用RSA密码算法将32 14 32解密为 18 14 18，即SOS.
自 测 题 5
一、 填空题(每小题3分，共15分)
1. 整数集合Z关于整数的加法运算+和乘法运算·都是()运算.
2. 若整数m|1，则m=().
3. -19(mod  7)=().
4. 设p和q是素数，则欧拉函数φ(pq)=().
5. 线性同余方程3x≡5(mod  8) 的解为x=( ).
二、 单选题(每小题3分，共15分)
1. 对于正整数n，用φ(n)表示小于或等于n且与n互素的正整数个数，则φ(12)=().

A. 1  B. 2C. 3D. 4
2. 集合A={2n|n∈N}上的整除关系|是()关系.
A. 偏序  B. 线性序 C. 良序D. 等价
3. 下列各式中，()为真.
A. 446≡278(mod  7)B.  445≡536(mod  18)
C.  383≡126(mod  15)  D.  2019≡1882(mod  17)
4. 设p是素数，则Zp={0，1，2，…，p-1}关于模p的乘法运算·p ().
A. 每个元素都有逆元 B.  每个元素都没有逆元
C.  每个非零元素都有逆元   D.  每个非零元素都没有逆元
5. 线性同余方程9x≡12(mod  21)的所有解为().
A.  5，12 B.  6，13，20C.  7，13，20D.  13，20
三、 判断题(每小题3分，共15分)
1. 对于整除关系|，有0|0.()
2. 对任意整数m和n，若m|n且n|m，则m=n.()
3. 对任意整数m，n和k，若gcd(m，n)=1，m|k且n|k，则mn|k.()
4. 整数集Z上的模m同余关系≡m是等价关系.()
5. 线性同余方程4x≡9(mod  14)无解.()
四、 (10分) 计算gcd(540，168)，并求出贝祖系数s和t,使得gcd(540，168)=540s+168t.
五、 (10分) 有多少对正整数(m，n)的最小公倍数lcm(m，n)=23×35?
六、 (10分) 证明：
(1) 设a，b和m是整数，其中m>1.若a≡b(mod  m)，则a2≡b2 (mod  m).
(2) 在任何1～200的103个不同整数中，必存在两个整数，其差恰为5.
七、 (10分) 利用中国剩余定理求解下列线性同余方程组.x≡1(mod 3)
x≡2(mod 5)
x≡3(mod 7)八、 (15分) 对于x∈N，令π(x)表示小于或等于x的素数个数.设A={x∈N|2≤x≤9}，定义A上的关系
={(x,x)|x∈A}∪{(x,y)∈A2|π(x)<π(y)}
(1) 验证(A，)是偏序集，并画出(A，)的哈斯图.
(2)  求出(A，)的所有极大元.
(3)  给出A的一个子集B的例子，使B存在最大元，但无最小元.
自测题5参考答案
一、 1. 封闭(或代数)
2. ±1
3. 2
4. (p-1)(q-1)
5.  7.
二、 1. D2. B3. A4. C5. B
三、 1. √2. ×3. √4. √5. √
四、 解根据带余除法有540=3×168+36
168=4×36+24
36=1×24+12
24=2×12+0于是，gcd(540，168)=12.
由上述等式可知12=36-1×24
24=168-4×36
36=540-3×168因此，gcd(540，168)=36-1×24=36-1×(168-4×36)=5×36-1×168=5×(540-3×168)-1×168=5×540-16×168，进而s=5且t=-16.
五、 解 显然，根据公倍数的定义知 m=2x3y且n=2r3s.由已知lcm(m，n)=2335可得max(x，r)=3 且max(y，s)=5，进而有7种可能的(x，r)，分别为(0，3)，(1，3)，(2，3)，(3，3)，(3，2)，(3，1)，(3，0).同理，有11种可能的(y，s).根据乘法原理，有7×11=77对满足条件的正整数(m，n).
六、 证(1) 因为a≡b(mod  m)，所以m|(a-b).而a2- b2=(a-b)(a+b)，于是m|(a2-b2)，即a2≡b2 (mod  m).
(2) 令hi是所取103个整数中的第i个，这时1≤hi≤200，1≤i≤103.取gi=hi+5，则6≤gi≤205，1≤i≤103.于是得到206个整数h1，h2，…，h103，g1，g2，…，g103，它们的取值范围都为1～205.因此，必有两个整数相同，显然一个是hi，另一个是gj.而gj=hj+5，所以hi=hj+5，这时hi-hj=5，结论得证.
七、 解令m1=3，m2=5，m3=7,于是m=m1m2m3=3×5×7=105，进而M1=mm1=35，M2=mm2=21，M3=mm3=15根据Mixi≡1(mod mi),i=1,2,3，分别求得x1=2，x2=1，x3=1.由于a1=1，a2=2，a3=3，取x=a1M1x1+a2M2x2+a3M3x3=52 mod 105则所给线性同余方程组的解为52 mod  105=52，所有解为x=52+105k，k∈Z.
八 、解 (1) 容易验证，（A，）是偏序集且COV(A)={(2,3),(2,4),(3,5),(3,6),(4,5),(4,6),（5,7）,(5,8),(5,9),(6,7),(6,8),（6,9）}.因而（A，）的哈斯图如图51所示.
图51
(2) 7，8，9.
(3) 取 B={3，4，5}.第6章图论[*4/5]6.1图的基本概念习题6.1及参考答案
1. 如图61所示，用1,2,3,4,5,6表示6个人，两个点之间的无向边表示对应的两个人认识，则图61所示的含义是什么? 能得出任意6个人中有3个人相互认识或相互不认识的结论吗?
解图61表示有1,2,3,4,5,6共6个人，其中1与3认识，1与4认识，2与3认识，2与5认识，3与6认识.
能得出任意6个人中有3个人相互认识或相互不认识的结论，其理由如下:
对于节点1来说，考虑其与节点2, 3, 4, 5, 6的关系，1至少与其中3个人认识或不认识.不妨假设1与其中2, 3, 4认识.在3, 4, 5中，若有2个人相互认识，则存在3个人相互认识，例如3与4认识，则1, 3, 4相互认识；若3, 4, 5中没有任何2个人相互认识，则3, 4, 5相互不认识.最后的结论如图62所示.
图61
图62
2. 在一次10周年同学会上，想统计所有人握手的次数之和，应该如何建立该问题的图模型？
解将每个同学作为一个节点，如果两个人握过一次手，就在相应的两个节点之间画一条无向边，由此得到一个无向图.
一个人握手的次数就是这个节点与其他节点所连接的边的条数，进而可得出所有人握手的次数之和.
3. 在一次联欢舞会上，要得出跳了奇数次舞的人数的规律，应该如何建立图模型？特别地，一个人单独跳一次舞该如何处理呢？某两人多次跳舞又如何处理?
解将联欢舞会上的每个人作为一个节点，若两个人跳过一次舞，则在相应的两个节点之间画一条无向边，由此得到一个无向图.一个人跳舞的次数就是这个人对应的节点与其他节点所连接的边的条数，进而可得出跳了奇数次舞的人数.
一个人单独跳了一次舞，可以认为自己跟自己跳，这时在该节点处有一个环；也可以认为联欢舞会上单独跳舞不计入跳舞次数.若两人多次跳舞，则在对应的节点之间出现平行边(多重边)，其重数是这两人跳舞的次数.
4. 任意n(n≥2)个人的组里必有两个人有相同个数的朋友，解答此问题的图模型该如何建立？
解将该组里的每个人作为一个节点，若两个人是朋友，则在相应的两个节点之间连一条无向边，由此得到一个无向图.
5. (3户3井问题)在一个地方有3户人家，并且有3口井供他们使用.由于土质和气候的关系，有的井中的水常常干枯，因此各户人家要到有水的井去打水.不久，这3户人家成了冤家，于是决定各自修一条路通往水井，打算使得他们在去水井的路上不会相遇.建立解决此问题的图模型.
解将3户人家分别作为3个节点，将3口井分别作为另外3个节点，若一户人家与一口井之间有一条路，则在相应的两个节点之间连一条无向边，这样就得到一个无向图.
6. （过河问题）某人挑一担菜并带一只狼和一只羊要从河的一岸到对岸去.由于船太小，只能带狼、菜、羊中的一种过河.由于明显的原因，当人不在场时，狼要吃羊，羊要吃菜.通过建立图模型给出此问题的答案.
解不妨认为过河的方向是从北岸到南岸，则在北岸可能出现的状态为24=16种，其中安全状态有下面10种: (人，狼，羊，菜)，(人，狼，羊)，(人，狼，菜)，(人，羊，菜)，(人，羊)，()，(菜)，(羊)，(狼)，(狼，菜)；不安全的状态有下面6种: (人)，(人，菜)，(人，狼)，(狼，羊，菜)，(狼，羊)，(羊，菜).
现将北岸的10种安全状态作为10个节点，而渡河的过程则是状态之间的转移，由此得到一个无向图，如图63所示.图63

从图63可以得出两种安全的渡河方案:
第1种: (人，狼，羊，菜)→ (狼，菜)→ (人，狼，菜)→ (狼)→ (人，狼，羊)→ (羊)→ (人，羊)→ ().
第2种: (人，狼，羊，菜)→ (狼，菜)→ (人，狼，菜)→ (菜)→ (人，羊，菜)→ (羊)→ (人，羊)→ ().
7. （分油问题）有3个油桶A,B,C，分别可装8kg、5kg和3kg油.假设A桶已经装满了油，在没有其他度量工具的情况下，要将油平分，通过建立图模型给出此问题的答案.
解用(B,C)表示B, C两个油桶的状态（即桶内装油的千克数），由于B=0,1,2,3,4,5且C=0,1,2,3，于是所有状态共6×4=24种.
现将这24种状态看作24个节点，当且仅当两种状态可以相互转换时，在两个节点之间连一条无向边，由此得到一个无向图，如图64所示.
图64
从图64中可以看出，有两种将油平分的方案:
第1种: (0,0) →(0,3) →(3,0) →(3,3) →(5,1) →(0,1) →(1,0) →(1,3) →(4,0).
第2种: (0,0) →(5,0) →(2,3) →(2,0) →(0,2) →(5,2) →(4,3) → (4,0).
8. 证明: 任何n阶完全图Kn的边数为n(n-1)/2.
证n阶简单图的边数为C2n=n(n-1)/2.