初等数论第一章3

第一章 §11 证明：n a a a ,,21 都是m 的倍数。

∴存在n 个整数n p p p ,,21使 n n n m p a m p a m p a ===,,,222111又n q q q ,,,21 是任意n 个整数m p q p q q p a q a q a q n n n n )(22112211+++=+++∴即n n a q a q a q +++ 2211是m 的整数2 证： )12)(1()12)(1(-+++=++n n n n n n n )1()1()2)(1(+-+++=n n n n n n )1()1/(6),2)(1(/6+-++n n n n n n )1()1()2)(1(/6+-+++∴n n n n n n 从而可知 )12)(1(/6++n n n3 证： b a , 不全为0∴在整数集合{}Z y x by ax S ∈+=,|中存在正整数，因而有形如by ax +的最小整数00by ax +Z y x ∈∀,，由带余除法有00000,)(by ax r r q by ax by ax +<≤++=+则S b q y y a q x x r ∈-+-=)()(00，由00by ax +是S 中的最小整数知0=rby ax by ax ++∴/00 下证8P 第二题by ax by ax ++/00 （y x ,为任意整数） b by ax a by ax /,/0000++∴ ).,/(00b a by ax +∴ 又有b b a a b a /),(,/),( 00/),(by ax b a +∴ 故),(00b a by ax =+4 证：作序列 ,23,,2,0,2,,23,b b b b b b ---则a 必在此序列的某两项之间即存在一个整数q ，使b q a b q 212+<≤成立 )(i 当q 为偶数时，若.0>b 则令b qa bs a t q s 2,2-=-==，则有22220b t b qb q a b q a t bs a <∴<-=-==-≤若0<b 则令b qa bs a t q s 2,2+=-=-=，则同样有2b t < )(ii 当q 为奇数时，若0>b 则令b q a bs a t q s 21,21+-=-=+=，则有 2021212b t b q a b q a bs a t b ≤∴<+-=+-=-=≤-若 0<b ，则令b q a bs a t q s 21,21++=-=+-= 则同样有 2b t ≤综上 存在性得证 下证唯一性当b 为奇数时，设11t bs t bs a +=+=则b s s b t t >-=-)(11 而b t t t t b t b t ≤+≤-∴≤≤1112,2矛盾 故11,t t s s ==当b 为偶数时，t s ,不唯一，举例如下：此时2b为整数 2,2),2(2212311b t b t b b b b b ≤=-+⋅=+⋅=⋅ 2,2,222211bt b t t bs t bs a ≤-=+=+=5.证：令此和数为S ，根据此和数的结构特点，我们可构造一个整数M ，使MS 不是整数，从而证明S 不是整数（1） 令S=n14131211+++++，取M=p k 75321⋅⋅⋅-这里k 是使n k ≤2最大整数，p 是不大于n 的最大奇数。

第一章 §11 证明：n a a a ,,21 都是m 的倍数。

∴存在n 个整数n p p p ,,21使n n n m p a m p a m p a ===,,,222111又n q q q ,,,21 是任意n 个整数m p q p q q p a q a q a q n n n n )(22112211+++=+++∴即n n a q a q a q +++ 2211是m 的整数2 证： )12)(1()12)(1(-+++=++n n n n n n n )1()1()2)(1(+-+++=n n n n n n )1()1/(6),2)(1(/6+-++n n n n n n )1()1()2)(1(/6+-+++∴n n n n n n 从而可知 )12)(1(/6++n n n3 证： b a , 不全为0∴在整数集合{}Z y x by ax S ∈+=,|中存在正整数，因而有形如by ax +的最小整数00by ax +Z y x ∈∀,，由带余除法有00000,)(by ax r r q by ax by ax +<≤++=+则S b q y y a q x x r ∈-+-=)()(00，由00by ax +是S 中的最小整数知0=rby ax by ax ++∴/00 下证8P 第二题by ax by ax ++/00 （y x ,为任意整数） b by ax a by ax /,/0000++∴ ).,/(00b a by ax +∴ 又有b b a a b a /),(,/),( 00/),(by ax b a +∴ 故),(00b a by ax =+4 证：作序列 ,23,,2,0,2,,23,b b b b b b ---则a 必在此序列的某两项之间即存在一个整数q ，使b q a b q 212+<≤成立 )(i 当q 为偶数时，若.0>b 则令b qa bs a t q s 2,2-=-==，则有22220b t b qb q a b q a t bs a <∴<-=-==-≤若0<b 则令b qa bs a t q s 2,2+=-=-=，则同样有2b t <)(ii 当q 为奇数时，若0>b 则令b q a bs a t q s 21,21+-=-=+=，则有 2021212b t b q a b q a bs a t b ≤∴<+-=+-=-=≤-若 0<b ，则令b q a bs a t q s 21,21++=-=+-= 则同样有 2b t ≤综上 存在性得证 下证唯一性当b 为奇数时，设11t bs t bs a +=+=则b s s b t t >-=-)(11 而b t t t t b t b t ≤+≤-∴≤≤1112,2矛盾 故11,t t s s ==当b 为偶数时，t s ,不唯一，举例如下：此时2b为整数 2,2),2(2212311b t b t b b b b b ≤=-+⋅=+⋅=⋅ 2,2,222211bt b t t bs t bs a ≤-=+=+=5.证：令此和数为S ，根据此和数的结构特点，我们可构造一个整数M ，使MS 不是整数，从而证明S 不是整数（1） 令S=n14131211+++++，取M=p k 75321⋅⋅⋅-这里k 是使n k≤2最大整数，p 是不大于n 的最大奇数。

《初等数论》各章习题参考解答第一章习题参考解答1.解:因为25的最小倍数是100,9的最小倍数是，所以满足条件的最小正整数11111111100a =。

2.解：3在100!的分解式中的指数()1001001001003100!33113148392781⎡⎤⎡⎤⎡⎤⎡⎤=+++=+++=⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦⎣⎦， 在100!的分解式中的指数()1001001001001002100!50251261942481664⎡⎤⎡⎤⎡⎤⎡⎤⎡⎤=++++=++++=⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦，∴ ()9448474847100!2343123,,61k k k k =⋅⋅=⋅⋅=⋅=。

故 max 47n =，min 3M k =，(),61k =。

故 当M 最小值是3的倍数，但不是2的倍数。

3.解：112121n n n n x x ++++++等价于()()21221n n n x x x ++-+-，从而3x ³（n 就不会太大，存在反向关系）。

由()()22121n nn x x x -+-?+，得()()2212n n n x x -+?，即()()()121122nn x x -+?。

若2n ³，则()()()()251221114242nn x xx x-?+??，导致25140x x -+?，无解。

所以，只有1n =，335314x x x +-?，只能是37,14x +=，从而4,11x =。

综上所述，所求正整数对()()(),4,111,1x n =、。

4.解：按题意，2m n >>，记*,m n k k N =+?；则()222211111n n k nk n k k a a a a a a a a a a a a +++-+-?-+--++-22211111n k k n k k a a a a a a a a a ++?---+?-+-，故 存在无穷多个正整数a 满足2111n k k a a a a ++-+-。

初等数论1习题参考答案附录1 习题参考答案第⼀章习题⼀1. (ⅰ) 由a b知b= aq，于是b=(a)(q)，b = a(q)及b = (a)q，即a b，a b及a b。

反之，由a b，a b 及a b也可得a b； (ⅱ) 由a b，b c 知b= aq1，c= bq2，于是c= a(q1q2)，即a c； (ⅲ) 由b a i知a i= bq i，于是a1x1a2x2a k x k = b(q1x1q2x2q k x k)，即b a1x1a2x2a k x k；(ⅳ) 由b a知a = bq，于是ac = bcq，即bc ac； (ⅴ) 由b a知a = bq，于是|a| = |b||q|，再由a0得|q| 1，从⽽|a||b|，后半结论由前半结论可得。

2. 由恒等式mq np= (mn pq) (m p)(nq)及条件m p mn pq可知m p mq np。

3. 在给定的连续39个⾃然数的前20个数中，存在两个⾃然数，它们的个位数字是0，其中必有⼀个的⼗位数字不是9，记这个数为a，它的数字和为s，则a, a 1, , a 9, a 19的数字和为s, s 1, , s 9, s 10，其中必有⼀个能被11整除。

4. 设不然，n1 = n2n3，n2p，n3p，于是n = pn2n3p3，即p3n，⽭盾。

5. 存在⽆穷多个正整数k，使得2k1是合数，对于这样的k，(k1)2不能表⽰为a2p的形式，事实上，若(k1)2= a2p，则(k 1 a)( k 1a) = p，得k 1 a = 1，k 1 a = p，即p = 2k 1，此与p为素数⽭盾。

第⼀章习题⼆1. 验证当n =0,1，2，… ,11时，12|f(n)。

2.写a = 3q1r1，b = 3q2r2，r1, r2 = 0,1或2，由3a2b2 = 3Q r12r22知r1= r2 = 0，即3a且3b。

3.记n=10q+r, (r=0,1,…,9)，则n k+4- n k被10除的余数和r k+4- r k = r k( r4-1)被10 除的余数相同。

《初等数论》总结姓名 xxx学号 xxxxxxxx院系 xxxxxxxxxxxxxxx专业 xxxxxxxxxxxxxxx个人感想初等数论是一门古老的学科，它对于数的性质以及方程整数的解做了深入的研究，是对中等数学数的理论的继续和提高。

有时候上课听老师讲解一些例题，觉得比较简单，结果便是懂非懂地草草了之，但是过段时间做老师留下的一些相似的课后练习时，又毫无头绪，无从下手。

这就是上课的时候没做到全神贯注地去听，所以课下的时间尤为重要，一定做好复习巩固的工作。

老师讲课的方法也十分好，每次上课都会花二十分钟到半个小时来对上节课的知识帮助我们进行回顾，我想很多同学都喜欢并适合这种教学方式。

知识点总结第一章整数的可除性1.2性质：(1)传递性质)；(2)闭。

若反复运用这一性质，易则对于任意的整更一般，(3)若p 是质数，若n a p |，则a p |；(6)(带余数除法)设b a ,为整数，0>b ，则存在整数q 和r ，使得r bq a +=，其中b r <≤0，并且q 和r 由上述条件唯一确定；整数q 被称为a 被b 除得的(不完全)商，数r 称为a 被b 除得的余数。

注意：r 共有b 种可能的取值：0,1，……，1-b 。

若0=r ，即为a 被b 整除的情形；易知，带余除法中的商实际上为⎥⎦⎤⎢⎣⎡b a （不超过b a 的最大整数），而带余除法的核心是关于余数r 的不等式：b r <≤0。

证明a b |的基本手法是将a 分解为b 与一个整数之积，在较为初级的问题中，这种数的分解常通过在一些代数式的分解中取特殊值而产生若n 是正整数，则))((1221----++++-=-n n n n n n y xy y x x y x y x Λ；若n 是正奇数，则))((1221----+-+-+=+n n n n n n y xy y x x y x y x Λ；（在上式中用y -代y ）(7)如果在等式∑∑===mk k ni i b a 11中取去某一项外，其余各项均为c 的倍数，则这一项也是c 的倍数；(8)个连续整数中，有且只有一个是n 的倍数；(9)任何n 个连续的整数之积一定是n!的倍数，特别地，三个连续的正整数之积能被6整除；第二章 不定方程1. 定义：二元一次不定方程的一般形式是ax +by = c ，其中a ,b ,c 是整数2. 定理：(1) 不定方程有整数解的充要条件为 (a,b) | c. (2) 设是方程的一组解，则不定方程有无穷解，其一切解可表示成⎩⎨⎧+=-=t a yy t b x x 1010 Λ,2,1,0±±=t 其中),(,),(11b a b b b a a a ==3. 不定方程的解法：（1）观察法：当a,b 的绝对值较小时可直接观察不定方程的一组特解，然后用⎩⎨⎧+=-=ta y y tb x x 1010得到其所有解（2）公式法：当a,b 的绝对值较小时，可用公式211021110,,1,0,,1----+===+===k k k k k k k k P Q q Q Q Q P P q P q P P 得到特解n n n n P y Q x )1(,)1(010-=-=-，然后用公式写出一切解。

第一节 整数的p 进位制及其应用正整数有无穷多个，为了用有限个数字符号表示出无限多个正整数，人们发明了进位制，这是一种位值记数法。

进位制的创立体现了有限与无限的对立统一关系，近几年来，国内与国际竞赛中关于“整数的进位制”有较多的体现，比如处理数字问题、处理整除问题及处理数列问题等等。

在本节，我们着重介绍进位制及其广泛的应用。

基础知识给定一个m 位的正整数A ，其各位上的数字分别记为021,,,a a a m m，则此数可以简记为：021a a a A m m （其中01 m a ）。

由于我们所研究的整数通常是十进制的，因此A可以表示成10的1m 次多项式，即012211101010a a a a A m m m m ，其中1,,2,1},9,,2,1,0{ m i a i 且01 m a ，像这种10的多项式表示的数常常简记为10021)(a a a A m m 。

在我们的日常生活中，通常将下标10省略不写，并且连括号也不用，记作021a a a A m m ，以后我们所讲述的数字，若没有指明记数式的基，我们都认为它是十进制的数字。

但是随着计算机的普及，整数的表示除了用十进制外，还常常用二进制、八进制甚至十六进制来表示。

特别是现代社会人们越来越显示出对二进制的兴趣，究其原因，主要是二进制只使用0与1这两种数学符号，可以分别表示两种对立状态、或对立的性质、或对立的判断，所以二进制除了是一种记数方法以外，它还是一种十分有效的数学工具，可以用来解决许多数学问题。

为了具备一般性，我们给出正整数A 的p 进制表示：012211a p a p a p a A m m m m ，其中1,,2,1},1,,2,1,0{ m i p a i 且01 m a 。

而m 仍然为十进制数字，简记为p m m a a a A )(021 。

典例分析例1．将一个十进制数字2004（若没有指明，我们也认为是十进制的数字）转化成二进制与八进制，并将其表示成多项式形式。

第一章 整除理论§1.1 整数与自然数及整除的基本性质整数集},3,2,1,0,1,2,3,{ ---=Z ，整数中的四则运算我们已在中小学学习过，需要注意的是，任何下有界的非空整数集总含有它的最小元，这一性质也称为最小整数原理.同样地，一个上有界的非空整数集总含有它的最大元，自然数即是正整数，全体自然数集用N 表示.定义1.1.1 设0,,≠∈a Z b a ,如Z d ∈∃使得b ad =，则称a 整除b ，记为b a ，这里a 称为b 的约数或因数(或因子),b 称为a 的倍数.如果a 不能整除b ,则记为b a |/.例如3|1010|312|924|6,15|536|126|3///--，，，，，等等。

值得注意的是，由于Z a ∈∀，有00=⋅a ,若,0≠a 则0|a ,所以0被任何整数整除.定理1.1.1 (i ) .||||b a b a b a b a ⇔-⇔-⇔(ii )(传递性) c a c b b a ||,|⇒.(iii ) 若b d a d |,|,则by ax d Z y x +∈∀|,,有.(iv ) bn an b a n ||,0⇔≠∀(v ) b a a b b a ±=则若,|,|.(vi ) b a b b a ≤≠则且若,0,|.证明 仅证(iii ).因为,,|,|2,1Z d d b d a d ∈∃故使得a dd =1,b dd =2,⇒∀)(,,2121y d x d d y dd x dd by ax Z y x +=+=+∈有,而Z y d x d ∈+21,故by ax d +|.证毕.在此定理中的(iii )显然有如下推广:定理1.1.2 若Z x m i a d i i ∈∀=则),,,2,1(| ,有∑=mi i i x a d 1|.例1 证明 若2|n, 3|n, 则6|n.证明 由于2|n,得n=2k(Z k ∈),由条件知3|2n,又由定理1.1.1中(iv )与(ii )可得3|3k,所以由定理1.1.1(iii )知3|(3k-2k),即3|k,再由定理1.1.1(iv )知k ⨯⨯2|32,即6|n.证毕.定理1.1.3 设b a ,是两个整数,其中0>b ,则存在两个唯一得整数r q 和,使得r bq a +=, b r <≤0 (1)成立证明 考虑数列,3,2,,0,,2,3,b b b b b b ---那么a 必在上述序列的某两之间,或是其中某一项,即存在一个整数q 使得b q a qb )1(+<≤ 成立.令.0,b r r qb a <≤=-则有故有(1)成立.再证唯一性.设11,r q 是满足(1)的另一对整数,因为r bq r q b +=+111,于是r r q q b -=-11)(.所以r r q q b -=-11.由于1r r 与都是小于b 的非负整数.故上式右边小于b ,如果q q ≠1,则上式左边b ≥,这不可能,故必q q =1.由此及上式知r r =1.证毕.定义1.1.2 我们把(1)式中q 叫做a 被b 除得出的不完全商,r 叫做a 被b 除所得到的余数.也叫做非负最小剩余.常记作r a b =><.以后总假定除数0>b 以及因数为正.在不致引起混淆的情况下,b a ><中的b 常略去不写.显然有如下结论:定理1.1.4 对于整数0,,,21>b b a a 其中,有(i ) 〉〉〈+〉〈〈=〉+〈2121a a a a .(ii ) 〉〉〈-〉〈〈=〉-〈2121a a a a .(iii ) 〉〉〉〈〈〈=〉〈2121,a a a a .证明 仅证(i )与(iii ).(ii )读者自证.设〉〈+=111a bq a ,〉〈+=222a bq a . 〉〉〈+〉〈〈+=〉〈+〉〈21321a a bq a a .于是〉〉〈+〉〈〈+++=〉〈+〉〈++=+21321212121)()(a a q q q b a a q q b a a .所以由定理1.1.3知(i )成立.又设 〉〈+=2121,a a bq a a ,于是))((221121〉〈+〉〈+=a bd a bd a a〉〉〈〈+-〉〈+〉〈+=21122121)(a a q a d a d d bd b从而 〉〉〉〈〈〈=〉〉〈〈2121,a a a a ,由定义知〉〉〉〈〈〈=〉〉〉〈〈〈=〉〈212121,a a a a a a由此(iii )得证.§2 最大公因数与辗转相除法定义1.2.1 设n a a a ,,,21 是n 个不全为零的整数.若整数d 是它们之中每一个因数,那么d 就叫做n a a a ,,,21 的一个公因数(或称为公约数).整数n a a a ,,,21 的公因数中最大的一个叫做最大公因数(或称为最大公约数),记作(n a a a ,,,21 ),若(n a a a ,,,21 )=1,我们称n a a a ,,,21 互素.注: n(n>1)个整数的公因数必有限.由最大公因数的定义知(n a a a ,,,21 )=),,,(21n a a a .而一组不全为零的整数的最大公因数等于它们当中全体不为零的整数的最大公因数,所以只须讨论全体正整数的最大公因数.首先将介绍辗转相除法求最大公因数.定理1.2.1 设c b a ,,是任意三个不全为零的整数,且c bq a +=,其中q 是整数,则),(),(c b b a =.证明 b d a d |,|∀,则由定理1.1.1知c d bq a d |).(|即-+,由d 的任意性知c b a |),(,故),(),(c b b a ≤.反之,c d b d |,|∀,由定理1.1.1知a d |,由d 的任意性知a c b |),(,于是),(),(b a c b ≤.综上),(),(c b b a =.证毕.设0,0>>b a ,由定理1.1.3(带余数除法)则有11r bq a +=, )|(01a b b r /<<221r q r b +=, )|(0112b r r r /<<3321r q r r +=, )|(01223r r r r /<<(1) n n n n r q r r +=--12, )|(0211---/<<n n n n r r r r 11+-=n n n q r r , )|(1-/n n r r 由于余数)1(n i r i ≤≤是正整数且逐次减小,所以经有限步后必有一个余数为零.即01=+n r .由(1)及定理1.2.1则得下述结论: 定理1.2.2 若任给整数0,0>>b a ,则n r b a =),(. 证明 由定理1.2.1得),(),(),(),(),0(2111b a r r r r r r r r n n n n n n n n ======---+ . 证毕.定理1.2.3 设0,0>>b a ,对于如上辗转相除法(1).有 n k r b U a V k k k k ,,2,1,)1(1 =-=-- (2) 这里⎩⎨⎧+===+===----211021110,1,1,,1k k k k k k k k V V q V V V U U q U q U U (3) 证明 可用数学归纳法来证明.由(1) 11r bq a +=,可写成 11111)1(r b U a V --=-. 由b q q a q r r b q a q r q r b )1()(1222212221+-=-+-=+=得,即21222)1(r b U a V --=-. 所以当2,1==k k 定理成立.下证由1+k k 到也成立.由于 111-k +++=k k k r r q r , )()1()()1(111121b U a V q b U a V r k k k k k k k k -----=-+---+ 所以)()1(1111b U a V q b U a V r k k k k k k k -+-=-+--+ b U a V b U U q a V V q k k k k k k k k 111111)()(++-+-+-=+-+=证毕.例1.2.1 求(299,247) 解.013339,1339152,39524247,522471299+⨯=+⨯=+⨯=+⨯=故 13)247,299(=由定理1.2.3即得如下推论: 推论1.2.1 若Z y x d b a ∈=,,),(则有使得 d by ax =+.证明 令k k k k U y V x )1(,)1(1-=-=-则有 d r by ax k ==+. 证毕.由例1.2.1知 13,3,247,299====k r n b a .由上面的等式 333b b U a V =-.而1,4,1321===q q q ,由(3)可得6,533==U V ,即1324762995=⨯-⨯. 所以d by ax y x =+-==有6,5.推论1.2.2b a 与的因数是),(b a 的因数. 证明 b a ,∀的公因数d ',则.|,|.|,|d d by ax d b d a d '+'''即所以证毕.定理1.2.4 设),(),(,1),(c b c ab c a ==则. 证明 设1),(,,,),(1111====c b d c c d b b d c b 且则(否则,若1),(11>c b ;反证d 不是b a 与的最大公因数),于是),(),(),(1111c ab d d c d ab c ab ==. 再证若.1),(11=c ab .|,|.1),(111c d ab d d c ab ''>'=则若d '无大于1的因子整除1b .则a d |',又c c |'.c d c d |,|1''于是.所以1),(>'≥d c a .此与1),(11=c b 矛盾.总之,.1),(11=c ab 于是d c ab d c ab ==),(),(11.证毕.推论1.2.3 设b c ab c c a |,|,1),(则=. 证明 因为.|,),(),(b c c c b c ab 即==证毕.。

第一章整除理论整除性理论是初等数论的基础。

本章要介绍带余数除法，辗转相除法，最大公约数，最小公倍数，算术基本定理以及它们的一些应用。

第一节数的整除性定义1设a，b是整数，b≠ 0，如果存在整数c，使得a = bc成立，则称a被b整除，a是b的倍数，b是a的约数（因数或除数），并且使用记号b∣a；如果不存在整数c使得a = bc成立，则称a不被b整除，记为b|/a。

显然每个非零整数a都有约数±1，±a，称这四个数为a的平凡约数，a的另外的约数称为非平凡约数。

被2整除的整数称为偶数，不被2整除的整数称为奇数。

定理1下面的结论成立：(ⅰ) a∣b⇔±a∣±b；(ⅱ) a∣b，b∣c⇒a∣c；(ⅲ) b∣a i，i = 1, 2, , k⇒b∣a1x1+a2x2+ +a k x k，此处x i（i = 1, 2, , k）是任意的整数；(ⅳ) b∣a ⇒bc∣ac，此处c是任意的非零整数；(ⅴ) b∣a，a≠ 0 ⇒ |b| ≤ |a|；b∣a且|a| < |b| ⇒a = 0。

证明留作习题。

定义2若整数a≠ 0，±1，并且只有约数±1和±a，则称a是素数（或质数）；否则称a为合数。

以后在本书中若无特别说明，素数总是指正素数。

定理2任何大于1的整数a都至少有一个素约数。

证明若a是素数，则定理是显然的。

若a不是素数，那么它有两个以上的正的非平凡约数，设它们是d1, d2, , d k 。

不妨设d1是其中最小的。

若d1不是素数，则存在e1 > 1，e2 > 1，使得d1 = e1e2，因此，e1和e2也是a的正的非平凡约数。

这与d1的最小性矛盾。

所以d1是素数。

证毕。

推论证明使用定理2中的记号，有a = d1d2，其中d1 > 1是最小的素约数，所以d12≤a。

证毕。

例1设r是正奇数，证明：对任意的正整数n，有n+ 2|/1r+ 2r+ +n r。