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

第一章习题解答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证明：形如3k－1，4k－1，6k－1的正整数必有同样形式的素因数。证明：证形如3k－1的正整数必含形如3k－1的素因数。由于任一素数可以写成3n－1,3n或3n＋1的形式，而(3n1)(3n2)＝9n1n2＝3(3n1n2),(3n1＋1)(3n2＋1)＝9n1n2＋3n1＋3n2＋1＝3(3n1n2＋n1＋n2)＋1,所以把形如3n或3n＋1的数相乘的积仍为3n形式的数。12证明：形如3k－1，4k－1，6k－1的正整数必有同样形式的素因数。证明：又(3n1)(3n2＋1)＝9n1n2＋3n1＝3(3n1n2＋n1),即把形如3n与3n＋1的数相乘的积仍为3n形式的数。因此，把形如3k－1的整数分解成素数的乘积时，这些素因数不可能都是形如3n或3n＋1的形式的素数，一定含有3n－1形式的素因数。13证明：形如4k＋3的素数有无穷多个。证明：分两步证明。先证形如4k＋3的正整数必含形如4k＋3的素因数。由于任一奇素数只能写成4n＋1或4n＋3的形式，而(4n1＋1)(4n2＋1)＝16n1n2＋4n1＋4n2＋1＝4(4n1n2＋n1＋n2)＋1,所以把形如4n＋1的数相乘的积仍为4n＋1形式的数。13证明：形如4k＋3的素数有无穷多个。证明：因此，把形如4k＋3的整数分解成素数的乘积时，这些素因数不可能都是4n＋1的形式的素数，一定含有4n＋3形式的素数。其次，设N是任一正整数，并设p1,p2,…,ps是不超过N的形如4k＋3的所有素数。令q＝4p1p2…ps－1。显然，每个pi(i＝1,2,…,s)都不是q的素因数，否则将会导致pi|1，得到矛盾。13证明：形如4k＋3的素数有无穷多个。证明：如果q是素数，由于q＝4p1p2…ps－1＝4(p1p2…ps－1)＋3，即q也是形如4k＋3的素数，并且显然qpi(i＝1,2,…,s)，从而qN。即q是形如4k＋3的大于N的素数。如果q不是素数，由第一步证明知q含有形如4k＋3的素因数p，同样可证ppi(i＝1,2,…,s)，从而pN。即p是形如4k＋3的大于N的素数。由于N是任意的正整数，因此证明了形如4k＋3的素数有无穷多个。21证明：n1时，不是整数。证明：令整数n满足2n2＋1。将n131211＋＋＋＋11111123n221＋＋＋＋＋＋＋通分。则公分母必为2·k，k为奇数。7532732752753275353275327327532753275327532753252131217132151213121110191817161514131211232232322322323232223232＋＋＋＋＋＋＋＋＋＝＋＋＋＋＋＋＋＋＋＝＋＋＋＋＋＋＋＋＋21证明：n1时，不是整数。n131211＋＋＋＋通分后，这一项的分子变为奇数k，其余各项的分子均为偶数(至少乘上一个2)。所以分子为奇数，而分母为偶数。所以不是整数。21n131211＋＋＋＋22设mn是正整数，证明：2n－12m－1的充分必要条件是nm。以任意正整数a2代替2结论仍成立吗？证明：必要性，已知2n－12m－1。由mn，设m＝kn＋r，0rn。则2m－1＝2kn＋r－1＝2kn·2r－2r＋2r－1＝2r(2kn－1)＋(2r－1)＝2r((2n)k－1)＋(2r－1)＝2r(2n－1)((2n)k－1＋(2n)k－2＋…＋2n＋1)＋(2r－1)2m－1＝2r(2n－1)((2n)k－1＋(2n)k－2＋…＋2n＋1)＋(2r－1)由2n－12m－1知2n－12r－1。由rn得，r＝0，即nm。充分性，已知nm，设m＝kn。则2m－1＝2kn－1＝(2n)k－1＝(2n－1)((2n)k－1＋(2n)k－2＋…＋2n＋1)，所以，2n－12m－1。以任意正整数a2代替2结论仍成立。23设奇数a2，d＝d0是使得a2d－1的最小正整数。证明2d被a除后，所有可能取到的不同的最小非负余数有d0个。证明：由d0的定义，对d＝1,2,…,d0－1，a2d－1。令，2－1＝k1a＋r1，22－1＝k2a＋r2，23－1＝k3a＋r3…，，akdd001211100012dddrakarrrd1210,,,0下面证明1210,,,drrr互不相同。事实上，若有ri＝rj，ji，则2i－1＝kia＋ri，2j－1＝kja＋rj，两式相减得：(2j－1)－(2i－1)＝(kj－ki)a即2i(2j－i－1)＝(kj－ki)a。由已知a为奇数知a2i所以a(2j－i－1)，但j－id0，得到矛盾。说明互不相同。1210,,,drrr从而，是2d被a除后，d0个不同的最小非负余数。最后，由1,,1,1,11210drrr)12()12(21222212000sdssssdsd所以ssdsssdssdssdrakkrakak)2(2)12()12(2120000说明，被a除后的余数与2s－1被a除后的余数相同。从而，120sd1,,1,1,11210drrr是2d被a除后，d0个所有可能取到的不同的最小非负余数。26证明：(i)如果正整数a,b满足(a,b)＝1，那么对于任意正整数n，都有(an,bn)＝1。(ii)如果a,b是整数，n是正整数，且anbn，那么ab。证明：(i)由1.4节定理1：若(a,c)＝1，则(ab,c)＝(b,c)。从而(a2,b)＝(aa,b)＝(a,b)＝1，以此类推(an,b)＝(aan－1,b)＝(an－1,b)＝(aan－2,b)＝(an－2,b)＝…＝(a2,b)＝(aa,b)＝(a,b)＝1(b，an)＝(an,b)＝1，类似的(bn,an)＝(bbn－1,an)＝(bn－1,an)＝(bbn－2,an)＝(bn－2,an)＝…＝(b2,an)＝(bb,an)＝(b,an)＝1(ii)设sipppaiss,,2,1,0,2121sipppbiss,,2,1,0,2121则,2121snsnnnpppa,2121snsnnnpppb由anbn，根据1.5节定理3知nini，即ii，所以根据1.5节定理3ab。29求如下整数对的最大公因数：(1)(2t＋1，2t－1)，(2)(2n，2(n＋1))，(3)(kn，k(n＋2))，(4)(n－1，n2＋n＋1)。解2t＋1＝1·(2t－1)＋2由1.3定理3(2t＋1，2t－1)＝(2t－1，2)＝1因为2t－1为奇数34设m，n是正整数，a1是整数。证明：(am－1，an－1)＝a(m,n)－1。证明：不妨设mn，由带余除法得m＝kn＋r，0rn。有am－1＝akn＋r－1＝akn·ar－ar＋ar－1＝ar(akn－1)＋(ar－1)＝ar(an－1)((an)k－1＋(an)k－2＋…＋an＋1)＋(ar－1)由1.3节定理3，得(am－1，an－1)＝(an－1，ar－1)注意到(m,n)＝(n,r),若r＝0，则(m,n)＝n，结论成立。若r0，则继续对(an－1，ar－1)作同样得讨论，由广义欧几里得除法知，结论成立。35设a,b是正整数。证明：若[a,b]＝(a,b)，则a＝b。证明：[a,b]a(a,b)[a,b]b(a,b)a＝b＝[a,b]＝(a,b)36证明：若(a,4)＝2,(b,4)＝2，则(a＋b,4)＝4。证明：由(a,4)＝2,(b,4)＝2，可设：a＝4k1＋2，b＝4k2＋2，a＋b＝4k1＋4k2＋4＝4(k1＋k2＋1)即4(a＋b)，所以(a＋b,4)＝4。37设a,b是两个不同的整数，证明如果整数n1满足n|(a2－b2)和n|(a＋b)，n|(a－b)，则n是合数。证明：由已知及a2－b2＝(a＋b)(a－b)得n|(a＋b)(a－b)。若n是素数，根据1.4定理2,n|(a＋b)或n|(a－b)，与已知条件矛盾。所以n是合数。39设a,b是任意两个不全为零的整数，(i)若m是任一整数，则[am,bm]＝[a,b]m。(ii)[a,0]＝0。证明:(i)设L＝[a,b]，则aL，bL，进而amLm，bmLm，即Lm是am,bm的公倍数。所以[am,bm]Lm＝[a,b]m。反之，设L＝[am,bm]，及L＝k1am，L＝k2bm，由此知，mLmLba''|,|这说明，是a,b的公倍数。所以[a,b]，即[a,b]mL＝[am,bm]。综合得，[am,bm]＝[a,b]m。(ii)由a0知，[a,0]＝0。mL'mL'40证明：都不是有理数。17,7,2证明：反证法，设是有理数，的既约分数表示为22qp2有2q2＝p2，这说明p2是偶数，从而p也是偶数(若p是奇数，则p2也是奇数)，设p＝2k，得2q2＝(2k)2,2q2＝4k2,q2＝2k2,于是q也是偶数，这与是既约分数矛盾。qp40证明：都不是有理数。17,7,2证明：反证法，设是有理数，的既约分数表示为77qp7有7q2＝p2，这说明7p2，从而7p(因为，若7p，则7p2)，设p＝7k，得7q2＝(7k)2,7q2＝49k2,q2＝7k2,于是7q，这与是既约分数矛盾。qp41证明：log210，log37，log1521都是无理数。证明：若log210是有理数，设log210＝a/b(b0)则102ba或2a＝10b＝2b·5b等式两边出现不同的素数因数，这是不可能的。故log210是无理数。42ab0,n1,证明：an–bnan+bn。证明：用反证法。假设an–bnan+bn。则22111nnnnnnnnababbabab为整数，于是112nab或即23nab或对ab0,n1不成立。42ab0,n1,证明：an–bnan+bn。证明：用反证法。假设an–bnan+bn，有an–bnan+bn–(an–bn)，即an–bn2bn。设2bn=k(an–bn)，则有2nnakbk1212,0,1,2,,ssiapppis1212,0,1,2,,ssibpppis设(1)适当排列p1,p2,···,ps的顺序，不妨设ii，i=1,2,…,t，jj，j=t+1,t+2,…,s，于是12121122112212121212()()()2()ssttttttssnnsnnsntnttspppabppppppkpppk从而112211221212()2()ttttssttnttsntkpppkpppk和k+2不可能同时为完全n次方的整数。得到矛盾。43证明：gc的充要条件是对任意pg(p为素数)必有pc，这里pg表示pg，p＋1g。证明：设sipppgiss,,2,1,0,2121sipppciss,,2,1,0,2121若gc，由1.5节定理3，ii，所以sicpi,,2,1,反之由有，由1.5节定理3，ii，所以gc。gpi||cpi|44设k是给定的正整数，证明：任一正整数n必可唯一表示为n=abk，其中a,