最大公因数与辗转相除法.doc

学院

学 术 论 文

题 目:最大公因数与辗转相除法
学号：
学校：
专业：
班级：
姓名：
指导老师：
时间：

【摘要】：文章先介绍最大公因数的一些性质和求法以及在解决实际问题的应用，再提出一些例子，进一步理解最大公因数。然后介绍质数的一些定义，相关的定理和现在的情况。最后介绍辗转相除法，并且用辗转相除法来求最大公因数，把三者结合起来。
【关键词】:最大公因数;互质;辗转相除法；

引言
1.最大公因数
1.1最大公因数的定义：

整数a1,a2,a3,……..an的公因数中最大的一个叫做最大公因数记作（a1,a2,a3,……..an），若（a1,a2,a3,……..an）=1，我们说a1,a2,a3,……..an互质或互素
1.2 以求20、30和36的最大公因数为例，我们先来计算这三个数的最大公因数
1.2.1 列举法
20的因数有：1、2、4、5、10、20
30的因数有：1、2、3、5、6、10、15、30
36的因数有：1、2、3、4、6、9、12、18、36
三个数的最大公因数是2
1.2.2 分解质因数的方法
20=2×2×5
30=2×5×3
36=2×2×3×3
[20，30，36]=2×2×3×5×3=180
1.2.3短除的方法

（20，30，36）=2
[20，30，36]=2×2×3×5×3=180
1.2.4小结：在计算三个数的最大公因数和最小公倍数的时候，最大公因数要找三个数的公有的质因数，如果其中的两个商还有质因数的话，也不要往下除。
1.3最大公约数的性质。
例. 求18和24的最大公约数
（1）用分解质因数的方法独立完成

（18，24）=2×3=6
[18，24]=2×3×3×2×2=72
（2）观察发现：18×24=4×72
（3）小结：
两个自然数的最大公约数的一个重要的性质是：两个自然数的乘积等于这两个自然数的最大公约数和最小公倍数的乘积。
若a、b表示两个自然数，则 a×b=（a，b）×[a，b]
例. 两个数的最大公约数是6，最小公倍数是504，如果其中的一个数是42，那么另一个数是多少？
分析与解答：根据ab=（a，b）×[a，b] 又知a=42 则
1.4.利用最大公因数解决实际问题。
例. 有320个苹果，240个橘子，200个梨，用这些果品，最多可以分成多少份同样的物？在每份的礼物中，苹果、橘子和梨各有多少个？
分析：根据题目的要求，在分礼物的时候必须正好分尽3样果品。因此，礼物的份数必须是320、240和200的公因数，现在还要求最多可以分成多少份同样的礼物，也就是说要求320、240和200的最大公因数。
解答：

（320，240，200）=2×2×2×5=40
因此，最多可以分成40份，每份礼物中有苹果320÷40=8（个），橘子240÷40=6（个），梨200÷40=5（个）
2质数

2.1.1质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。换句话说，只有两个正因数（1和自己）的自然数即为素数。比1大但不是素数的数称为合数。1和0既非素数也非合数。素数在数论中有着很重要的地位
2.1.2　　算术基本定理： 任何大于1的正整数n可以唯一表示成有限个素数的乘积: n=p_1p_2...p_s, 这里p_1≦p_2 ≦...≦p_s是素数【1】。
　　这一表达式也称为n的标准分解式。
　　算术基本定理是初等数论中最基本的定理。由此定理， 我们可以重新定义两个整数的最大公因子和最小公倍数等等概念。
　　1不能称作素数，是因为要确保算术基本定理所要求的唯一性成立。这一解释可参看华罗庚《数论导引》【2】
2.2素数分布问题，就是指素数在正整数集或其特殊子集中的分布情况，比如素数个数问题等等。这方面的结果如下;
　　2.2.1欧几里得以反证法证明了素数个数无限；欧拉利用解析方法也证明了此结论。
　　2.2.2高斯提出著名的素数定理（当时是猜想，后被证明）： 设π(x)是不超过x的素数个数， 那么极限(x趋向于无穷)
　　lim π(x)/(x/Ln x)=1
　　更好的逼近公式有高斯提出的li(x)函数， 即lim π(x)/lix=1。
　　2.2.3 狄利克雷 证明了任何等差数列： a, a+d,a+2d,...a+nd,... (这里a,d互质)中都包含无限个素数。
　　2.2.4 兰伯特猜想（已被证明）： 在n和2n之间必定存在一个素数， 这里n是大于1的正整数。
3．辗转相除法

3.1.1. 方法介绍：　辗转相除法又叫做欧几里德除法，是求最大公约数的另一种方法。具体做法是：用较小数除较大数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。
　3.1.2辗转相除法的算理是根据：在a=bq+r，中，除数b和余数r能被同一个数整除，那么被除数a也能被这个数整除。或者说，除数与余数的最大公约数，就是被除数与除数的最大公约数；如果反过来说，被除数与除数的最大公约数，就是除数与余数的最大公约数。
3.1.3. 用辗转相除法计算两个数的最大公约数。
用辗转相除法求两个数的最大公约数的步骤如下：
先用小的一个数除大的一个数，得第一个余数，再用第一个余数除小的一个数，得到第二个余数；又用第二个余数除第一个余数，得第三个余数，这样逐次用后一个余数去除前一个余数，直到余数是0为止。那么最后一个除数就是所求的最大公约数（如果最后的余数是1，那么原来的两个数互质）。
例. 求792和1134的最大公约数。
1134÷792=1……342
792÷342=2……108
342÷108=3……18
108÷18=6 （没有余数）
∴（792，1134）= 18
用辗转相除法在短除计算两个数的最大公约数有困难的时候，效果尤其显著。
参考文献（1）
【1】，闵嗣鹤，严士键编.初等数论[M] 北京：高等教育出版社，2003.12，第3版
【2】华罗庚，数论导引【M】，人民邮电出版社， 1957年出版，第五版

参考文献（2）
欧几里得，希腊文：Ευκλειδης ，约公元前330年—前275年），古希腊数学家，被称为“几何之父”。他活跃于托勒密一世（公元前323年－前283年）时期的亚历山大里亚，他最著名的著作《几何原本》是欧洲数学的基础，提出五大公设，发展欧几里得几何，被广泛的认为是历史上最成功的教科书。欧几里得也写了一些关于透视、圆锥曲线、球面几何学及数论的作品,是几何学的奠基人
　 狄利克雷，德国数学家。对数论、数学分析和数学物理有突出贡献，是解析数论的创始人之一。1805年2月13日生于迪伦，1859年5月5日卒于格丁根。中学时曾受教于物理学家G.S.欧姆；1822～1826年在巴黎求学，深受J.-B.-J.傅里叶的影响 。回国后先后在布雷斯劳大学、柏林军事学院和柏林大学任教27年，对德国数学发展产生巨大影响。1839年任柏林大学教授，1855年接任C.F.高斯在哥廷根大学的教授职位

Most GongYinShu and Euclidean algorithm
Tuwenluo Science and Technology Department of Mathematics, Jiangxi Normal 330038
Abstract: Article first introduces some of the biggest GongYinShu in nature and method to solve practical problems and puts forward some examples of application, and further understanding GongYinShu maximum. Then some of the definition, prime related theorem and now. Finally, and introduced Euclidean algorithm using Euclidean algorithm to get the best GongYinShu, the combination.
Key words: the maximum GongYinShu, Co-prime, Euclidean algorithm
6