本科生基础课 初等数论讲义 华东师范大学数学系 2018
前言这本讲义尝试按照代数几何的观点来介绍初等数论的经典内容初等数论的重要内容之一就是研究低次数不定方程的整数解或者有理数解。从代数几何的观点看，就是研究底次平面曲线上的整数点或者有理点．我们希望以解方程为主线，逐步展开内容，将初等数论的各个知识点与方程联系统一起来．另一方面，我们还希望在教学过程中突出算法的重要性，比如辗转相除法、连分数方法、椭圆曲线的加法运算等等，这样可以让学生更好地掌握初等数论这门课程的精髓
目录目录第一章导读11.1一些记号说明11.2初等数论的主线一求解不定方程本章习题.3第二章4一次不定方程2.1整除与素数.42.2公因子和欧几里得算法.52.2.1公因子52.2.2欧几里得算法，72.3算术基本定理.92.3.19算术基本定理2.3.2应用(I)：最大公因子的素因子分解算法.102.3.3应用(II)：最小公倍数的素因子分解算法102.3.4应用(II)：一些无理数的判定.11132.3.5应用(IV)：素数个数无限的证明2.4一次不定方程，152.4.1二元一次不定方程的求解算法..152.4.2多元一次不定方程的求解算法，172.5同余式，202.5.1同余与完全剩余系202.5.223既约剩余类与欧拉定理。2.5.3些简单的应用25282.5.4欧拉函数的公式算法，2.6一次同余方程(组），302.6.1一元一次同余方程的求解算法，302.6.2多元一次同余方程的求解算法，332.6.3同余方程组与孙子定理：36本章习题39第三章二次不定方程413.1勾股方程及其算法，413.1.1数论证明。423.1.2解析几何证明423.1.3椭圆或双曲线上的有理点，43453.1.4应用：四次费马方程平方剩余及其算法3.2463.2.1勒让德符号与欧拉定理473.2.2应用(I)：威尔逊定理493.2.3应用（II)：模素数二次同余式求解算法503.2.4高斯引理.51-ii-
目录3.2.5二次互反律533.2.6应用（III)：梅森素数的判别.563.2.7雅克比符号....573.2.860般情形的二次同余式的求解算法，平方和问题3.3613.3.1费马-欧拉定理623.3.2高斯整数.633.3.3补充材料：华林问题简介663.4佩尔方程与连分数算法673.4.1连分数的基础知识，673.4.269渐近分数的逼近，3.4.3循环连分数723.4.4佩尔方程的求解算法75本章习题77第四章三次不定方程794.1椭圆曲线上的群结构794.280有理点的算法，4.3同余数.814.4费马大定理与椭圆曲线824.5圆锥曲线与二次不定方程.84本章习题85第五章86高次不定方程5.1高次同余方程的解数865.2Wolstenholme 定理.885.3原根与指标..895.3.1原根的存在性895.3.2指标.905.3.3应用(1)：威尔逊定理的新证明925.3.492应用(II)：正多边形尺规作图问题5.4k次剩余94本章习题95参考文献97-ili-
第一章导读第一章导读1.1一些记号说明为方便讨论，我们这里规定一些记号(1)整数集Z :={0,±1,±2,±3...}(2）正整数集Z+ :=(nezIn>0](3)非负整数集N := Z+ u (0).(4)有理数集Q=p,qEZ,q0q(5)取整函数：对任何实数，以[国表示不超过a的最大整数，它也称为a的整数部分比如[2.6] = 2,[0] = 0, [-2.3] =-3,[-3] =-3,[V2] = 1,[-V2] = -2.的小数部分定义为[α] := a - []容易看到,0≤a<1,因而[]≤a<[a]+1.1.2初等数论的主线一求解不定方程初等数论的主要研究对象就是整数和有理数，对它们的研究，主要是通过求解某些特殊的方程作为主线来展开的事实上，你会发现许多重要的经典数学课程都围绕着”解方程”这一主题比如解析几何就是研究方程的几何图形：线性代数则研究线性方程：抽象代数最早是从研究代数方程的可解性发展起来的（我们熟知的尺规作图问题等都与此有关...因此这本讲义也将按照求解方程的主线来介绍初等数论首先让我们回忆一下，在平面解析几何中，人们主要关心以下多项式方程在平面中所描绘的曲线，C: f(a,y) =0比如直线和圆锥曲线（椭圆、双曲线、抛物线）等等定义1.2.1如果曲线C上的点p=（a,y）的分量a,y都是有理数，我们就称p是C的有理点.如果分量，y都是整数，我们就称P是C的整数点-1-
第一章导读般说来，曲线C上的有理点和整数点是非常稀少的，有时甚至没有！数论的主要任务之一就是要求出曲线C上的有理点或整数点当我们只关心有理点或者整数点的时候，方程f(z,y)=0通常就被称为丢香图方程或者不定方程。我们的初等数论主要关心如何求出直线和圆锥曲线等的有理点或整数点.此外我们也可以考虑变量更多次数更高的不定方程或者不定方程组当我们说，求一个不定方程（组)的整数解或有理解时，就相当于说（从几何角度看），寻找这个方程定义的几何图形上的整数点或者有理点下面我们将逐一简要介绍这本讲义所关心的各类重要的不定方程（组）问题1.2.1求线性方程组的整数解（α1*，n）：a11i+a1222+:+ainan=b1A2121+a222+..+a2nTn=b2...am12i+am22+..*+amnn =bm这里诸ai,b；EZ.这一方程的求解将会引出初等数论中的整除理论和同余理论问题1.2.2求解单位圆周上的有理点（a,y)：2+y?= 1或者等价地，我们要求勾股方程X?+ y? = z2的整数解(X,Y,Z)此外，也希望求解圆周方程a?+y=d的整数解(a,y)，此处d是给定整数这些方程的求解将会涉及到近世代数中的一部分内容一事实上，近世代数的许多内容只不过是初等数论的推广问题1.2.3求解双曲线上的整数点(,9)：a2- dy2-1,此处d是给定的正整数，该不定方程也称为佩尔方程，我们将用连分数的方法来巧妙求解问题1.2.4解抛物线上的整数点(r,y)：r2 py = q,此处P，9是给定的正整数该不定方程也称为二次剩余问题或平方剩余问题.这个问题将会引出是初等数论中最引人入胜的内容之一一高斯的二次互反律注 1.2.1上面的三个问题本质上都是寻找圆锥曲线上的整数点或有理点我们也可以研究更一般的不定方程Ar?+2Bry+Cy?=D,-2-
第一章导读这里A.B.C.D是给定整数.这个方程将引出二次型理论和闵可夫斯基的“数的几何”，不过限于-本书的篇幅，我们只能简要介绍其中的部分内容问题1.2.5求解三次方程的有理数解（r,9)：y?=a3+ar+b.这一方程定义的曲线称作椭圆曲线，我们将介绍一种巧妙的计算方法，可以从已知的有理点构造出新的有理点，此外，作为应用，我们将介绍著名的同余数问题等等。问题1.2.66求高次方程的整数解(r,y)：anrn + an-1an-1 +.+aia + ao = py,这里诸aiPEZ.这一方程的求解在近世代数中有不同程度的推广。数论中还有许许多多著名的不定方程问题，其中一些至今未能解决我们这里不再一一赞述，读者将会在此后的章节中看到更多的不定方程的介绍本章习题加*号的习题表示有一定难度习题1.1证明以下各结论：(1)[国]≤a0, [ry],[g], [3] 之间有什么关系吗?(6)画出y=[a]和y=(a}的图像(7）对任何实数O,aEZ,[-a] + [a] --1, a&Z.（8*）（厄尔米特恒等式）对任何实数恒有：++"=[m]图+++++m-3-
第二章一次不定方程第二章量一次不定方程以下如无特别声明，a,d,c.等均指整数2.1整除与素数最简单的不定方程就是求br=a,b≠0(2-1)的整数解：如果该方程有整数解，我们就称b整除a，或称α被b整除，并记作a「b：否则就称b不整除a,记作bta.显然，alb等价于说是整数.例 2.1.112,3(-6),35,(-2)1.命题2.1.1设a,b,ceZ,bc≠0，我们有(1)（传递性）若ba且c|b,则c|a;(2)（自反性)b|b;(3)（消去律）bc|ac当且仅当b|a;(4)(万有性)±1a且b0;(5）（序关系）若b|c,则[≤cl;(6）（加性）若ca,c/b,则对任何m,nEZ,都有cl（am+bm)证明月(1)-(4)是显然的，留给读者验证.(5)设=号.因为b[c且bc≠0,所以是非零整数.因而cl=≥[6].(6)设=,y=。由命题条件，a,yeZ.因此am+bn=am+yneZ,c即 c I (am + bn).-由命题2.1.1（5）以下的常用结论推论2.1.1设ab是正整数，若ab且ba,则a=b定义2.1.1设b「a（要求b≠0)，我们称b是a的因子，a是b的倍数．进一步，如果11是整数.如果p没有真因子，我们就称p是素数；否则就称合数-4-
第二章一次不定方程正整数中最前面的素数分别是2,3,5,7,11,13,17,19,23,29,31,37,.其中2是唯一的偶素数命题2.1.2设n>1是整数，则n必可分解为素数的乘积n=q1q2**qk这里诸i是素数（允许相同)证明对n施归纳法：n=2时是显然的.今假设0.如果c[a并且c|b,我们就称c是a和b的公因子所有公因子中的最大者称作最大公因子，记作gcd(a,b)，或简记作(a,b)。如果(a,b)=1,我们就称a,b是互质的(也称互素)-例2.2.1(2, 4) = 2, (2,3) = 1, (-4, -6) = 2.注 2.2.1我们也可以用方程的语言来叙述公因子的定义，即如果方程组[cr=a,(cy=b-存在整数解（a,y)，则称c是a和b的公因子进一步，我们也可以归纳地定义n个整数a1，an的最大公因子(al, ++,an) := ((al,+,an-1),an).以下我们将介绍求最大公因子的算法.为此需要先对最大公因子的一些基本性质做一些了解，首先，我们回顾基础算术中的带余数除法-5-
第二章一次不定方程引理2.2.1（带余数除法）设a,bEZ,b>0,则存在唯一的整数g,r，使得a=qb+r，并且0≤r<b.r称为余数，q称为商，证明(1)存在性.令q=[号],r=a-bq.由第1.1节(5)的讨论，我们有0≤r=α-bq=b(-(1) <b.(2)唯一性，设a=q6’+是另一满足条件的式子.我们有(-Q)6=一7两边取绝对值得Id-ql -b==r因为≤r,rb,所以0-<b.这就推出0≤q-1,因而迫使=,故得■r=r.■注2.2.2b|a也可以等价定义为：a除以b的余数为零考虑整数集合中的特殊子集Za.b=(am+bn /m,n EZ)引理2.2.22(1)（零元)0EZa,b;(2)（封闭性）对任何a,yEZa,b,s,tEZ,都有st+tyEa,b证明(1)取m=-b,n=a,则0=am+bmez-(②)直接验算即得引理2.2.3设d=amo+bno是Ea,b中最小的正整数(1) d = (a,b):(2)对任何aEZa.b,都有da;(3)设c是a,b的任一公因子，则c|d证明(1)因为(a,b)|a,(a,b)b,故由命题2.1.1(6)立知(a, b) I d(= amo + bno).因此由命题2.1.1(5)推出(a,b)≤d.另一方面，设a=dg+r(0≤r<d)是带余数除法.我们有r = a-dg= a(1-qmo) +b(-qno) eZa.bd的最小性迫使r=0,即d|a.同理可证d|b.因此d是a和b的公因子。由最大公因子的定义得d≤(a,b).这就证明了d=(a,b).(2)显然.-(3)因ca.cb,故由命题2.1.1 (6)知cd(=amo+bmo)推论2.2.1存在a,yEZ,使得ar+by=(a,b)注2.2.3我们将在推论2.2.4中给出计算上述，y的方法-6-