初等数论-学生1

初等数论大纲要求•同余，欧几里得除法，裴蜀定理，完全剩余系，不定方程和方程组，高斯函数[x]，费马小定理，格点及其性质，无穷递降法*，欧拉定理*，孙子定理*。第一节同余定义•数论中的重要概念。给定一个正整数m，如果两个整数a和b满足（a-b）能够被m整除，即（a-b）/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(modm)。对模m同余是整数的一个等价关系。•最先引用同余的概念与符号者为德国数学家高斯。同余理论是初等数论的重要组成部分，是研究整数问题的重要工具之一，利用同余来论证某些整除性的问题是很简便的。同余是数学竞赛的重要组成部分。性质•(1)若a≡0(modm),则m|a;•(2)a≡b(modm)等价于m|(a-b)•1反身性a≡a(modm)•2对称性若a≡b(modm)，则b≡a(modm)•3传递性若a≡b(modm)，b≡c(modm)，则a≡c(modm)•4同余式相加若a≡b(modm)，c≡d(modm)，则a±c≡b±d(modm)•5同余式相乘若a≡b(modm)，c≡d(modm)，则ac≡bd(modm)•4线性运算如果a≡b(modm)，c≡d(modm),那么(1)a±c≡b±d(modm)，(2)a*c≡b*d(modm)•5除法若ac≡bc(modm)c≠0则a≡b(modm/gcd(c,m))其中gcd(c,m)表示c,m的最大公约数•特殊地,gcd(c,m)=1则a≡b(modm)•6幂运算如果a≡b(modm)，那么a^n≡b^n(modm)7若a≡b(modm)，n|m,则a≡b(modn)•8若a≡b(modmi)(i=1,2...n)则a≡b(mod[m1,m2,...mn])其中[m1,m2,...mn]表示m1,m2,...mn的最小公倍数余数定理：n=km+r(0≤r≤m-1)•一个整数n被正整数m除后，余数r有m种情形：0，1，2，3，…，m-1，•它们彼此对模m不同余。这表明，每个整数恰与这m个整数中某一个关于模m同余。•这样一来，按关于模m是否同余对整数集进行分类，可以将整数集分成m个两两不相交的子集。•我们把（所有）对模m同余的整数构成的一个集合叫做模m的一个剩余类。•确切地说，若m是一个给定的正整数,则全体整数可以分成m个集，记作A0,A1,…Ai,...,Am-1,其中Ai是由一切形如km+i(k∈Z)的整数所组成的集。剩余类的性质•①每一个整数必包含在而且仅包含在上述一个集合里。②两个整数同在一个集合的充分必要条件是它们对模□同余。•例如.•模12的剩余类，为12个集合：•{...,0,12,24,36,...}•{...,1,13,25,37,...}•{...,2,14,26,38,...}•....•{...,11,23,35,47...}完系•完系,是同余中的一个特殊情况.一般叫做模……的完系。（如：模m的完系）•模m的完系是指有m个互不相等的数，模m的余数分别不相等。则这m个数被叫做模m的完系。•在模n的剩余类中各取一个元素，则这n个数就构成了模n的一个完全剩余系。完系的性质（1）完系的性质（2）完系的性质（3）简系•如果一个模m的剩余类Kr中任一数与m互质,则称Kr是与模m互质的剩余类;在与模m互质的每个剩余类中任取一个数(共f(m)个)所组成的数组,称为模m的一个简化剩余系,简称简系。•简系是同余理论中的概念.•缩系也叫简系（简化剩余系）。•例如，模n的简化剩余系就是小于n且与n互素的整数的集合。•例1：模10的简化剩余系为1，3，7，9。•例2：模30的简化剩余系为1，7，11，13，17，19，23，29。•模n的简化剩余系中元素的个数为φ(n)（既欧拉函数）简系的性质•【定理1】x1,x2,...,xφ(m)是模m的简系的充要条件是(x,m)=1且x,xj不同余于m(i≠j,i,j=1,2,...,φ(m)).•【定理2】在模m的一个完系中,取出所有与m互质的数组成的数组就是一个模m的简系.•【定理3】若(a,m)=1,且x1,x2...,xφ(m)是模的简系,则模ax1,ax2,...,axφ(m)也是模m的简系.•费马小定理(FermatTheory)是数论中的一个重要定理，•其内容为：假如p是质数，且gcd(a,p)=1，那么a(p-1)≡1（modp）验证推导•引理1．若a,b,c为任意3个整数,m为正整数,且(m,c)=1,则当ac≡bc(modm)时,有a≡b(modm)证明：ac≡bc(modm)可得ac–bc≡0(modm)可得(a-b)c≡0(modm)因为(m,c)=1即m,c互质,c可以约去,a–b≡0(modm)可得a≡b(modm)•引理2．设m是一个整数,且m1,b是一个整数且(m,b)=1.如果a1,a2,a3,a4,…am是模m的一个完全剩余系,则ba1,ba2,ba3,ba4,…bam也构成模m的一个完全剩余系.证明：若存在2个整数bai和baj同余即bai≡baj(modm),根据引理1则有ai≡aj(modm),根据完全剩余系的定义可知这是不可能的,•所以ba1,ba2,ba3,ba4,…bam构成模m的一个完全剩余系.费马小定理的证明•构造素数p的既约剩余系{0,1,2,…,p-1}•因为(a,p)=1,由引理2可得{0,a,2a,…,(p-1)a}也是p的一个既约剩余系。•由同余的性质有1·2·3·…·(p-1)≡1a·2a·3a·…·(p-1)a•(p-1)!≡(p-1)!an-1(modp)•易知((p-1)!,p)=1，同余式两边可约去(p-1)!，得到•ap-1≡1(modm),这样就证明了费马小定理。•9欧拉定理•设a,m∈N,(a,m)=1,则aφ(m)≡1(modm)•(注:φ(m)指模m的简系个数，•φ(m)=m-1,如果m是素数；•一般的φ(m)=m(1-1/q1)(1-1/q2)...(1-1/qn))•m=q1r1q2r2...qnrn欧拉简介•莱昂哈德·欧拉（LeonhardEuler，1707年4月15日～1783年9月18日），瑞士数学家，13岁进巴塞尔大学读书，得到著名数学家贝努利的精心指导．•欧拉是科学史上最多产的一位杰出的数学家，他从19岁开始发表论文，直到76岁，•他那不倦的一生，共写下了886本书籍和论文，其中在世时发表了700多篇论文。•彼得堡科学院为了整理他的著作，整整用了47年。•欧拉著作惊人的高产并不是偶然的。•他那顽强的毅力和孜孜不倦的治学精神，可以使他在任何不良的环境中工作：他常常抱着孩子在膝盖上完成论文。•即使在他双目失明后的17年间，也没有停止对数学的研究，口述了好几本书和400余篇的论文。•当他写出了计算天王星轨道的计算要领后离开了人世。•欧拉永远是我们可敬的老师。•欧拉研究论著几乎涉及到所有数学分支，对物理力学、天文学、弹道学、航海学、建筑学、音乐都有研究！•有许多公式、定理、解法、函数、方程、常数等是以欧拉名字命名的。•欧拉写的数学教材在当时一直被当作标准教程。•19世纪伟大的数学家高斯（Gauss，1777-1855）曾说过“研究欧拉的著作永远是了解数学的最好方法”。•欧拉还是数学符号发明者，他创设的许多数学符号，例如π，i，e，sin，cos，tg，Σ，f(x)等等，至今沿用。•欧拉不仅解决了彗星轨迹的计算问题，还解决了使牛顿头痛的月地问题。•对著名的“哥尼斯堡七桥问题”的完美解答开创了“图论”的研究。•欧拉发现，不论什么形状的凸多面体，其顶点数V、棱数E、面数F之间总有关系V+F-E=2，此式称为欧拉公式。V+F-E即欧拉示性数，已成为“拓扑学”的基础概念。欧拉定理的证明•将1~n中与n互质的数按顺序排布：x1,x2……xφ(n)（显然，共有φ(n)个数）•我们考虑这么一些数：ax1,ax2,…,axφ(n)•1）这些数中的任意两个都不模n同余，•2）这些数除n的余数都与n互质，•故ax1ax2…axφ(n)≡x1x2…xφ(n)(modn)•aφ(n)x1x2…xφ(n)≡x1x2…xφ(n)(modn)•显然(n,x1x2…xφ(n))=1，故可约去•所以aφ(n)≡1(modn)欧拉定理的应用•首先看一个基本的例子。令a=3，n=5，这两个数是互素的。比5小的正整数中与5互素的数有1、2、3和4，所以φ(5)=4。计算:aφ(n)=34=81，而81=80+1≡1(mod5)。与定理结果相符。•这个定理可以用来简化幂的模运算。•比如计算7222的个位数，实际是求7222被10除的余数。(7,10)=1，且φ(10)=4。由欧拉定理知74≡1(mod10)。所以7222=(74)55*(72)≡15572≡49≡9(mod10)。欧拉发现的几何定理•1)设三角形的外接圆半径为R，内切圆半径为r，外心与内心的距离为d，则d^2=R^2-2Rr．•2)三角形ABC的垂心H，九点圆圆心V,重心G,外心O共线，称为欧拉线欧拉拓扑公式•V+F-E=X(P)，V是多面体P的顶点个数，F是多面体P的面数，E是多面体P的棱的条数，X(P)是多面体P的欧拉示性数。•如果P可以同胚于一个球面（可以通俗地理解为能吹胀成一个球面），那么X(P)=2，如果P同胚于一个接有h个环柄的球面，那么X(P)=2-2h。•X(P)叫做P的拓扑不变量，是拓扑学研究的范围。•例：足球表面由五边形和六边形的皮革拼成，计算一共有多少个这样的五边形和六边形？•答：足球是多面体，满足欧拉公式F－E+V=2，•设足球表面正五边形(黑皮子)和正六边形(白皮子)的面各有x个和y个，那么•面数F=x+y•棱数E=(5x+6y)/2（每条棱由两块皮子共用）•顶点数V=(5x+6y)/3（每个顶点由三块皮子共用）•由欧拉公式，x+y－(5x+6y)/2+(5x+6y)/3=2，•解得x=12。所以，共有12块黑皮子•黑皮子一共有12×5=60条棱，这60条棱都是与白皮子缝合在一起的•白皮子所有边的一半是与黑皮子缝合在一起的•那么白皮子就应该一共有60×2=120条边，120÷6=20•所以共有20块白皮子威尔逊定理•在初等数论中，威尔逊定理给出了判定一个自然数是否为素数的充分必要条件。即：当且仅当p为素数时：(p-1)!≡-1(modp)，•充分性•如果“p”不是素数，那么它的正因数必然包含在整数1,2,3,4,…,p−1中，因此gcd((p−1)!,p)1，所以我们不可能得到(p−1)!≡−1(modp)。必要性•若p是素数,取集合A={1,2,3,...p-1};则A构成模p乘法的缩系,即任意i∈A,存在j∈A,使得:•(ij)≡1(modp)那么A中的元素是不是恰好两两配对呢?不一定,但只需考虑这种情况•x^2≡1(modp)•解得:x≡1(modp)或x≡p-1(modp)•其余两两配对;故而•(p-1)!≡1﹡(p-1)≡-1(modp)拉格朗日定理•拉格朗日定理存在于多个学科领域中，分别为：流体力学中的拉格朗日定理；微积分中的拉格朗日定理；数论中的拉格朗日定理；群论中的拉格朗日定理。•数论中的拉格朗日定理•1、拉格朗日四平方和定理(费马多边形数定理特例)•每个自然数均可表示成4个平方数之和。3个平方数之和不能表示形式如4^k(8n+7)的数。如果在一个正整数的因数分解式中，没有一个数有形式如4k+3的质数次方，该正整数可以表示成两个平方数之和。•2、设p是一个素数，f(x)是整系数多项式，模p的次数为n，则同余方程f(x)≡0（modp）至多有n个互不相同（即模p互不同余）的解。复数中的欧拉定理•e^(ix)=cosx+isinx，e是自然对数的底，i是虚数单位。•它将三角函数的定义域扩大到复数，建立了三角函数和指数函数的关系，它在复变函数论里占有非常重要的地位。•将公式里的x换成-x，得到：e^(-ix)=cosx-isinx，•sinx=[e^(ix)-e^(-ix)]/(2i)，cosx=[e^(ix)+e^(-ix)]/2.•这两个