资源描述：
《最大公因数与辗转相除法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、学院学术论文题目:最大公因数与辗转相除法学号：学校：专业：班级：姓名：指导老师：时间：6【摘要】：文章先介绍最大公因数的一些性质和求法以及在解决实际问题的应用，再提出一些例子，进一步理解最大公因数。然后介绍质数的一些定义，相关的定理和现在的情况。最后介绍辗转相除法，并且用辗转相除法来求最大公因数，把三者结合起来。【关键词】:最大公因数;互质;辗转相除法；引言1.最大公因数1.1最大公因数的定义：整数a1,a2,a3,……..an的公因数中最大的一个叫做最大公因数记作（a1,a2,a3,……..an），若（a1,a2,a3,……..an）=1，我们说a1,a2,a3,……..a
2、n互质或互素1.2以求20、30和36的最大公因数为例，我们先来计算这三个数的最大公因数1.2.1列举法20的因数有：1、2、4、5、10、2030的因数有：1、2、3、5、6、10、15、3036的因数有：1、2、3、4、6、9、12、18、36三个数的最大公因数是21.2.2分解质因数的方法20=2×2×530=2×5×336=2×2×3×3[20，30，36]=2×2×3×5×3=1801.2.3短除的方法6（20，30，36）=2[20，30，36]=2×2×3×5×3=1801.2.4小结：在计算三个数的最大公因数和最小公倍数的时候，最大公因数要找三个数的公有的质因
3、数，如果其中的两个商还有质因数的话，也不要往下除。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.利用最大公因数
4、解决实际问题。例.有320个苹果，240个橘子，200个梨，用这些果品，最多可以分成多少份同样的物？在每份的礼物中，苹果、橘子和梨各有多少个？分析：根据题目的要求，在分礼物的时候必须正好分尽3样果品。因此，礼物的份数必须是320、240和200的公因数，现在还要求最多可以分成多少份同样的礼物，也就是说要求320、240和200的最大公因数。解答：6（320，240，200）=2×2×2×5=40因此，最多可以分成40份，每份礼物中有苹果320÷40=8（个），橘子240÷40=6（个），梨200÷40=5（个）2质数2.1.1质数又称素数。指在一个大于1的自然数中，除了1和此
5、整数自身外，没法被其他自然数整除的数。换句话说，只有两个正因数（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
6、.2素数分布问题，就是指素数在正整数集或其特殊子集中的分布情况，比如素数个数问题等等。这方面的结果如下; 2.2.1欧几里得以反证法证明了素数个数无限；欧拉利用解析方法也证明了此结论。 2.2.2高斯提出著名的素数定理（当时是猜想，后被证明）：设π(x)是不超过x的素数个数，那么极限(x趋向于无穷) limπ(x)/(x/Lnx)=1 更好的逼近公式有高斯提出的li(x)函数，即limπ(x)/lix=1。 2.2.3狄利克雷证明了任何等差数列：a,a+d,a+2d,...a+nd,...(这里a,d互质)中都包含无限个素数。6 2.2.4兰伯特猜想（已被证明）：
7、在n和2n之间必定存在一个素数，这里n是大于1的正整数。3．辗转相除法3.1.1.方法介绍： 辗转相除法又叫做欧几里德除法，是求最大公约数的另一种方法。具体做法是：用较小数除较大数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。 3.1.2辗转相除法的算理是根据：在a=bq+r，中，除数b和余数r能被同一个数整除，那么被除数a也能被这个数整除。或者说，除数与余数的最大公约数，
