《初等数论》习题解答（第三版）广东石油化工学院
第一章 整数的可除性
§1 整除的概念·带余除法 1．证明定理3
定理3 若a1，a2，，an都是m得倍数，q1，q2，，qn是任意n个整数，则
q1a1?q2a2?证明：
?qnan是m得倍数．
a1,a2,an都是m的倍数。
pn使 a1?p1m,a2?p2m,? 存在n个整数p1,p2,又q1,q2,,an?pnm
,qn是任意n个整数
?qnan
?q1a1?q2a2??q1p1m?q2p2m??(p1q1?q2p2?即q1a1?q2a2??qnpnm?qnpn)m
?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)．
1 / 77
《初等数论》习题解答（第三版）广东石油化工学院
证：
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,|t|?|b| 2成立，并且当b是奇数时，s，t是唯一存在的．当b是偶数时结果如何？ 证：作序列
,?3bbb3b,?b,?,0,,b,,2222qq?1b?a?b成立 22则a必在此序列的某两项之间
即存在一个整数q，使
(i)当q为偶数时，若b?0.则令s?qq,t?a?bs?a?b，则有 22bqqq0?a?bs?t?a?b?a?b?b?t?
2222 若b?0 则令s??,t?a?bs?a?q2bqb，则同样有t?
22(ii)当q为奇数时，若b?0则令s?q?1q?1,t?a?bs?a?b，则有 22 2 / 77
《初等数论》习题解答（第三版）广东石油化工学院 ?bbq?1q?1?t?a?bs?a?b?a?b?0?t? 2222bq?1q?1综上所述，存在性,t?a?bs?a?b，则同样有t?2，22若 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 22b为整数 2当b为偶数时，s,t不唯一，举例如下：此时
3?bbbbb?b?1??b?2?(?),t1?,t1?22222
§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??(a,b)?rn
?d?|a?bq1?r1， d?|b?r1q2?r2，┄, d?|rn?2?rn?1qn?rn?(a,b),
即d?是(a,b)的因数。
3 / 77
,rn?2
?rn?1qn?rn,rn?1?r1?b 《初等数论》习题解答（第三版）广东石油化工学院
反过来(a,b)|a且(a,b)|b，若d??|(a,b),则d??|a,d??|b，所以(a,b)的因数都是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|??sn,tn,tn?2?tn?1sn?tn; ?sn?1,tn?1,tn?1?tnsn?1?tn?1;
且|tn|?|t|b?,222,如此类推知：
|tn?1||tn?2|?2?22?|t||b| ?2n2n?1而b是一个有限数，??n?N,使tn?1?0
?(a,b)?(b,t)?(t,t1)?(t1,t2)??(tn,tn?1)?(tn,0)?tn，存在其求法为：
(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 log2 4 / 77
《初等数论》习题解答（第三版）广东石油化工学院
证：由P3§1习题4知在（1）式中有 0?rn?1?rn?rn?1rn?2?2?22?r1b，而rn?1 ?2n?12n ?1?logblogbbn?n?logb?n?， ，即 ,?2?b2log2log22n§3 整除的进一步性质及最小公倍数
1．证明两整数a，b互质的充分与必要条件是：存在两个整数s，t满足条件ax?bt?1． 证明 必要性。若(a,b)?1，则由推论1.1知存在两个整数s，t满足：as?bt?(a,b)，
?as?bt?1
充分性。若存在整数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 定理3 ?a1,a2证：设[a1,a2,,an???|a1|,|a2|,|an|?
,n)
,an]?m1，则ai|m1(i?1,2,,n)又设[|a1|,|a2|,∴|ai||m1(i?1,2,,|an|]?m2
则m2|m1。反之若|ai||m2，则ai|m2，?m1|m2 从而m1?m2，即[a1,a2,3．设anxn?an?1xn?1?,an]=[|a1|,|a2|,,|an|]2
?a1x?a0 （1）
是一个整数系数多项式且a0，an都不是零，则（1）的根只能是以a0的因数作分子以an为分母的既约分数，并由此推出2不是有理数．
证：设（1）的任一有理根为
p，(p,q)?1,q?1。则 q 5 / 77