初等数论中的几个重要定理(竞赛必备)
初等数论中的几个重要定理
基础知识
定义（欧拉(Euler)函数）一组数称为是模的既约剩余系，如果对任意的，且对于任意的，若＝1，则有且仅有一个是对模的剩余，即。并定义
中和互质的数的个数，称为欧拉（Euler）函数。
这是数论中的非常重要的一个函数，显然
，而对于，就是1,2，…，中与互素的数的个数，比如说是素数，则有。
引理：；可用容斥定理来证（证明略）。
定理1：（欧拉（Euler）定理）设＝1，则。
分析与解答：要证，我们得设法找出个相乘，由个数我们想到中与互质的的个数：，由于＝1，从而也是与互质的个数，且两两余数不一样，故
（），而（）＝1，故。
证明：取模的一个既约剩余系
，考虑，由于与互质，故仍与互质，且有，于是对每个都能找到唯一的一个，使得，这种对应关系是一一的，从而
，。
，，故。证毕。
这是数论证明题中常用的一种方法，使用一组剩余系，然后乘一个数组组成另外一组剩余系来解决问题。
定理2：（费尔马（Fermat）小定理）对于质数及任意整数有。
设为质数，若是的倍数，则。若不是的倍数，则由引理及欧拉定理得
，，由此即得。
定理推论：设为质数，是与互质的任一整数，则。
定理3：（威尔逊（Wilson）定理）设为质数，则。
分析与解答：受欧拉定理的影响，我们也找个数，然后来对应乘法。
证明：对于，在中，必然有一个数除以余1，这是因为则好是的一个剩余系去0。
从而对，使得
；
若，，则，
，故对于，有。即对于不同的对应于不同的，即中数可两两配对，其积除以余1，然后有，使，即与它自己配对，这时，
，或，或。
除外，别的数可两两配对，积除以余1。故。
定义：设为整系数多项式（），我们把含有的一组同余式（）称为同余方组程。特别地，，当均为的一次整系数多项式时，该同余方程组称为一次同余方程组.若整数同时满足：
，则剩余类（其中
）称为同余方程组的一个解，写作
定理4：（中国剩余定理）设是两两互素的正整数，那么对于任意整数，一次
初等数论练习题一 一、填空题 1、τ(2420)=27；?(2420)=_880_ 2、设a ，n 是大于1的整数，若a n -1是质数，则a=_2. 3、模9的绝对最小完全剩余系是_{-4，-3，-2，-1，0，1，2，3，4}. 4、同余方程9x+12≡0(mod 37)的解是x ≡11(mod 37)。 5、不定方程18x-23y=100的通解是x=900+23t ，y=700+18t t ∈Z 。. 6、分母是正整数m 的既约真分数的个数为_?(m )_。 7 8、??? ??10365 =-1。 9、若p 是素数，则同余方程x p - 1 ≡1(mod p )的解数为二、计算题 1、解同余方程：3x 2+11x -20≡0 (mod 105)。 解：因105 = 3?5?7， 同余方程3x 2+11x -20≡0 (mod 3)的解为x ≡1 (mod 3)， 同余方程3x 2+11x -38 ≡0 (mod 5)的解为x ≡0，3 (mod 5)， 同余方程3x 2+11x -20≡0 (mod 7)的解为x ≡2，6 (mod 7)， 故原同余方程有4解。 作同余方程组：x ≡b 1 (mod 3)，x ≡b 2 (mod 5)，x ≡b 3 (mod 7)， 其中b 1 = 1，b 2 = 0，3，b 3 = 2，6， 由孙子定理得原同余方程的解为x ≡13，55，58，100 (mod 105)。 2、判断同余方程x 2≡42(mod 107)是否有解？ 11074217 271071107713231071107311072107 710731072107732107422110721721107213)(=∴-=-=-==-=-=-==??≡-?--?-）（）（）（）（），（）（）（）（），（）（））（）（（ ）（解： 故同余方程x 2≡42(mod 107)有解。 3、求（127156+34）28除以111的最小非负余数。
初等数论 初等数论从表面意义来讲，就是作为一门研究数的相关性质的数学学科。准确地按照潘承洞、潘承彪两位数论大师的说法：初等数论是研究整数最基本的性质，是一门十分重要的数学基础课。它不仅是中、高等师范院校数学专业，大学数学各专业的必修课，而且也是计算机科学等相关专业所需的课程。纵观数论发展过程，我国出现了许许多多的数论大师，如：华罗庚的早期研究方向、陈景润、潘承洞等。 第一部分：整除 初接触初等数论，经过《初等数论》课本知整除理论是初等数论的基础。整除理论首先涉及整除。现向上延伸则想到整除的对象，即自然数、整数。从小学、中学再到大学，我们从接触最初的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）当n=1时，P(1)不成立； （2）设n>1,若对所有的自然数m 《初等数论》作业 第一次作业： 一、单项选择题 1、=),0(b （ ）. A b B b - C b D 0 2、如果a b ，b a ，则( ). A b a = B b a -= C b a ≤ D b a ±= 3、如果1),(=b a ，则),(b a ab +=（ ）. A a B b C 1 D b a + 4、小于30的素数的个数（ ）. A 10 B 9 C 8 D 7 5、大于10且小于30的素数有（ ）. A 4个 B 5个 C 6个 D 7个 6、如果n 3，n 5，则15（）n . A 整除 B 不整除 C 等于 D 不一定 7、在整数中正素数的个数（ ）. A 有1个 B 有限多 C 无限多 D 不一定 二、计算题 1、求24871与3468的最大公因数? 2、求[24871,3468]=? 3、求[136,221,391]=? 三、证明题 1、如果b a ,是两个整数,0 b ,则存在唯一的整数对r q ,,使得r bq a +=,其中b r ≤0. 2、证明对于任意整数n ,数6 233 2n n n + +是整数. 3、任意一个n 位数121a a a a n n -与其按逆字码排列得到的数n n a a a a 121- 的差必是9的倍数. 4、证明相邻两个偶数的乘积是8的倍数. 第二次作业 一、单项选择题 1、如果( A ),则不定方程c by ax =+有解. A c b a ),( B ),(b a c C c a D a b a ),( 2、不定方程210231525=+y x （A ）. A 有解 B 无解 C 有正数解 D 有负数解 二、求解不定方程 1、144219=+y x . 解：因为（9，21）=3，1443，所以有解； 化简得4873=+y x ； 初等数论 1. 整除性质 a) 若a|b，a|c，则a|(b±c)。 b) 若a|b，则对任意c，a|bc。 c) 对任意非零整数a，±1|a，±a|a。 d) 若a|b，b|a，则|a|=|b|。 e) 如果a能被b整除，c是任意整数，那么积ac也能被b整除。 f) 如果a同时被b与c整除，并且b与c互质，那么a一定能被积bc整除，反 过来也成立。 g) 如果a∣b且b∣c，则a∣c。 h) 如果c∣a且c∣b，则c∣ua+vb，其中u，v是整数。 i) 对任意整数a，b，b>0，存在唯一的数对q，r，使a=bq+r，其中0≤r 2013年春西南大学《初等数论》作业及答案(共4次,已整理) 第一次作业 1、设n，m为整数，如果3整除n，3整除m，则9（）mn。 A：整除 B：不整除 C：等于 D：小于 正确答案：A 得分：10 2、整数6的正约数的个数是（）。 A：1 B：2 C：3 D：4 正确答案：D 得分：10 3、如果5|n ，7|n，则35（）n 。 A：不整除 B：等于 C：不一定 D：整除 正确答案：D 得分：10 4、如果a|b，b|a ，则（）。 A：a=b B：a=-b C：a=b或a=-b D：a，b的关系无法确定 正确答案：C 得分：10 5、360与200的最大公约数是（）。 A：10 B：20 C：30 D：40 正确答案：D 得分：10 6、如果a|b，b|c，则（）。 A：a=c B：a=-c C：a|c D：c|a 正确答案：C 得分：10 7、1到20之间的素数是（）。 A：1，2，3，5，7，11，13，17，19 B：2，3，5，7，11，13，17，19 C：1，2，4，5，10，20 D：2，3，5，7，12，13，15，17 正确答案：B 得分：10 8、若a，b均为偶数，则a + b为（）。 A：偶数 B：奇数 C：正整数 D：负整数 正确答案：A 得分：10 9、下面的（）是模12的一个简化剩余系。 A：0，1，5，11 B：25，27，13，-1 C：1，5，7，11 D：1，-1，2，-2 正确答案：C 得分：10 10、下面的（）是模4的一个完全剩余系。 A：9，17，-5，-1 B：25，27，13，-1 C：0，1，6，7 D：1，-1，2，-2 正确答案：C 得分：10 11、下面的（）是不定方程3x + 7y = 20的一个整数解。 A：x=0,y=3 B：x=2,y=1 C：x=4,y=2 D：x=2,y=2 正确答案：D 得分：10 12、设a,b,c,d是模5的一个简化剩余系，则a+b+c+d对模5同余于（）。 A：0 B：1 C：2 D：3 正确答案：A 得分：10 13、使3的n次方对模7同余于1的最小的正整数n等于（）。 A：6 B：2 欧拉定理 认识欧拉 欧拉，瑞士数学家，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 即欧拉示性数，已成为“拓扑学”的基础概念。那么什么是“拓扑学”？欧拉是如何发现这个关系的？他是用什么方法研究的？今天让我们沿着欧拉的足迹，怀着崇敬的心情和欣赏的态度探索这个公式...... 初等数论中的欧拉定理 初等数论中的几个重要定理(竞赛必备) 初等数论中的几个重要定理 基础知识 定义（欧拉(Euler)函数）一组数称为是模的既约剩余系，如果对任意的， 且对于任意的，若＝1，则有且仅 有一个是对模的剩余，即。并定义 中和互质的数的个数，称为欧 拉（Euler）函数。 这是数论中的非常重要的一个函数，显然， 而对于，就是1,2，…，中与互素的 数的个数，比如说是素数，则有。 引理：；可用容斥定理来证（证明略）。 定理1：（欧拉（Euler）定理）设＝1， 则。 分析与解答：要证，我们得设法找出个相乘，由个数我们想到中与 互质的的个数：，由于＝1，从而 也是与互质的个数，且两两余数 不一样，故 （），而（）＝1，故。 证明：取模的一个既约剩余系 ，考虑，由于与互质， 故仍与互质，且有 ，于 是对每个都能找到唯一的一个，使 得，这种对应关系是一一的，从而 ，。 ，，故。证毕。 这是数论证明题中常用的一种方法，使用一组剩余系，然后乘一个数组组成另外一组剩余系来解决问题。 定理2：（费尔马（Fermat）小定理）对于质数及任意整数有。 设为质数，若是的倍数，则。 若不是的倍数，则由引理及欧拉定理得 ，，由此即得。 定理推论：设为质数，是与互质的任 一整数，则。 定理3：（威尔逊（Wilson）定理）设为质数，则。 分析与解答：受欧拉定理的影响，我们也找个数，然后来对应乘法。 证明：对于，在中，必然有 一个数除以余1，这是因为则好是的 一个剩余系去0。 从而对，使得 ； 若，，则， ，故对于，有 。 即对于不同的对应于不同的，即中数可 两两配对，其积除以余1，然后有，使 ，即与它自己配对，这时， ，或，或。 除外，别的数可两两配对，积除以 余1。故。 定义：设为整系数多项式（），我们把 含有的一组同余式（）称为同 余方组程。特别地，，当均为的一次整系数多项式时，该同余方程组称为一次同余方程组.若整数同时满足： ，则剩余类（其中 ）称为同余方程组的一个解，写作 定理4：（中国剩余定理）设是两两 互素的正整数，那么对于任意整数，一次 “4-6 初等数论初步”简介 北京师范大学胡永建 初等数论是研究整数的性质和不定方程（组）的整数解的一门学问，它与几何学是最古老的两个数学分支。初等数论中至今仍有许多没有解决的问题，如哥德巴赫（Goldbach）问题，孪生素数猜想，奇完全数的存在性问题等，它们对人类智慧产生了极大挑战。人们在解决一些初等数论问题的过程中所作的贡献，对数论乃至整个数学的发展起了重要的推动作用，产生了一些直接与数学有关的新的重要数学分支。初等数论在计算机科学和信息工程中有许多重大的实际应用。在本专题中，同学们将通过具体的问题，学习初等数论的一些基本知识，如有关整数和整除的知识，用辗转相除法求解一次同余方程（组）和简单的一次不定方程等，初等数论中蕴含的一些思想方法，以及我国古代数学在初等数论的研究方面取得的一些重要成就。 一、内容与课程学习目标 本专题的学习初等数论的一些基本知识，具体包括：整数的整除、同余与同余方程、一次不定方程和数论在密码中的应用四部分内容。通过本专题的学习，要引导学生：1．通过实例，认识带余除法，理解同余和剩余类的概念及意义，探索剩余类的运算性质（加法和乘法），并且理解它的实际意义。体会剩余类运算与传统数的运算的异同（会出现零因子）。 2．理解整除、因数和素数的概念，了解确定素数的方法,如埃拉托斯特尼（Eratoshenes）筛法，知道素数有无穷多个。 3．了解十进制表示的整数的整除判别法，探索整数能被3，9，11，7等整除的判别法。会检查整数加法、乘法运算错误的一种方法,如弃九验算法。 4．通过实例，探索利用辗转相除法求两个整数的最大公约数的方法，理解互素的概念，并能用辗转相除法证明：若a能整除bc，且a,b互素，则a能整除c。探索公因数和公倍数的性质。了解算术基本定理。 5．通过实例，理解一次不定方程的模型，利用辗转相除法求解简单的一次不定方程。并尝试写出算法的程序框图，在条件允许的情况下上机实现。 6．通过实例（如物不知其数问题），理解一次同余方程组的模型。 7．理解大衍求一术和孙子定理的证明。 8．理解费马小定理（当m是素数时，a m-1≡1(mod m)）和欧拉定理（aφ(m)≡1(mod m),其中φ(m)是1，2，…，m-1中与m互素的数的个数）及其证明。 9．了解数论在密码中的应用——公开密钥。 二、内容安排 本专题共安排了四讲，其中最后一讲“数论在密码中的应用”可根据教学时间的实际情况机动安排，可由教师讲授，也可作为学生课后的阅读材料。本专题教学时间约需18课时，具体分配如下（仅供参考）： 第一讲整数的整除约5课时 一、整除的概念和性质约2课时 二、最大公因数与最小公倍数约2课时 第五节 初等数论中的几个重要定理 基础知识 定义（欧拉(Euler)函数）一组数s x x x ,,,21 称为是模m 的既约剩余系，如果对任意的s j ≤≤1，1),(=m x j 且对于任意的Z a ∈，若),(m a ＝1，则有且仅有一个j x 是a 对模m 的剩余，即)(mod m x a j ≡。并定义},,2,1{)(m s m ==?中和m 互质的数的个数，)(m ?称为欧拉（Euler ）函数。 这是数论中的非常重要的一个函数，显然1)1(=?，而对于1>m ，)(m ?就是1,2，…，1-m 中与m 互素的数的个数，比如说p 是素数，则有1)(-=p p ?。 引理：∏? =为质数）－（P |P 11)(m P m m ?；可用容斥定理来证（证明略）。 定理1：（欧拉（Euler ）定理）设),(m a ＝1，则)(mod 1)(m a m ≡?。 证明：取模m 的一个既约剩余系))((,,,,21m s b b b s ?= ，考虑s ab ab ab ,,,21 ，由于a 与m 互质，故)1(s j ab j ≤≤仍与m 互质，且有i ab )1(s j i ab j ≤<≤?，于是对每个 s j ≤≤1都能找到唯一的一个s j ≤≤)(1σ， 使得)(mod )(m b ab j j σ≡，这种对应关系σ是一一的，从而)(mod )(mod )(11)(1m b m b ab s j j s j j s j j ∏∏∏===≡≡σ，∴))(mod ()(11m b b a s j j s j j s ∏∏==≡。 1),(1=∏=s j j b m ，)(mod 1m a s ≡∴，故)(mod 1)(m a m ≡?。证毕。 分析与解答：要证)(mod 1)(m a m ≡?，我们得设法找出)(m ?个n 相乘，由)(m ?个数我们想到m ,,2,1 中与m 互质的)(m ?的个数：)(21,,,m a a a ? ，由于),(m a ＝1，从而)(21,,,m aa aa aa ? 也是与m 互质的)(m ?个数，且两两余数不一样，故)(21m a a a ???? ≡)(21,,,m aa aa aa ? ≡)(m a ?)(21m a a a ???? （m mod ），而 （)(21m a a a ???? m ）＝1，故)(mod 1)(m a m ≡?。 这是数论证明题中常用的一种方法，使用一组剩余系，然后乘一个数组组成另外一组剩余系来解决问题。 作业次数：学号姓名作业成绩 第0章序言及预备知识 第一节序言（1） 1、数论人物、资料查询：（每人物写600字左右的简介） （1）华罗庚 2、理论计算与证明： （1 是无理数。 （2）Show that there are infinitely many Ulam numbers 3、用Mathematica 数学软件实现 A Ulam number is a member of an which was devised by and published in in 1964. The standard Ulam sequence (the (1, 2-Ulam sequence starts with U 1=1 and U 2=2 being the first two Ulam numbers. Then for n > 2, U n is defined to be the smallest that is the sum of two distinct earlier terms in exactly one way 。 By the definition, 3=1+2 is an Ulam number; and 4=1+3 is an Ulam number (The sum 4=2+2 doesn't count because the previous terms must be distinct. The integer 5 is not an Ulam number because 5=1+4=2+3. The first few terms are 1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26, 28, 36, 38, 47, 48, 53, 57, 62, 69, 72, 77, 初等数论第一次作业 简答题 1. 叙述整数a被整数b整除的概念。 2. 给出两个整数a，b的最大公因数的概念。 3. 叙述质数的概念，并写出小于14的所有质数。 4. 叙述合数的概念，并判断14是否为合数。 5. 不定方程c +有整数解的充分必要条件是什么？ by ax= 6. 列举出一个没有整数解的二元一次不定方程。 7. 写出一组勾股数。 8. 写出两条同余的基本性质。 9. 196是否是3的倍数，为什么？ 10. 696是否是9的倍数，为什么？ 11. 叙述孙子定理的内容。 12. 叙述算术基本定理的内容。 13.给出模6的一个完全剩余系。 14.给出模8的一个简化剩余系。 15.写出一次同余式) ax≡有解得充要条件。 (mod m b 答： 1.设a,b是任意两个整数，其中b≠0，如果存在一个整数q使得等式a=bq 成立，我们就称b整除a或a被b整除,记做b|a。 2.设a,b是任意两个整数，若整数d是他们之中每一个的因数，那么d就叫做a,b的一个公因数。a,b的公因数中最大的一个叫做最大公因数。 3.一个大于1的整数，如果它的正因数只有1和它本身，就叫作质数(或素数)。14的所有质数为2,3,5,7,11,13 4.一个大于1的整数，如果它的正因数除了1和它本身，还有其他的正因数，则就叫作合数。14的所有正因数为1,2,7,14，除了1和本身14，还有2和7两个正因数，所以14是合数。 5.不定方程c ax= +有整数解的充分必要条件是。 by 6.没有整数解的二元一次不定方程10x+10y=5。 7.一组勾股数为3,4,5。 8.同余的基本性质为： 性质1 m为正整数，a，b，c为任意整数，则 ①a≡a（mod m）； 《初等数论》习题解答 作业3 一．选择题 1，B 2，C 3，D 4，A 二．填空题 1，自反律 2，对称性 3，13 4，十进位 5，3 6， 2 7，1 三．计算题 1， 解：由Euler 定理知：（a,m ）=1 则 a φ (m)≡1 (mod m) ∵(3,100)=1. 3φ (100)=340≡1 3360≡1 3364=3360×34≡34 (mod 100) ∴34≡81 (mod 100) 故：3364的末两位数是81. 2, 解：132=169≡4 （mod 5） 134=16≡1 (mod 5) 1316≡1 (mod 5) 1332≡1 (mod 5) 1348≡1 (mod 5) 1350=1348×132 1350≡132≡4 (mod 5) 3, 解： ∵(7,9)=1. ∴只有一个解 7X －5≡9Y (mod 9) 7X －9Y ≡5 (mod 9) 解之得：X=2，Y=1 ∴X=2+9≡11=2 (mod 9) 4, 解： ∵（24，59）=1 ∴只有一个解 24X ≡7 (mod 59) 59Y ≡﹣7 (mod 24) 11Y=﹣7 (mod 24) 24Z=7 (mod 11) 2Z=7 (mod 11) 11W=﹣7 (mod 2) W =﹣7 (mod 2) W=﹣1 (mod 2) Z=2 711+-= －2 Y=11 7242-?-=－5 X=247595+?-=2 288-=－12 =47(mod59) 5 解 ∵（45，132）=3，∴同余式有三个解。 45X ≡21（mod32） 15x ≡7 (mod44) 44y ≡-7 (mod15) 14y ≡-7 (mod15) 15z ≡-7 (mod14) z ≡7 (mod14) y= 14 7715-?=7 x=15 7744+?=21 ∴x=21+3 1322?=109 (mod132) x=21+31321?=65 (mod132) x=21 (mod132) 6、解 ∵（12，45）=3, ∴同余式有三个解。 4x+5≡0 (mod15) 4x ≡15y-5 由观察法：∴x=10, y=3 ∴x=10 (mod45) x=10+ 3 1×45=25 (mod45) x=10+32×45=40 (mod45) 7、解 37x=25 (mod107) 107y=-25 (mod37) 33y=-25 (mod37) 37z= -25 (mod37) 4z= 25 (mod37) 33w= -25 (mod37) w= -25 (mod37) w=3 z= 4 25333+?=31 y=33253137-?=33 1122=34 x=372534107+?=373633=99 ∴x=99 (mod321) 欧拉定理 ————————————————————————————————作者: ————————————————————————————————日期: 欧拉定理 认识欧拉 欧拉,瑞士数学家,1３岁进巴塞尔大学读书，得到著名数学家贝努利的精心指导．欧拉是科学史上最多产的一位杰出的数学家，他从19岁开始发表论文，直到7６岁,他那不倦的一生，共写下了886本书籍和论文，其中在世时发表了70０多篇论文。彼得堡科学院为了整理他的著作，整整用了４7年。欧拉著作惊人的高产并不是偶然的。他那顽强的毅力和孜孜不倦的治学精神,可以使他在任何不良的环境中工作:他常常抱着孩子在膝盖上完成论文。即使在他双目失明后的17年间,也没有停止对数学的研究,口述了好几本书和400余篇的论文。当他写出了计算天王星轨道的计算要领后离开了人世。欧拉永远是我们可敬的老师。欧拉研究论著几乎涉及到所有数学分支，对物理力学、天文学、弹道学、航海学、建筑学、音乐都有研究!有许多公式、定理、解法、函数、方程、常数等是以欧拉名字命名的。欧拉写的数学教材在当时一直被当作标准教程。19世纪伟大的数学家高斯（Gａuss，1７77-1855）曾说过“研究欧拉的著作永远是了解数学的最好方法”。欧拉还是数学符号发明者，他创设的许多数学符号，例如π,i，e,ｓｉn,cos，tｇ，Σ,ｆ(x)等等,至今沿用。欧拉不仅解决了彗星轨迹的计算问题,还解决了使牛顿头痛的月离问题。对著名的“哥尼斯堡七桥问题”的完美解答开创了“图论”的研究。欧拉发现，不论什么形状的凸多面体，其顶点数Ｖ、棱数E、面数F之间总有关系V+Ｆ－E＝2，此式称为欧拉公式。V+F-Ｅ即欧拉示性数，已成为“拓扑学”的基础概念。那么什么是“拓扑学”? 欧拉是如何发现这个关系的?他是用什么方法研究的?今天让我们沿着欧拉的足迹，怀着崇敬的心情和欣赏的态度探索这个公式．..．.. 初等数论中的欧拉定理 初等数论中的几个重要定理 基础知识 定义（欧拉(Euler)函数）一组数称为是模的既约剩余系，如果对任意的，且对于任意的，若＝1，则有且仅有一个是对模 的剩余，即。并定义中和互质的数的个数， 称为欧拉（Euler）函数。 这是数论中的非常重要的一个函数，显然，而对于，就是1,2，…，中与互素的数的个数，比如说是素数，则有。 引理：；可用容斥定理来证（证明略）。 定理1：（欧拉（Euler）定理）设＝1，则。 分析与解答：要证，我们得设法找出个相乘，由个数我们想到中与互质的的个数：，由于＝1，从而 也是与互质的个数，且两两余数不一样，故 （），而（）＝1，故。 证明：取模的一个既约剩余系，考虑，由于与互质，故仍与互质，且有，于是对每个都能找到唯一的一个，使得，这种对应关系 是一一的，从而，。 ，，故。证毕。 这是数论证明题中常用的一种方法，使用一组剩余系，然后乘一个数组组成另外一组剩余系来解决问题。 定理2：（费尔马（Fermat）小定理）对于质数及任意整数有。 设为质数，若是的倍数，则。若不是的倍数，则 由引理及欧拉定理得，，由此即得。 定理推论：设为质数，是与互质的任一整数，则。 定理3：（威尔逊（Wilson）定理）设为质数，则。 分析与解答：受欧拉定理的影响，我们也找个数，然后来对应乘法。 证明：对于，在中，必然有一个数除以余1，这是因为则好是的一个剩余系去0。 从而对，使得； 若，，则，，故对于，有。即对于不同的对应于不同的，即中数可两两配对，其积除以余1，然后有，使，即与它自己配对，这时，，或，或。 除外，别的数可两两配对，积除以余1。故。 定义：设为整系数多项式（），我们把含有的一组同余式 （）称为同余方组程。特别地，，当均为的一次整系数多项式时，该同余方程组称为一次同余方程组.若整数同时满足： ，则剩余类（其中）称为同余方程组的一个解，写作 定理4：（中国剩余定理）设是两两互素的正整数，那么对于任意整数，一次同余方程组，必有解，且解可以写为： 这里，，以及满足，（即为对模的逆）。 中国定理的作用在于它能断言所说的同余式组当模两两互素时一定有解，而对于解的形式并不重要。 定理5：（拉格郎日定理）设是质数，是非负整数，多项式 是一个模为次的整系数多项式（即），则同余方程至多有个解（在模有意义的情况下）。 定理6：若为对模的阶，为某一正整数，满足，则必为的倍数。 以上介绍的只是一些系统的知识、方法，经常在解决数论问题中起着突破难点的作用。另外还有一些小的技巧则是在解决、思考问题中起着排除情况、辅助分析等作用，有时也会起到 第三次作业答案： 一、选择题 1、整数5874192能被( B )整除. A 3 B 3与9 C 9 D 3或9 2、整数637693能被(C )整除. A 3 B 5 C 7 D 9 3、模5的最小非负完全剩余系是( D ). A -2,-1,0,1,2 B -5,-4,-3,-2,-1 C 1,2,3,4,5 D 0,1,2,3,4 4、如果)(mod m b a ≡,c 是任意整数,则（A ） A )(mod m bc ac ≡ B b a = C ac T )(m od m bc D b a ≠ 二、解同余式（组） （1）)132(mod 2145≡x . 解 因为(45,132)=3|21,所以同余式有3个解. 将同余式化简为等价的同余方程 )44(mod 715≡x . 我们再解不定方程 74415=-y x , 得到一解(21,7). 于是定理4.1中的210=x . 因此同余式的3个解为 )132(mod 21≡x , )132(mod 65)132(mod 3 13221≡+ ≡x , )132(mod 109)132(mod 3132221≡?+≡x . （2）)45(mod 01512≡+x 解 因为(12,45)=3|15,所以同余式有解,而且解的个数为3. 又同余式等价于)15(mod 054≡+x ,即y x 1554=+. 我们利用解不定方程的方法得到它的一个解是(10,3), 即定理4.1中的100=x . 因此同余式的3个解为 )45(mod 10≡x , )45(mod 25)45(mod 3 4510≡+≡x , )45(mod 40)45(mod 3 45210≡?+≡x . （3）)321 (m od 75111≡x . 解 因为(111,321)=3|75,所以同余式有3个解. 将同余式化简为等价的同余方程 )107(mod 2537≡x . 我们再解不定方程 2510737=+y x , 得到一解(-8,3). 于是定理4.1中的80-=x . 因此同余式的3个解为 )321(mod 8-≡x , )321(mod 99)321(mod 3 3218≡+-≡x , )321(mod 206)321(mod 3 32128≡?+-≡x . （4）?? ???≡≡≡)9(mod 3)8(mod 2)7(mod 1x x x . 解 因为(7,8,9)=1,所以可以利用定理5.1.我们先解同余式 )7(mod 172≡x ,)8(mod 163≡x ,)9(mod 156≡x , 得到)9(mod 4),8(mod 1),7(mod 4321-=-==x x x .于是所求的解为 ). 494(mod 478)494(mod 510 )494(mod 3)4(562)1(631472=-=?-?+?-?+??≡x （5）???????≡≡≡≡) 9(mod 5)7(mod 3)5(mod 2)2(mod 1x x x x . (参考上题) [编辑本段] 欧拉定理 1、初等数论中的欧拉定理： 对于互质的整数a和n，有a^φ(n) ≡ 1 (mod n) 证明： 首先证明下面这个命题： 对于集合Zn={x1,x2,...,xφ(n)},其中xi(i=1,2,…φ(n))是不大于n且与n互素的数，即n的一个化简剩余系，或称简系，或称缩系)，考虑集合S = {a*x1(mod n),a*x2(mod n),...,a*xφ(n)(mod n)} 则S = Zn 1) 由于a,n互质，xi也与n互质，则a*xi也一定于p互质，因此 任意xi，a*xi(mod n) 必然是Zn的一个元素 2) 对于Zn中两个元素xi和xj，如果xi ≠ xj 则a*xi(mod n) ≠ a*xi(mod n)，这个由a、p互质和消去律可以得出。 所以，很明显，S=Zn 既然这样，那么 （a*x1 × a*x2×...×a*xφ(n)）(mod n) = （a*x1(mod n) × a*x2(mod n) × ... × a*xφ(n)(mod n)）(mod n) = （x1 × x2 × ... × xφ(n)）(mod n) 考虑上面等式左边和右边 左边等于(a*（x1 × x2 × ... × xφ(n)）) (mod n) 右边等于x1 × x2 × ... × xφ(n)）(mod n) 而x1 × x2 × ... × xφ(n)(mod n)和n互质 根据消去律，可以从等式两边约去，就得到： a^φ(n) ≡ 1 (mod n) 推论：对于互质的数a、n，满足a^(φ(n)+1) ≡ a (mod n) 费马定理: a是不能被质数p整除的正整数，则有a^(p-1) ≡ 1 (mod p) 证明这个定理非常简单，由于φ(p) = p-1，代入欧拉定理即可证明。 同样有推论：对于不能被质数p整除的正整数a，有a^p ≡ a (mod p) 2、平面几何里的欧拉定理： （1）(Euler定理)设三角形的外接圆半径为R，内切圆半径为r，外心与内心的距离为d，则d2=R2-2Rr． 证明：如右下图，O、I分别为⊿ABC的外心与内心． 2016年西南大学初等数论第四次作业 证明题 1． 设n 是整数，证明6 | n (n + 1)(2n + 1)。 证明：n (n + 1)(2n + 1) = n (n + 1)(n – 1) + n (n + 1)(n + 2)。 n (n + 1)(n – 1)是三个连续整数的积，n (n + 1)(n + 2)也是三个连续整数的积， 而三个连续整数的积可被6整除， 所以6 | n (n + 1)(n – 1)，6 | n (n + 1)(n + 2)。 由整出的性质可得6 | n (n + 1)(2n + 1)。 2． 设n 是整数，证明：n n -3|6。 证明：)1)(1(3+-=-n n n n n 。 由于)1)(1(+-n n n 是3个连续整数的积，所以n n -3|3。 由于)1(-n n 是2个连续整数的积，所以n n -3|2。 又（2,3）= 1，所以 n n -3|6。 3． 设x ，y 均为整数。证明：若y x 2|7+，则y x 610|7+。 证明：)2(37610y x x y x ++=+，因为y x 2|7+，所以)2(3|7y x +, 因为7|7，所以7|7x ，从而)2(37|7y x x ++，所以y x 610|7+ 4． 设x ，y 均为整数。证明：若y x 9|5+，则y x 78|5+。 证明：y y x y x 65)9(878-+=+。因为y x 9|5+，所以)9(8|5y x +。 又因为5|65，所以5|65y 。从而y y x 65)9(8|5-+，所以y x 78|5+。 5.设x 是实数，n 是正整数，证明：?? ????=??????n x n x ][。 欧拉定理99617 欧拉定理 认识欧拉 欧拉，瑞士数学家，13岁进巴塞尔大学读书，得到著名数学家贝努利的精心指导．欧拉是科学史上最多产的一位杰出的数学家，他从19岁开始发表论文，直到76岁，他那不倦的一生，共写下了886本书籍和论文，其中在世时发表了700多篇论文。彼得堡科学院为了整理他的著作，整整用了4 7年。欧拉著作惊人的高产并不是偶然的。他那顽强的毅力和孜孜不倦的治学精神，可以使他在任何不良的环境中工作：他常常抱着孩子在膝盖上完成论文。即使在他双目失明后的17年间，也没有停止对数学的研究，口述了好几本书和400余篇的论文。当他写出了计算天王星轨道的计算要领后离开了人世。欧拉永远是我们可敬的老师。欧拉研究论著几乎涉及到所有数学分支，对物理力学、天文学、弹道学、航海学、建筑学、音乐都有研究！有许多公式、定理、解法、函数、方程、常数等是以欧拉名字命名的。欧拉写的数学教材在当时一直被当作标准教程。19世纪伟大的数学家高斯（Gau ss，1777-1855）曾说过“研究欧拉的著作永远是了解数学的最好方法”。欧拉还是数学符号发明者，他创设的许多数学符号，例如π，i，e，sin，co s，tg，Σ，f (x)等等，至今沿用。欧拉不仅解决了彗星轨迹的计算问题，还解决了使牛顿头痛的月离问题。对著名的“哥尼斯堡七桥问题”的完美解答开创了“图论”的研究。欧拉发现，不论什么形状的凸多面体，其顶点数V、棱数E、面数F之间总有关系V+F-E=2，此式称为欧拉公式。V+F-E即欧拉示性数，已成为“拓扑学”的基础概念。那么什么是“拓扑学”？欧拉是如何发现这个关系的？他是用什么方法研究的？今天让我们沿着欧拉的足迹，怀着崇敬的心情和欣赏的态度探索这个公式...... 初等数论中的欧拉定理 定理内容 在数论中，欧拉定理（也称费马-欧拉定理）是一个关于同余的性质。欧拉定理表明，若n,a为正整数，且n,a互素，(a,n) = 1，则 a^φ(n) ≡ 1 (mod n) 证明 首先证明下面这个命题： 对于集合Zn={x1,x2,...,xφ(n)},其中xi(i=1,2,…φ(n))是不大于n且与n 互素的数，即n的一个化简剩余系，或称简系，或称缩系)，考虑集合S = {a *x1(mod n),a*x2(mod n),...,a*xφ(n)(mod n)} 则S = Zn 1) 由于a,n互质，xi也与n互质，则a*xi也一定于p互质，因此 任意xi，a*xi(mod n) 必然是Zn的一个元素 最新文件---------------- 仅供参考--------------------已改成-----------word 文本 --------------------- 方便更改 第七讲 费马小定理与欧拉定理 2017.12.18 基础例题 1. 设n 是自然数，则n n n n 4321|5+++/ 2.设{x 1，x 2，x 3，…，()m x ?}为模m 的一个简化剩余系，则()()()mod 1321≡?m x x x x ? 3. 设a ，b ，c ，m 为自然数，m >1，(b ，m )=1，且()m b a mod 1≡， ()m b c mod 1≡，记()c a d ,=，则()m b d mod 1≡ 4. 设p 是素数，p |b n -1，n 为自然数，则下列两个结论中至少有一个成立： (1)p |b d -1对于某个因数d 6. 将612-1分解质因数 7. 若a ，b 是任意整数，p 为素数.证明：()()p b a b a p p p mod +≡+ 8. 设p 为奇素数，a ，n 都是正整数，且p n |a p -1. (1)证明：p n -1|a -1； (2)当p =2时，上述结论成立吗? 10. 求(1237156+34)28被111除的余数. 11. 设p 是一个大于5的素数，求证：240|p 4-1 12. 设p 为素数.证明：存在无穷多个正整数n 使得()p n n mod 2≡ 13.(1)证明下列事实但不许用费马小定理：若p 是质数，h 1，h 2，…，h n 是整数，则(h 1+h 2+…+h n )p ≡h 1p +h 2p +…+h n p (mod p ) (2)由(1)证明费马定理，然后再由费马定理证明欧拉定理. 每周真题小练 1. (ELMO 2017)设H 为三角形ABC 的垂心，M 为边BC 的中点.以AH 为直径的圆上，有相异的两点P ，Q (P 、Q 两点均不与A 重合)，满足M 位于直线PQ 上.证明：三角形APQ 的垂心位于三角形ABC 的外接圆上. 2.(命题人讲座) 设n 是一个大于1的奇数，数a 1，a 2，a 3，…，()n a ?是1，2，3，…，n 中与n 互素的所有正整数.证明()()n n k k n a ??π2 1cos 1=∏=初等数论作业
初等数论定理
2013年春_西南大学《初等数论》作业及答案(共4次_已整理)
欧拉定理
初等数论中的几个重要定理(竞赛必备)
“4-6 初等数论初步”简介
第五节初等数论中的几个重要定理
初等数论练习册汇总
西南大学2016《初等数论》网上作业(共4次)
初等数论习题解答
欧拉定理
初等数论中的几个重要定理高中数学竞赛
初等数论作业(3)答案
欧拉定理
2016年初等数论第四次作业答案
欧拉定理99617知识讲解
.12.15初等数论费马小定理与欧拉定理(优选.)
相关主题
文本预览