下载文档原格式
初等数论初等数论从外表意义来讲，就是作为一门研究数的相关性质的数学学科。
准确地按照潘承洞、潘承彪两位数论大师的说法：初等数论是研究整数最基本的性质，是一门十分重要的数学基础课。
它不仅是中、高等师范院校数学专业，大学数学各专业的必修课，而且也是电脑科学等相关专业所需的课程。
纵观数论发展过程，我国出现了许许多多的数论大师，如：华罗庚的早期研究方向、陈景润、潘承洞等。
第一部分：整除初接触初等数论，经过《初等数论》课本知整除理论是初等数论的基础。
整除理论首先涉及整除。
现向上延伸则想到整除的对象，即自然数、整数。
从小学、中学再到大学，我们从接触最初的1、2、3再到后来的有理数、无理数、实数再到复数，可谓种类繁多。
但数论中的整除运算仅仅局限于自然数及其整数等相关范围内。
首先大学数学中绝大多数数学定义中的自然数不包括0 ，这似乎与中学有一点差异，当然整数的定义改变就相对少得多。
另外，自然数、整数的相关基本性质需懂得及灵活利用，如分配律、交换律、反对称性等。
在初等代数中曾系统地介绍了自然数的起源问题：自然数源于经验，自然数的本质属性是由归纳原理刻画的，它是自然数公理化定义的核心。
自然数集合严格的抽象定义是由Peano定理给出的，他刻画了自然数的本质属性，并导出有关自然数的有关性质。
Peano定理：设N是一个非空集合，满足以下条件：〔ⅰ〕对每一个n∈N，一定有唯一的一个N中的元素与之对应，这个元素记作n+,称为是n的后继元素〔或后继〕；〔ⅱ〕有元素e∈N，他不是N中任意元素的后继；〔ⅲ〕N中的任意一个元素至多是一个元素的后继，即从a+=b+ 一定可以推出a=b;(ⅳ)(归纳原理)设S是N的一个子集合，e∈S, 如果n∈S则必有n+ ∈S,那么，S=N.这样的集合N称为自然数集合，它的元素叫做自然数。
其中的归纳原理是我们常用的数学归纳法的基础。
数学归纳法在中学已属重点内容，此处就不作介绍。
主要描述一下推广状态下的第二种数学归纳法：〔第二种数学归纳法〕设P(n)是关于自然数n的一种性质或命题。
第一章 整除理论整除性理论是初等数论的基础。
本章要介绍带余数除法，辗转相除法，最大公约数，最小公倍数，算术基本定理以及它们的一些应用。
第一节 数的整除性定义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 ∣a 1x 1 + a 2x 2 + + 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 不是素数，那么它有两个以上的正的非平凡约数，设它们是d 1, d 2, , d k 。
不妨设d 1是其中最小的。
若d 1不是素数，则存在e 1 > 1，e 2 > 1，使得d 1 = e 1e 2，因此，e 1和e 2也是a 的正的非平凡约数。
这与d 1的最小性矛盾。
第一节 整数的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 即==证毕.。
