信息安全数学基础第一章-第1章习题解答.pptx

第一章习题解答 5 对于任给的正整数对于任给的正整数k，必有，必有k个连续的正整数都是个连续的正整数都是和数证明：设整数证明：设整数M=(k+1)!，则，则M+2=(k+1)!+2，M+3=(k+1)!+3，M+ (k+1)=(k+1)!+ (k+1)，是是k个连续的正整数，并且都是和数个连续的正整数，并且都是和数12 证明：形如证明：形如3k1，4k1，6k1的正整数必有的正整数必有同样形式的素因数同样形式的素因数证明：证形如证明：证形如3k1的正整数必含形如的正整数必含形如3k1的素因数的素因数 由于任一素数可以写成由于任一素数可以写成3n1, 3n 或或3n1的形式，的形式，而而 (3n1)(3n2)9n1n23(3n1n2), (3n11)(3n21)9n1n23n13n21 3(3n1n2n1n2)1,所以把形如所以把形如3n或或3n1的数相乘的积仍为的数相乘的积仍为3n形式的数形式的数12 证明：形如证明：形如3k1，4k1，6k1的正整数必有的正整数必有同样形式的素因数同样形式的素因数证明：又证明：又(3n1)(3n21)9n1n23n1 3(3n1n2n1), 即把形如即把形如3n与与3n1的数相乘的积仍为的数相乘的积仍为3n形式的数。

形式的数 因此，把形如因此，把形如3k1的整数分解成素数的乘积时，的整数分解成素数的乘积时，这些素因数不可能都是形如这些素因数不可能都是形如3n或或3n1的形式的素数，的形式的素数，一定含有一定含有3n1形式的素因数形式的素因数13 证明：形如证明：形如4k3的素数有无穷多个的素数有无穷多个证明：分两步证明证明：分两步证明 先证形如先证形如4k3的正整数必含形如的正整数必含形如4k3的素因数的素因数 由于任一奇素数只能写成由于任一奇素数只能写成4n1或或4n3的形式，而的形式，而 (4n11)(4n21)16n1n24n14n21 4(4n1n2n1n2)1,所以把形如所以把形如4n1的数相乘的积仍为的数相乘的积仍为4n1形式的数形式的数13 证明：形如证明：形如4k3的素数有无穷多个的素数有无穷多个证明：因此，把形如证明：因此，把形如4k3的整数分解成素数的乘积时，的整数分解成素数的乘积时，这些素因数不可能都是这些素因数不可能都是4n1的形式的素数，一定含有的形式的素数，一定含有4n3形式的素数形式的素数 其次，设其次，设 N 是任一正整数，并设是任一正整数，并设 p1, p2 , , ps是不超过是不超过N的形如的形如4k3的所有素数。

的所有素数令令q4p1 p2 ps1显然，每个显然，每个pi (i1, 2, , s)都都不是不是 q 的素因数，否则将会导致的素因数，否则将会导致 pi |1，得到矛盾得到矛盾13 证明：形如证明：形如4k3的素数有无穷多个的素数有无穷多个证明：如果证明：如果 q 是素数，由于是素数，由于q4p1 p2 ps14(p1 p2 ps1)3，即，即 q 也是也是形如形如4k3的素数，并且显然的素数，并且显然q pi (i1, 2, , s)，从而从而 q N 即q是形如是形如4k3的大于的大于N的素数 如果如果 q 不是素数，由第一步证明知不是素数，由第一步证明知q含有形如含有形如4k3的素因数的素因数p，同样可证，同样可证p pi (i1, 2, , s)，从而，从而 p N 即即p 是形如是形如4k3的大于的大于N的素数由于由于N是任意的正整数，因此证明了是任意的正整数，因此证明了形如形如4k3的素数有无穷多个的素数有无穷多个21 证明：证明：n 1 时，时， 不是整数不是整数证明：令整数证明：令整数 n 满足满足 2 n1 时，时， 不是整数不是整数通分后，通分后， 这一项的分子变为奇数这一项的分子变为奇数k，其余各项的，其余各项的分子均为偶数分子均为偶数(至少乘上一个至少乘上一个2)。

所以分子为所以分子为奇数，而分母为偶数所以奇数，而分母为偶数所以不是整数不是整数22 设设m n是正整数，证明：是正整数，证明：2n1 2m1的充分的充分 必要条件是必要条件是n m以任意正整数以任意正整数 a 2代替代替 2 结论结论 仍成立吗？仍成立吗？ 证明：证明： 必要性，已知必要性，已知2n1 2m1 由m n， 设设 mknr，0 r n 则 2m1 2knr1 2kn2r2r2r1 2r (2kn1)(2r1) 2r (2n) k1)(2r1) 2r (2n1) (2n)k1 (2n)k2 2n 1) (2r1) 2m1 2r (2n1) (2n)k1 (2n)k2 2n 1) (2r1) 由由 2n1 2m1 知知 2n1 2r1 由由 r 2代替代替 2 结论仍成立结论仍成立23 设奇数设奇数a 2，d d0是使得是使得 a 2d1的最小正整数的最小正整数证明证明 2d 被被 a 除后，所有可能取到的不同的除后，所有可能取到的不同的最小非负余最小非负余 数数有有d0个 证明：证明： 由由d0的定义，对的定义，对 d 1, 2, , d01， a 2d1令，令，21k1ar1， 221k2ar2 ， 231k3ar3 ， ， 下面证明下面证明互不相同。

互不相同事实上，若有事实上，若有 rirj ，j i，则，则2i1kiari ， 2j1kjarj ，两式相减得：两式相减得：(2j1)(2i1)(kjki)a 即即2i (2ji1)(kjki)a 由已知a为奇数知为奇数知 a 2i所以所以a (2ji1) ，但，但 ji 1是整数证明：是整数证明： (am1，an1) a(m, n)1 证明：证明： 不妨设不妨设m n，由带余除法得，由带余除法得 mknr，0 r 0，则继续对，则继续对(an1，ar1) 作同样得讨论，由作同样得讨论，由广义欧几里得除法知，结论成立广义欧几里得除法知，结论成立35 设设 a , b 是正整数证明：若是正整数证明：若a, b(a, b)，则，则 ab 证明：证明： a, b a (a, b) a, b b (a, b) ab a, b(a, b)36 证明：若证明：若(a, 4)2, (b, 4)2，则，则 (ab, 4)4 证明：由证明：由(a, 4)2, (b, 4)2，可设：，可设： a4k12， b4k22 ， ab 4k14k24 4(k1k21) 即即 4 (ab )，所以所以 (ab, 4)4 。

37 设设a, b 是两个不同的整数，证明如果整数是两个不同的整数，证明如果整数n 1满足满足n|(a2b2) 和和 n | (ab)，n | (ab)，则，则n是合数证明：由已知及证明：由已知及a2b2(ab)(ab)得得 n|(ab)(ab)若若 n 是素数，根据是素数，根据1.4定理定理2, n|(ab) 或或 n|(ab)，与已知条件矛盾所以与已知条件矛盾所以n是合数39 设设a, b 是任意两个不全为零的整数，是任意两个不全为零的整数，(i) 若若m是任一整数，则是任一整数，则am, bma, bmii) a, 00 证明证明:(i) 设设 L a, b，则，则 a L， b L，进而，进而am Lm， bm Lm，即，即Lm是是am, bm的公倍数的公倍数所以所以am, bm Lm a, bm反之，设反之，设L am, bm，及，及L k1am ， L k2bm ，由此知，由此知，这说明，这说明， 是是a, b的公倍数的公倍数所以所以a, b ，即，即a, b m L am, bm 综合得，综合得， am, bma, bmii) 由由 a 0 知，知， a, 00 40 证明：证明： 都不是有理数。

都不是有理数证明：反证法，设证明：反证法，设 是有理数，是有理数， 的既约分数的既约分数表示为表示为有有 2q2p2，这说明这说明 p2 是偶数，从而是偶数，从而 p 也是偶数也是偶数(若若 p 是奇数，则是奇数，则p2也是奇数也是奇数)，设，设p2k，得，得 2q2(2k)2, 2q24k2, q22k2 , 于是于是q 也是偶数，这与也是偶数，这与 是既约是既约分数矛盾分数矛盾40 证明：证明： 都不是有理数都不是有理数证明：反证法，设证明：反证法，设 是有理数，是有理数， 的既约分数的既约分数表示为表示为有有 7q2p2，这说明这说明 7 p2 ，从而，从而 7 p (因为，若因为，若 7 p ，则，则7 p2)，设设p7k，得，得 7q2(7k)2, 7q249k2, q27k2 , 于是于是 7 q ，这与，这与 是既约是既约分数矛盾分数矛盾41 证明：证明：log210，log37，log1521都是无理数都是无理数证明：若证明：若 log210 是有理数，设是有理数，设 log210 a / b (b 0)则则或或 2a 10b 2b5b等式两边出现不同的素数因数，这是不可能的。

等式两边出现不同的素数因数，这是不可能的故故log210 是无理数是无理数42 ab0, n1, 证明：证明：an bn an+bn证明：用反证法证明：用反证法假设假设 an bn an+bn则为整数，于是为整数，于是即即对对 ab0, n1不成立42 ab0, n1, 证明：证明：an bn an+bn证明：用反证法证明：用反证法假设假设 an bn an+bn，有，有 an bn an+bn (an bn )，即即an bn 2bn 设 2bn = k(an bn )，则有，则有设设(1)适当排列适当排列p1 , p2 , , ps的顺序，不妨设的顺序，不妨设 i i ，i=1,2, , t， j 1 使得使得 d k a 证明：设证明：设进一步设进一步设 i = i k+ ri ，0 ri k ， i=1,2, , s，所以所以由于由于0 ri 1，d k a 由由 i = i k+ ri ，0 ri 2则 a1 1，而，而 a1是是an1 的因数，的因数，与与an1 是素数是素数 矛盾，故矛盾，故a2 若若 n 为合数为合数 ncd，c 1，d 1，则，则2n1 2cd1 (2c1)(2c(d1)2c(d2)2c1 ) 与与an1 是素数矛盾，故是素数矛盾，故n 是素数。

是素数形为形为 Mp2p1 的素数叫的素数叫Mersenne素数已知的已知的Mersenne素数素数 p2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937时时Mp2p1 为素数 设在美国奥兰多的梅森素数搜索组织设在美国奥兰多的梅森素数搜索组织2005年年2月月28日日正式公正式公布，德国一名数学爱好者近日发现了迄今最大的素数这个布，德国一名数学爱好者近日发现了迄今最大的素数这个素数有素数有780多万位，可写成多万位，可写成2的的25964951次方减次方减1 这个新发现的素数是这个新发现的素数是第第42个梅森素数个梅森素数，它也是目前已知最，它也是目前已知最大的素数这位名叫马丁大的素数这位名叫马丁诺瓦克的数学爱好者是德国一名眼诺瓦克的数学爱好者是德国一名眼科医生，他利用主频为科医生，他利用主频为2.4GHz的个人电脑运行梅森素数计算的个人电脑运行梅森素数计算程序，经过程序，经过50多天的持续运算终于在多天的持续运算终于在2月月18日得到了这个日得到了这个7816230位的已知最大素数。

它比此前发现的最大素数多位的已知最大素数它比此前发现的最大素数多50万万位5天之后，一名法国专家独立验证了这一结果。