《初等数论》习题解答（第三版）广东石油化工学院
第一章 整数的可除性§1 整除的概念·带余除法
1．证明定理3:若a1，a2，，an都是m得倍数，q1，q2，，qn是任意n个整数，则
q1a1?q2a2?证明：
?qnan是m得倍数．
,an都是m的倍数。? 存在n个整数p1,p2,,an?pnm又q1,q2,?qnpnm?(p1q1?q2p2?pn使
a1,a2a1?p1m,a2?p2m,?q1p1m?q2p2m?,qn是任意n个整数?q1a1?q2a2??qnpn)m即q1a1?q2a2??qnan
?qnan是m的整数
2．证明 3|n(n?1)(2n?1) 证明 又
n(n?1)(2n?1?)nn(?1n)?(?2n??n(n?1)(n?2)?n(?1n)n(?
n(n?1)(n?2)，(n?1)n(n?2)是连续的三个整数故3|n(n?1)(n?2),3|(n?1)n(n?1) ?3|n(n?1)(n?2)?(n?1)n(n?1)从而可知
3|n(n?1)(2n?1)
3．若ax0?by0是形如ax?by（x，y是任意整数，a，b是两不全为零的整数）的数中最小整数，则(ax0?by0)|(ax?by)． 证：
a,b不全为0?在整数集合S??ax?by|x,y?Z?中存在正整数，因而有形如ax?by的最
小整数ax0?by0?x,y?Z，由带余除法有ax?by?(ax0?by0)q?r,0?r?ax0?by0.
则r?(x?x0q)a?(y?y0q)b?S，由ax0?by0是S中的最小整数知r?0?ax0?by0|ax?by
ax0?by0|ax?by （x,y为任意整数） ?ax0?by0|a,ax0?by0|b?ax0?by0|(a,b). 又有
(a,b)|a，(a,b)|b?(a,b)|ax0?by0 故ax0?by0?(a,b)
4．若a，b是任意二整数，且b?0，证明：存在两个整数s，t使得a?bs?t,成立，并且当b是奇数时，s，t是唯一存在的．当b是偶数时结果如何？ 证：作序列
|t|?|b| 2,?3bbb3b,?b,?,0,,b,,2222 1 / 57
则a必在此序列的某两项之间
《初等数论》习题解答（第三版）广东石油化工学院
即存在一个整数q，使
qq?1b?a?b成立 22qq,t?a?bs?a?b，则有22(i)当q为偶数时，若b?0.则令s?bqqqqq0?a?bs?t?a?b?a?b?b?t?若b?0 则令s??,t?a?bs?a?b，则同
222222样有t?b2(ii)当q为奇数时，若b?0则令s?q?1q?1,t?a?bs?a?b，则有 22?bbq?1q?1?t?a?bs?a?b?a?b?0?t? 2222bq?1q?1,t?a?bs?a?b，则同样有t?综上所述，存在性得证． 222，
若 b?0，则令s??下证唯一性: 当b为奇数时，设a?bs?t?bs1?t1则t?t1?b(s1?s)?b 而t?bb,t1??t?t1?t?t1?b 矛盾 故s?s1,t?t1 22bbbbbb为整数3??b?1??b?2?(?),t1?,t1?222222
当b为偶数时，s,t不唯一，举例如下：此时
§2 最大公因数与辗转相除法
1．证明推论4.1:推论4.1 a，b的公因数与（a，b）的因数相同． 证：设d?是a，b的任一公因数，?d?|a，d?|b由带余除法
a?bq1?r1,b?r1q2?r2,?rnqn?1,0?rn?1?rn?rn?1??r1?b,rn?2
?rn?1qn?rn,rn?1, d?|rn?2?rn?1qn?rn?(a,b), ?(a,b)?rn ?d?|a?bq1?r1， d?|b?rq12?r2，┄即d?是(a,b)的因数。反过来(a,b)|a且(a,b)|b，若d??|(a,b),则d??|a,d??|b，所以(a,b)的
2 / 57
《初等数论》习题解答（第三版）广东石油化工学院
因数都是a,b的公因数，从而a,b的公因数与(a,b)的因数相同。
2．证明：见本书P2，P3第3题证明。
3．应用§1习题4证明任意两整数的最大公因数存在，并说明其求法，试用你的所说的求法及辗转相除法实际算出（76501，9719）．
解：有§1习题4知：?a,b?Z,b?0,?s,t?Z,使a?bs?t,|t|?b。， 2??s1,t1，使b?s1t?t1,|t1|?|t|b?,222,如此类推知：?sn,tn,tn?2?tn?1sn?tn;
|t||b|?n?1 n22 ?(tn,tn?1)?(tn,0)?tn，
?sn?1,tn?1,tn?1?tnsn?1?tn?1;且|tn|?|tn?1||tn?2|?2?22?而b是一个有限数，??n?N,tn?1?0?(a,b)?(b,t)?(t,t1)?(t1,t2)?存在其求法为：(a,b)?(b,a?bs)?(a?bs,b?(a?bs)s1)?
?(76501,9719)?(9719,76501?9719?7)?(8468,9719?8468)?(1251,8468?1251?6) ??(3,1)?14．证明本节（1）式中的n?logb证：由P3§1习题4知在（1）式中有
log2
?r1b?，而rn?1 n?1n22 0?rn?1?rn?rn?1rn?2?2?22 ?1?logblogbbn,?2?b?n?logb?n?， ，即 2n2log2log2§3 整除的进一步性质及最小公倍数
1．证明两整数a，b互质的充分与必要条件是：存在两个整数s，t满足条件ax?bt?1．
3 / 57
《初等数论》习题解答（第三版）广东石油化工学院
?as?bt?1 证明 必要性。若(a,b)?1，则由推论1.1知存在两个整数s，t满足：as?bt?(a,b)，
充分性。若存在整数s，t使as+bt=1，则a，b不全为0。
又因为(a,b)|a,(a,b)|b，所以(a,b|as?bt) 即(a,b)|1。又(a,b)?0，?(a,b)?1
2．证明定理3: ?a1,a2,an???a|1|a,|2|an,?| |证：设[a1,a2,,an]?m1，则ai|∴|ai||m1(i?1,2,,n)又[|a1|,|a2|,,|an|]?m2mi(,2?,,)n11则m2|m1。反之若|ai||m2，则ai|m2，即[a1,a2,,an]=[|a1|,|a2|,,|an|]2 ?m1|m2从而m1?m2，
3．设anxn?an?1xn?1??a1x?a0（1）,是一个整数系数多项式且a0，an都不是零，则（1）的根只能是以a0的因数作分子以an为分母的既约分数，并由此推出2不是有理数． 证：设（1）的任一有理根为
ppp，(p,q)?1,q?1。则an()n?an?1()n?1?qqq?a1p?a0?0 qanpn?an?1pn?1q??a1pqn?1?a0qn?0 （2） 由(2)?anpn?an?1pn?1q??a1pqn?1?a0qn，
所以q整除上式的右端，所以q|anpn，又(p,q)?1,q?1，所以(q,pn)?1,?q|an； 又由（2）有anpn?an?1pn?1q??a1pqn?1??a0qn
因为p整除上式的右端，所以P|a0qn ，(p,q)?1,q?1，所以(qn,p)?1, ∴p|an 故（1）的有理根为
p，且p|a0,q|an。假设2为有理数，x?2,?x2?2?0，次方程为整系q数方程，则由上述结论，可知其有有理根只能是?1,?2，这与2为其有理根矛盾。故2为无理数。另证，设2为有理数2=p,(p,q)?1,q?1 qp22?2,?2q2?p2,?(p2,q2)?(2q2,p2)?q2?1
q但由(p,q)?1,q?1知(p2,q2)?1，矛盾，故2不是有理数。 §4 质数·算术基本定理
1．试造不超过100的质数表 解：用Eratosthenes筛选法
4 / 57
相关推荐：
loading