郭学军--初等数论

《郭学军--初等数论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数论讲义郭学军南京大学数学系guoxj@nju.edu.cnx1引言数论是纯粹数学的一个分支，主要讨论数，特别是整数的性质。数论在众多的学科中都有体现，并且在实际生活中也有重要的应用。有据可查的数论研究开始于公元前17世纪的古巴比伦。是数学发展史上，数论一直是核心数学的重要内容。x2数的同余假设b,c∈Z，非零m∈N。如果a

2、(b−c),那么我们称b,c模m同余，记为b≡c(modm).m叫做模，b叫做c模m的剩余。例如：−9≡16(mod5).注意这里的b,c是整数，而不能是分数。但是如果bc≡1(modm),我们也常常把b记为1/c

3、.给定a,a模m的所有的剩余（我们称之为一个剩余类）都形如a+km,k∈Z.定理2.1.假设m是一个正整数，A,a是任意两个整数，则a,a+1,...,a+m−1中有且恰有一个模m同余于A.1因此对任一整数A,都有它的一个模m剩余位于集合{0,1,2,...,m−1}中。这样的集合我们成称为是模m的一个完全剩余系。任何一个含有m个元素的整数集合{a0,...,am1}，如果其中的元素模m两两不同。我们都称它是一个完全剩余系。命题2.2.如果A≡a(modm),B≡b(modm)，那么AB≡ab(modm).假设f(x)是一个整系数的多

4、项式。如果a≡b(modm),那么f(a)≡f(b)(modm).假设m是一个正整数，我们定义φ(m)为1,2,...,m−1中与m互素的元素的个数。我们称φ(m)为欧拉函数。如果一个含有φ(m)个元素的整数集合S={a1,...,aφ(m)}中的元素模m两两不同，而且都和m互素，我们就称S是模m的一个缩系。定理2.3.假设m是一个正整数,a和m互素.则aφ(m)≡1(modm).证明.假设S={a1,...,aφ(m)}是模m的一个缩系。那么T={aa1,...,aaφ(m)}也是模m的一个缩系。所以两个缩系中的元素乘起来以后模m是相

5、同的。所以aφ(m)≡1(modm).例子2.4.十进制整数an···a1能够被9整除当且仅当an+···+a1能够被9整除。十进制整数a···a能够被11整除当且仅当a−a+a−a+···+(−1)(n1)a能n11234n够被11整除。x3素数和整除只能被1和其自身整除的整数称为是素数。例如2,3,5,7,11,...注意1不是素数，普林斯顿大学的著名数学家Conway认为应该修改素数的定义，使得−1是一个素数。同时注意2是一个素数，数学界有句名言所有的素数都是奇的,2是最奇的.这主要是因为素数2相比于其他的素数有很多独特的性质。

6、已知的最大的素数是243112609−12写成十进制的共有12978189位，是2008年8月23日发现的。制作素数表可用埃拉托色尼筛法。寻找大素数主要是出于军事和商业的需要，因为大素数对制作安全的密码至关重要。在这里我们会简单的介绍一些RSA算法，P和NP问题，还有印度数学家Agrawal的工作。x4算术基本定理算术基本定理出现在欧几里得《几何原本》中.算术基本定理是极其重要的一个定理，是整个数论的基础。我们将在课堂上给出详细的证明。定理4.1.设p是一个素数，a,b是两个正整数，而且p>a,p>b.则p-ab.定理4.2.设p是一个

7、素数，a,b是两个正整数。如果p

8、ab,则p

9、a或者p

10、b.定理4.3.设p是一个素数。如果p

11、a1···an,则存在i使得p

12、ai.定理4.4(算术基本定理).每个大于1的自然数均可写为素数的积，而且这些素因子按大小排列之后，写法仅有一种方式。√例子4.5.2是无理数。例子4.6.lg2=log102是无理数。x5中国剩余定理在中国古代著名数学著作《孙子算经》中，有这样一道叫做“物不知数”的题目，“有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？”中国数学家秦九韶于1247年做出了完整的解答，口诀如下：“三人同行七十

13、希，五树梅花廿一支，七子团圆正半月，除百零五便得知”定理5.1.假设n1,...,nk是两两互素的正整数，则对于任意的整数a1,...,ak,同余方程x≡a1(modn1),...x≡ak(modnk).有模N=n1···nk惟一的解。其推广的形式为3定理5.2.假设n1,...,nk是两两互素的正整数，则对于任意的整数a1,...,ak,同余方程x≡a1(modn1),...x≡ak(modnk).有解当且仅当最大公因子(ni,nj)

14、(ai−aj).对任意的i̸=j成立。有解的时候，解模N=[n1

15、,...,nk]（最小公倍数）惟一。注意我们这里的解都是一次的，如果是高次的同余方程，那么求解非常困难，而且没有固定的方法。x6有限域初步假设p是一个固定的素数。我们在这一节中只考虑由集合{0,1,2,..