《离散数学刘任任第二版答案 习题19整数》由会员分享，可在线阅读，更多相关《离散数学刘任任第二版答案 习题19整数（10页珍藏版）》请在金锄头文库上搜索。
1、离散数学刘任任（第二版）习题答案第19章 整数1. 请推导出本节定理16.1.3中计算和的递推公式.kSkT分析：本题主要是考察矩阵的推导过程。解：由（P154）TV SUqqqkkkkk 121 101 101 101L ( )有比TV SUTV SUqq TVT q SUSkkkkkkkkkkkkkkkkk 11111111111 102 ( )较(2)式两端，可知US VTTq TV Sq SUkkkkkkkkkkkk 11111134 ( )( )由(3)有US VTkkkk 1212(5)由(4)和(5)得Sq SS Tq TTkkkkkkkk 12126 ( )由(3)可令SU T
2、V01017 ( )又由(1)有TV SUq111111 10 于是SU TVS Tq01011110 11 这样，对任意， 由(6)可求出 和 。k 2SkTk2. 求 1331 和 5709 的最大公因数，并表为它们的倍数之和.分析：本题主要是考察用辗转相除法来求两个数的最大公因数。解：用辗转相除法求最大公因数，逐次得出商及余数并计算和。今列表如下：SkTk0 1 2 3 4 5k385 176 33 11 0rk4 3 2 5 qk30 1 3 7 38 空 Sk1 4 13 30 163 空 Tk由上表知，最大公因数为 , 且有r411rST44 1 44 41570911331 38
3、5709163 1331 ()()3. 求证：任意奇数的平方减1必是8的倍数.分析：本题首先根据奇数的概念，然后进行变形即得。证明： 设为奇数。可令 于是 .nnkk211,.nkkk22221441()从而 nkkk k2214441 ().(1) 当时， 是8的倍数。k 1n210 (2) 当时，和必有一个是2的倍数, 因此，总是8的倍数。k 1kk 141k k()故结论成立。4. 试证：若一个数的奇数位上的数码之和与偶数位上的数码之和两者之差是 11 的倍数， 则此数也是 11 的倍数.分析：本题因为涉及到 11 以及整数，所以考虑 11 与 10 的关系，然后根据特殊推广到一般。证明
4、：设. 将10写成11与1之差。有aaaa a ann12210L11的倍数1；1011 1 11的倍数+1；1011 111211 1222 ()11的倍数1；1011 1113 113 11 13332 ()。的倍数. 从而1011 11111nn() () 11naaaa a ann12210L=aaaaann nn 0122 22 1110101010 L=的倍数1）的倍数+1）的倍数1)+aa0111(a211(a311(的倍数Lan 111 () 11n=11的倍数()()aaaaaa024135LL因此，若是11的倍数，则由性质2之(5)知, 是11()()aaaaaa02413
5、5LLa的倍数。5. 试证：将一个位数，任意颠倒其各位数字，所得之数与之差是 9 的倍数.nabac分析：本题和第 4 题类似，由于这里涉及到的是 9，所以考虑 9 与 10 的关系，然后由特殊 推广到一般。证明：设。将10写成9与1之和，有aaaa a ann12210L的倍数+110919 的倍数+1109192919222 ().的倍数+11091911nn()令任意颠倒其各位数字后所得的b为：abbbb bbnn122 1 0L=bbbbbnn nn 0122 22 1110101010 L于是， cabababababnnn()()()()0011222 111101010L=9的倍
6、数+1）9的倍数+1)()()(abab0011L()(abnn11=9的倍数 ()()aaabbbnn011011LL()ab11L9的倍数()abnn11=9的倍数9的倍数()ab11L()abnn11由性质2之（5）可知结论成立.6. 试证：任意整数，至少有一个质约数.1a分析：本题主要运用到质数的不可分解性。证明：不妨设是一个正整数。若本身就是质数，则结论成立，否则，设 a的最小真约aa数为，则就是质数，否则与的最小性矛盾。qqq7. 设是合数，是的最小正约数，试证：aqaaq 证明：根据数的分解即可。证明：由题意有。设，显然。于是, 即.q aaqa1aq1aq2qa8.试证：形如的
7、质数有无穷多个.14 n分析：用反证法，通过 构造一个新的数来找矛盾。证明：假设是不大于的所有质数。令41 414112nnnk, L41nannnpk 4 41 414114112()()()L易知，有不同于的质约数。显然的质约数是奇数，但奇数可以写成a411niki, La或。而. 所以的质约数中不能都是41n41n()()()41 414 41lmlmlm a的形状，其中必有形如的质约数。因此结论成立41n41n9. 证明：若，则.)( |322ba ba|3 ,|3分析：本题主要是根据定理 16.1.1 对数进行分解ba,，然后证明都是 0.amr bnsr s3303, sr,证明：
8、若，则。从而3不整除。故不妨设.令12a b,ab222 5 8 , ,()ab22a b, 3. 若或，则因amr bnsr s3303, r 0s 0且 , 故有.但由abmmrrnnss2222229696322ab322rsrs221 2 5 8 , , , 知，3不能整除. 矛盾。故必有, 即.rs22rs 033ab, 10. 设试证：与之间至少有一个质数.2nn! n分析：通过构造一个新的数，来说明该数有一个介于与之间的质因数。n! n证明：设不大于的质数为。令。易知，有异于的质因数，nppk1,Lqppk11Lqpip且，于是.故结论成立。pnnpqnn!111. 设质数，求证
9、：5p)24(mod12p分析：质数，可得一定是质数，然后根据 24=3、以及同余5ppgcd(3, 8) 1的性质可得。证明：因是质数，所以。即。从而,p 5p 0 mod 3)(p 1 (mod 3)p2211 () (mod 3)又由假设，可令。于是。 pkk212 ()pkkkk k222214414111 ()() (mod 8)再由 得 .gcd(3, 8) 1p21 (mod 24)12. 解同余方程。)97(mod135 x分析：本题注意是根据孙子定理求得。解。注意到35与97互质，按题2的方法，有 . 从而3635 13971. 故 .36351 (mod 97)x 3613
10、. 设为质数，求证：p。)(mod)(pbabappp证明：由二项式定理有()abaabbabppp pip iipppip C(mod 1114. 试证明：正整数是 3 的倍数必要而且只要的各位数码之和是 3 的倍数.nn分析：本题主要是根据来证明。101 (mod 3)证明： 设 . 因为, 所以naaaann 11 22 10101010L101 (mod 3)naaaa aaaannn 11 22 101210101010L L (mod 3)于是 必要且只要 .n 0 (mod 3)aaaan12100L (mod 3)15. 试找出正整数能被 7 整除的必要充分条件.n证明：本题的
11、难点在于找出一个对照数 1000，找到这个数其余就迎刃而解了。解。因为 。将写成千进制数10001 (mod 7)naaaaann i 0122 11100010001000001000L (mod 7), , naaaaaaaaaaaannn n 010001000100001000122 110121 10213(mod 7) (mod 7)(mod 7)(mod 7)LLLL()()(). 例如，()1001 i i in a (mod 7)n 8148638141000863, , 所以，814863是7的倍数。aaaa0101863814490, (mod 7)16. 解同余方程组)
12、7(mod2)5(mod3)4(mod1xxx分析：本题使用孙子定理来求解。解： 令。先分别解同余方程mmmmmm m123123457140,. m mcmiiii11 2 3 (mod ), ,即解 .35111123ccc (mod 4), 28 (mod 5), 20 (mod 7)解得 , 于是，所求解为ccc123121 (mod 4), (mod 5), (mod 7)xm mcaiii i 13 35112823201235 1684093()()(mod 140)17. 解同余方程组 )19(mod096)11(mod75 xx分析：本题与孙子定理有点不同，首先要先化成孙子定
13、理的形式，然后根据孙子定理 求解。解： 等价于解，先将（1）化为 57 69x x (mod 11)(mod 19) (1)xa xa 12(mod 11)(mod 19) 的形式。解, 得 , 57x (mod 11)x 8 (mod 11)解 ,得 .69x (mod 19)x 8 (mod 19)因此， .x 8 (mod 209)18. 求。)60(mod?131956分析：本题主要是根据欧拉定理来求解。解：由Euler定理，, 与互质. 这里，, 于是amm( )1 (mod )amm 602 2 3 5.( )()( ) ( ) ( ) (5)m 602231 1 2 48131313131131316911121119568 244 48244142444422 ()()()
