简述最大公约数(辗转相除法)的原理
2016.08
已知整数x, y，且x>y，它们的最大公约数为z=f(x,y)。那么有：ax+by
z
=k其中a,b,k∈常数
辗转相除法的列表如下(假设)：
x,y,m,….,P,Q,0
令n=x%y余m. 那么有
x=n?y+m
m=x?n?y
由ax+by
z =k可知m
z
=x?n?y
z
=k2（k2是一个常数）,也就是说它们的
余数也能被最大公约数整除，如此辗转迭代，直到余数为0的时候，说明那么上面的列表可以成
x,y,m,k1?z,k2?z, ….,k n?z,z,0注意，根据取余运算的性质，我们容易得到k n是单调递减，当第一次出现余数为0的时候，说明最大公约数出现了!
§1.2 最大公约数与辗转相除法
§2 最大公约数与辗转相除法 一、有关概念 1、定义：123,,,...,n a a a a 的公因数， ()123,,,...,n a a a a 及()123,,,...,1n a a a a = 2、说明：1公因数不可能是0；1是必然的公因数； 2 0与非零数b 的公因数就是b 的因数； 3两两互质与互质的关系； 4 (,)(,)a b b a = 5(0,)b b = ； (1,)1b = 6若(,)a b b =，则b ∣a 7若12(,)1a a =，则()123,,,...,1n a a a a = 3、定理：123,,,...,n a a a a 与123,,,...,n a a a a 相同的公因数。 ? ()123,,,...,n a a a a =123(,,,...,)n a a a a 4、求最大公因数的方法： 1观察法； 2短除法；3辗转相除法。
二、辗转相除法 定理1：设,,a b c 是不全为0的整数，且a bq c =+，q 为整数 则（1）,a b 与,b c 有相同的公因数； （2）()(),,a b b c = 定理2：设,a b 为正整数，则(),n a b r = 推论：,a b 的公因数与(),a b 的因数相同。 例1 证明:当n N +∈时， 143 214 n n ++为既约的真分数。 例2 求()1859,1573-及()169,121 例3 某数除193余4，除1087余7，求符合要求的最大整数。 例4 某数除300，262，205余数相同，求这个数。 三、最大公因数的性质 1、()(),,am bm a b m m =为正整数 2、() ,,a b a b δδδδ?? = ??? 为,a b 的公因数 3、()(),1,,a b a b a b ??= ? ??? 4、设()122,a a d =， ()233,d a d =，()1,n n n d a d -= 则()123,,,n n a a a a d = 例5 设(),1a b = ，求(),a b a b +-
用短除法求最大公因数和最小公倍数教案资料
《用短除法求最大公因数和最小公倍数》 教学设计 马官镇中心学校教师姚娟设计理念 本课是人教版第四单元《分数的意义和性质》中《最大公因数》和《最小公倍数》的内容，我把两个内容融合在一起进行对比教学，是为了让学生更加清楚地理解“求最大公因数和最小公倍数的方法及算理”，引导学生在教师讲授、学生自主参与、发现、归纳的基础上熟练地用短除法去求几个数的最大公因数和最小公倍数。 教学内容 用短除法求最大公因数和最小公倍数的方法。 教学目标 1.知识与能力： 理解最大公因数和最小公倍数的意义，学会用短除法求两个或三个数的最大公因数和最小公倍数的方法，掌握算理。 2.过程与方法： 在探索求最大公因数和最小公倍数的过程中，经历观察、猜测、归纳等数学活动，进一步发展初步的推理能力。 3.情感态度价值观：
在探索交流的学习过程中，使学生获得成功的体验，激发学生的学习兴趣。 教学重点 求两个数的最大公因数和最小公倍数的方法、算理。 教学难点 求三个数的最大公因数和最小公倍数的方法、算理。 教学准备 多媒体课件 教学过程： 课前播放音乐：《快乐的节日》 与学生交流：同学们，喜欢这首歌吗？知道歌名吗？它叫《快乐的节日》，老师愿你们天天快乐！让我们快乐地进入今天的数学课堂吧！ 一、复习导入 1.什么是最大公因数？（课件出示） 指名生答后，课件出示最大公因数的概念：两个或多个整数公有因数中最大的一个。 2.什么是最小公倍数？（课件出示） 指名生答后，课件出示最小公倍数的概念：几个整数的公倍数中最小的
那个数叫做这几个数的最小公倍数。 3.用例举法求12和18的最大公因数。（课件出示） 先让学生说说，然后老师归纳, 12的因数有：1、2、3、4、6、12. 18的因数有：1、2、3、6、18. 12和18的公因数有：1、2、3、6。其中6是12和18 的最大公因数。 问：同学们，这样做，你们不觉得麻烦吗？还会用其他方法求吗？ 生1:筛选法； 生2：短除法 师：这三种方法，哪种方法更简便些？ 师：用这三种方法都可以，但是，老师觉得用短除法来求最大公因数比较简便些，这节课我们就一起来学习用短除法求最大公因数和最小公倍数。板书课题：用短除法求最大公因数和最小公倍数。 【设计理念】通过提问，让学生了解什么是最大公因数和最小公倍数，为后面的学习做好铺垫；用列举法求12和18的最大公因数，让学生感觉这种方法有点麻烦，用短除法求最大公因数和最小公倍数比较简便，从而引出课题。 二、探索新知
辗转相除法求最大公约数和最小公倍数及其c语言实现
又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法。它是已知最古老的算法, 其可追溯至3000年前。 在数学中，辗转相除法，又称欧几里得算法，是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》（第VII卷，命题i 和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。 两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相减法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。例如，252和105的最大公约数是21（252 = 21 ×12；105 = 21 × 5）；因为252 ? 105 = 147，所以147和105的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时，所剩下的还没有变成零的数就是两数的最大公约数。由辗转相除法也可以推出，两数的最大公约数可以用两数的整数倍相加来表示，如21 = 5 ×105 + (?2) × 252。这个重要的等式叫做贝祖等式。 简单的想法 设两数为a、b(a>b)，b最大公约数(a，b)的步骤如下： 用b除a，得a=bq......r1(0≤r1)。若r1=0，则(a，b)=b； 若r1≠0，则再用r1除b，得b=r1q......r2 (0≤r2).若r2=0，则(a，b)=r1， 若r2≠0，则继续用r2除r1,……如此下去，直到能整除为止。其最后一个非零除数即为(a，b)。
设两数为a、b(b 辗转相除算法的简介 在数论中，辗转相除法（国际上一般称为Euclidean Algorithm 或Euclid's Algorithm，即欧几里得算法）是一种求任意两个欧几里得环（Euclidean Domain）中的单位（如：整数）的最大公约数的算法。这个算法的一个重要特点就是其不需要通过分解因式来求取最大公约数。辗转相除法正因为其易操作性与易实现性而成为了计算机编程中的一个重要的求最大公约数的常用算法。 辗转相除法的过程描述与应用 给出两个自然数a 和b：检查b是否为0；如果是，则a为最大公约数。如果不是，则分别用b和a 除b的余数作为上一步中的 a 和 b重复这一检查步骤。 正如上面所提到的，辗转相除法是编程中求最大公约数的常用算法，那么下面就是一个C++中通过递归实现辗转相除法的程序段范例： [cpp]view plaincopy 1.int gcd(int a, int b) 2.{ 3.return b == 0 ? a : gcd(b, a % b); 4.} 注：过程名设为gcd是为了更明显的标明这段程序的意图。因为gcd 是greatest common divisor （最大公约数）的缩写。再编写辗转相除法求最大公约数的过程是，最好将其命名为gcd 以方便他人日后阅读。 辗转相除法的证明 设两数为a、b(a > b)，求它们最大公约数的步骤如下： 设q = a / b，r = a % b, 得a＝bq＋r（0≤r＜b）。 1)若r = 0, 则b是a和b的最大公约数。 2)若r≠0,则继续考虑。首先，应该明白的一点是任何a 和b 的公约数都是r 的公约数。要想证明这一点，就要考虑把r 写成r=a-bq。现在，如果a 和b 有一个公约数d，而且设a=sd , b=td, 那么r = sd-tdq = (s-tq)d。因为这个式子中，所有的数（包括s-tq )都为整数，所以r 可以被d 整除。对于所有的d 的值，这都是正确的；所以a 和b 的最大公约数也是b 和r 的最大公约数。因此我们可以继续对b 和r 进行上述取余的运算。 . 1、查找约数法． 先分别找出每个数的所有约数，再从两个数的约数中找出公有的约数，其中最大的一个就是最大公约数． 例如，求12和30的最大公约数． 12的约数有：1、2、3、4、6、12； 30的约数有：1、2、3、5、6、10、15、30． 12和30的公约数有：1、2、3、6，其中6就是12和30的最大公约数． 2 更相减损术 《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。” 翻译成现代语言如下： 第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。 第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。 则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。 其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。 3、辗转相除法． 当两个数都较大时，采用辗转相除法比较方便．其方法是： 以小数除大数，如果能整除，那么小数就是所求的最大公约数．否则就用余数来除刚才的除数；再用这新除法的余数去除刚才的余数．依此类推，直到一个除法能够整除，这时作为除数的数就是所求的最大公约数． 例如：求4453和5767的最大公约数时，可作如下除法． 5767÷4453＝1余1314 4453÷1314＝3余511 1314÷511＝2余292 511÷292＝1余219 292÷219＝1余73 219÷73＝3 于是得知，5767和4453的最大公约数是73． 辗转相除法适用比较广，比短除法要好得多，它能保证求出任意两个数的最大公约数．4、求差判定法． 如果两个数相差不大，可以用大数减去小数，所得的差与小数的最大公约数就是原来两个数的最大公约数．例如：求78和60的最大公约数．78－60＝18，18和60的最大公约数是6，所以78和60的最大公约数是6． 如果两个数相差较大，可以用大数减去小数的若干倍，一直减到差比小数小为止，差和小数的最大公约数就是原来两数的最大公约数．例如：求92和16的最大公约数．92－16＝76，76－16＝60，60－16＝44，44－16＝28，28－16＝12，12和16的最大公约数是4，所以92和16的最大公约数就是4． 5、分解因式法． 先分别把两个数分解质因数，再找出它们全部公有的质因数，然后把这些公有质因数相乘，得到的积就是这两个数的最大公约数． 例如：求125和300的最大公约数．因为125＝5×5×5，300＝2×2×3×5×5，所以125和300的最大公约数是5×5＝25． 6、短除法． 为了简便，将两个数的分解过程用同一个短除法来表示，那么最大公约数就是所有除数的乘积． 例如：求180和324的最大公约数． 因为： 5和9互质，所以180和324的最大公约数是4×9＝36． 7、除法法． 当两个数中较小的数是质数时，可采用除法求解．即用较大的数除以较小的数，如果能够整除，则较小的数是这两个数的最大公约数． 例如：求19和152，13和273的最大公约数．因为152÷19＝8，273÷13＝21．（19和13都是质数．）所以19和152的最大公约数是19，13和273的最大公约数是13． 《辗转相除法》教学设计 一．教材分析 本节课是人教版必修三第一章《算法初步》第三节《算法案例》的第一课时，作为案例课，在整章中既是算法的总结，又是一个提升。教材突出了数学的人文价值，又为学生提供了探索算法的平台。二．学情分析 本节课的教授对象是高一学生，他们已经具备一定的数学基础和编程能力，已经掌握了用短除法求最大公约数的方法。现在学习辗转相除法，学生能够掌握辗转相除法的步骤，但是在具体做法的理解上并不到位，需要合作探究。 三．教学目标 1. 知识与技能目标： （1）理解辗转相除法的原理，能用辗转相除法求两正整数的最大公约数； （2）能读懂辗转相除法的程序框图，并能写出对应的程序语句。 2. 过程与方法目标：在学习辗转相除法的过程中，对比短除法，体会辗转相除法的优势，及其体现的化归思想。 3. 情感态度价值观： （1）通过辗转相除法的应用，提升计算能力，提高运算准确性。（2）通过程序的实际操作来体会算法的实用性、便捷性和高效性。四．教学重点和难点 1. 重点：辗转相除法的步骤及算法的理解。 2. 难点：辗转相除法的原理的理解，及辗转相除法的算法的理解。 五．预设问题：如何理解辗转相除法的原理。 六．预习反馈：1.为什么除数与余数的公约数也是被除数与除数的公约数？（1、2、6、8、9组） 2.为什么最后一步的除数为最大公约数？（1、3、6、8组） 3.怎样理解辗转相除法的算法？（3、5、11组） 七．教学课时：1课时 八．教学方法：依据“大三步”教学模式，以问题及问题链为主线，调动学生的学习积极性，使学生真正参与到课堂中，通过小组合作探究，充分的展示自己。 九．教学手段：利用多媒体辅助教学，可以降低学生的学习难度、增加课堂容量。 十．教学过程 （一）创设情景，引入课题 1.首先提出问题：在小学，我们已经学过求最大公约数的知识，你能求出18与24的公约数吗？ 2.进一步提出问题，如果用短除法求6757 与8729的最大公约数，可不可以行，方不方便？如果公约数比较大而且根据我们的观察又不能得到一些公约数，我们又应该怎样求它们的最大公约数？ （二）展示反馈问题 1.为什么除数与余数的公约数也是被除数与除数的公约数？ 最大公约数和最小公倍数怎么求？ 首先把两个数的质因数写出来，最小公倍数等于它们所有的质因数的乘积（如果有几个质因数相同，则比较两数中哪个数有该质因数的个数较多，乘较多的次数）。 比如：求45和30的最小公倍数。 45=3*3*5 30=2*3*5 不同的质因数是2,3,5。3是他们两者都有的质因数，由于45有两个3，30只有一个3，所以计算最小公倍数的时候乘两个3. 最小公倍数等于2*3*3*5=90 又如：计算36和270的最小公倍数。 36=2*2*3*3 270=2*3*3*3*5 不同的质因数是5。2这个质因数在36中比较多，为两个，所以乘两次；3这个质因数在270个比较多，为三个，所以乘三次。 最小公倍数等于2*2*3*3*3*5=540 最大公约数和最小公倍数<练习题> 1．有一级茶叶96克，二级茶叶156克，三级茶叶240克，价值相等．现将这三种茶叶分别等分装袋（均为整数克），每袋价值相等，要使每袋价值最低应如何装袋？ 2．a、b两数的最大公约数是12，已知a有8个约数，b有9个约数，求a与b． 3．两个数的积是6912，最大公约数是24，求：（1）它们的最小公倍数；（2）满足已知条件的自然数是哪几组？ 4．甲、乙、丙三个学生定期向某老师求教，甲每4天去一次，乙每6天去一次，丙每9天去一次，如果这一次他们三人是3月23日都在这个老师家见面，那么下一次三人都在这个老师家见面的时间是几月几日？ 5．求被5除余2，被6除余3，被7除4的大于1000、小于1500的所有自然数． 6．某个数与36的最大公约数是12，与36的最小公倍数是180，求这个数． 7．有三个自然数a、b、c，a与b的最大公约数是2；b和c的最大公约数是4；a和c的最大公约数是6；a、b、c三个数的最小公倍数是60，求这三个数的最小的和是多少？ 答案仅供参考： 1．三种数量不等的茶叶价值相等，等分装袋后，每袋价值仍相等，由于每种茶叶的总价值相等，每袋价值也要相等，所以这三种茶叶分装的袋数也一定相同．为了使每袋价值最低，就应使袋数尽可能多， 用迭代法求两个数的最大公约数和最小公倍数 化工09110605 摘要：迭代法是一种循环控制语句和循环结构程序的设计方法。在计算机解决问题的时候，总希望从复杂的问题中找到规律，并归结为简单问题的重复，发挥其擅长重复运算的特点，让它重复执行一组语句，直到满足给定条件为止。因此，c语言提供了重复操作的语句，由这些语句构成的程序称为循环结构。本文就是采用迭代法，利用c语言中提供的重复语句，求得两个数的最大公约数和最小公倍数。 关键词：循环语句；循环结构；迭代法；最大公约数和最小公倍数 Iterative Method with the greatest common divisor and least common multiple of two numbers Chemical 09110605 W ANG Meng Abstract: The iterative method is a loop control statement and loop structure design process.When the computer to solve the problem, hoping to find from the law of complex issues and boil down to a simple repetition of questions, to play the good characteristics of repeat operation, let it repeat a set of statements until the date that satisfies the given conditions. Therefore, c language repeat the statement provided by these statements constitute the program is called loop structure. This is the iterative method, using c language provided by the repeated statement, obtained the greatest common divisor and least common multiple of two numbers. Key words:loop; loop structure; iteration; greatest common divisor and least common multiple 算法案例——辗转相除法 育才中学潘敏 一、教材分析 选自苏教版普通高中课程标准实验教科书必修3第一章第4节。 1、地位作用： 与传统教学内容相比，《算法初步》为新增内容，算法是计算机科学的重要基础，从日常生活的电子邮件发送到繁忙的交通管理，从与人们生产、生活息息相关的天气预报到没有硝烟的战争模拟等等都离不开计算机算法。算法思想已经渗透到社会的方方面面，算法思想也逐渐成为每个现代人应具有的数学素养。 在以前的学习中，虽然没有出现算法这个名词，但实际上在数学教学中已经渗透了大量的算法思想，如四则运算的过程，求解方程的步骤，以及将要学习的数列求和等等，完成这些工作都需要一系列程序化的步骤，这就是算法思想。 本节内容是探究古代算法案例――辗转相除法，巩固算法三种描述性语言（自然语言、流程图和伪代码），提高学生分析和解决问题的能力。 2、教学目标： （1）知识目标： ①理解辗转相除法原理； ②能用自然语言、流程图和伪代码表达辗转相除法； ③能应用迭代算法思想。 （2）能力目标： ①培养学生把具体问题抽象转化为算法语言的能力； ②培养学生自主探索和合作学习的能力。 （3）情感目标： ①使学生进一步了解从具体到抽象，抽象到具体的辨证思想方法，对学生进行辨证唯物主义教育； ②创设和谐融洽的教学氛围和阶梯形问题，使学生在活动中获得成功感，从而培养学生热爱数学、积极学习数学、应用数学的热情。 3、教学重点与难点： （1）教学重点： ①理解辗转相除法原理； ②能用自然语言、流程图和伪代码表达辗转相除法。 （2）教学难点： ①理解和区分两种循环结构表达辗转相除法； ②能应用迭代算法思想。 二、教法学法 1、教法：以问题为载体，有引导的对话，让学生经历知识的形成过程和发展过程，从而突出教学重点，并采用多媒体教学，增加课堂容量，有利于学生活动的充分展开。 2、学法：以观察、讨论、思考、分析、动手操作、自主探索、合作学习多种形式相结合，引导学生多角度、多层面认识事物，突破教学难点。 数学知识点滴1.辗转相除法证明; 2.分数加法教学设计： 3.分数的意义： 4.阿拉伯数字最早起源于印度，在公元前500年，印度人就已经开始使用了，大约在8世纪前后才传到阿拉伯，9世纪阿拉伯人开始使用阿拉伯数字，大约在1100年由阿拉伯人传到欧洲，因此欧洲人称它为阿拉伯数字。阿拉伯数字传到中国是13世纪以后，1892年才在我国正式使用。 5.约分 “可半者半之，不可半者，副置分母，子之数，以少减多，更相减损，求其等也。以等相约之。”（吴文俊，1998a，p。58） 这种约分方法的具体思路是：首先判断分子与分母，如果都是偶数，就把分子分母分别除以2。如果是奇数，就把分子与分母相减（大减小），如果差与减数相等，差就是分子与分母 的最大公约（因）数，如果不相等，就把所得的差与减数再相减（大减小），这样一直减下去，直到新的差与新的减数相等为止，这个新的差就是原来分子与分母的最大公约数。（更相减损法） 6.分数除法 其一，被除数，除数之一含分数，另一个是整数，就先通分，后把被除数与除数的分子相除，如“方田”章第17题解题过程如下 813 ÷7=253 ÷7=8×3+13 ÷7×33 =(8×3+1)÷(7×3)=1421 其二，被除数，除数都含分数，就同时通分，后把被除数与除数的分子相除，如“方田”章第18题解题过程如下 （6+13 +34 )÷313 =6×12+4×1+3×312 ÷ (3×3+1)×412 =(6×12+4×1+3×3)÷【（3×3+1）×4】=218 这种计算方法虽然比我们现在用的“颠倒相乘法”麻烦，但是更容易理解。 第五讲 最大公约数与最小公倍数 【知识导引】 一、约数的概念与最大公约数 约数又叫因数(在正整数范围内）整数a 能被整数b 整除，a 叫做b 的倍数，b 就叫做a 的约数。最大公约数:如果一个数既是数a 的约数，又是数b 的约数，称为[a,b]的约数。几个数公有的因数，叫做这几个数的公因数,其中最大的一个叫做这几个数的最大公因数。 1. 求最大公约数的方法 ①分解质因数法：先分解质因数，然后把相同的因数连乘起来。 例如：2313711=??，22252237=??，所以(231,252)3721=?=； ②短除法：先找出所有共有的约数，然后相乘。例如：21812 39632 ，所以(12,18)236=?=； ③辗转相除法：每一次都用除数和余数相除，能够整除的那个余数，就是所求的最大公约数。用辗转相除法求两个数的最大公约数的步骤如下：先用小的一个数除大的一个数，得第一个余数；再用第一个余数除小的一个数，得第二个余数；又用第二个余数除第一个余数，得第三个余数；这样逐次用后一个余数去除前一个余数，直到余数是0为止。那么，最后一个除数就是所求的最大公约数(如果最后的除数是1，那么原来的两个数是互质的)。例如，求600和1515的最大公约数：151********÷= ；6003151285÷= ；315285130÷= ；28530915÷= ；301520÷= ；所以1515和600的最大公约数是15。 2. 最大公约数的性质 ①几个数都除以它们的最大公约数，所得的几个商是互质数； ②几个数的公约数，都是这几个数的最大公约数的约数； ③几个数都乘以一个自然数n ，所得的积的最大公约数等于这几个数的最大公约数乘以n 。 3. 求一组分数的最大公约数 先把带分数化成假分数，其他分数不变；求出各个分数的分母的最小公倍数a ；求 出各个分数的分子的最大公约数b ；b a 即为所求。 二、倍数的概念与最小公倍数 对于整数m ，能被n 整除（n/m ）,那么m 就是n 的倍数。如15能够被3或5整除，我们就说15是3的倍数，也是5的倍数。几个数公有的倍数叫做这几个数的公倍数,其中最小的一个叫做这几个数的最小公倍数。 论在小学教材中求最大公约数和最小公倍数的方法 班级：08数三班 学号：30308346 姓名：钟世校 初等数论是研究整数最基本性质的一门十分重要的数学基础课程,整除理论是初等数论的基础,其中心内容是最大公约数理论和算术基本定理,而我现在要论述的是求最大公约数和最小公倍数的几种方法 首先,让我们一起在来来了解一下最大公约数与最小公倍数的定义: 最大公约数: 设1a , 2a ,…，n a (n ≥2)是不全为零的整数,如果d| i a (i =1,2,3…,n),则称d 为 1a , 2a ,…，n a 的公约数,全体公约数中最大的一个数称为 1a , 2a ,…，n a 的最大公约数,记作(1a , 2a ,…，n a ). 最小公倍数: 设1a , 2a ,…，n a 是非零整数.若有整数M, 使 i a | M (i =1,2,3…,n ),则称 M 为1a , 2a ,…， n a 的公倍数,公倍数中最小的正数,称为1a , 2a ,…，n a 的最小公倍数,记作[1a , 2a ,…，n a ]。 求最大公约数的方法通常有两种,即用分解质因数法求最大公约数或用辗转相除法求最大公约数（亦称欧几里得算法），而求最小公倍数通常是用分解质因数或利用最大公约数来求最小公倍数,下最面我通过几道例题来演示上述方法. 一、 求最大公约数的方法. ⒈用分解质因数法求最大公约数. 例1. 求2700 、 7560、3960的最大公约数 解：把2700 、7560 、3960分别分解质因数. 得 2700=32 2 35 2?? 7560=3 3 357 2??? 3960= 2 3 352 11 ??? ∴ (2700,7560,3960)= 2 2 352 ??180 = 即2700 、 7560 、3960的最大公约数为180. 辗除法 辗除法（zhǎnchúfǎ）——辗转相除法，又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法。它是已知最古老的算法，其可追溯至3000年前。它首次出现于欧几里德的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。它并不需要把二数作质因子分解。 证明： 设两数为a、b(b 第四讲 辗转相除法与最大公因数 一、基础知识： 1．带余除法：若a ，b 是两个整数，b ＞0，则存在两个整数q 和r ，使得 a =bq+r （0≤r ＜ b ）成立， 且q ，r 是唯一的。 证明：【存在性】作整数序列 …，-3b ，-2b ，-b ，0，b ，2b ，3b ，… 则a 必在上述序列的某两项之间，即存在一个整数q 使得 qb ≤a <(q +1)b 成立。 令a -qb =r ，即证存在性。 【唯一性】设q 1、r 1是满足a =bq+r ，0≤r 一、 特殊情况： 1、倍数关系的两个数，最大公因数是较小的数，最小公倍数是较大的数。（如；6和12的最大公因数是6，最小公倍数是12。） 2、互质关系的两个数，最大公因数是１，最小公倍数是它们的乘积。（如，5和7的最大公因数时1，最小公倍数是5×7=35） 二、一般情况： 1求最大公因数： 列举法、单列举法、分解质因数法、短除法、除法算式法。 ①列举法：如，求18和27的最大公因数 先找出两个数的所有因数 18的因数有：1、2、3、6、9、18 27的因数有：1、3、9、27 再找出两个数的公因数： 18的因数有：1、2、3、6 、9、18 27的因数有：1、3、9、27 1、3、9 最后找出最大公因数： 9 ②单列举法：如，求18和27的最大公因数 先找出其中一个数的因数：18的因数有：1、2、3、6、9、18 再找这些因数中那些又是另一个数的因数：1、3、9又是27的因数 最后找出最大公因数： 9 ③短除法： 3 18 27 3 6 9 除到商是互质数为止，最后把所有的除数相乘 2 3 3×3=9 ④除法算式法： 用这两个数同时除以公因数，除到最大公因数为止。 18 ÷ 9就是18和27的最大公因数 27 2、求最小公倍数： 列举法、单列举法、大数翻倍法、分解质因数法或短除法。 ①列举法：如，求18和12的最小公倍数 先按从小到大的顺序找出这两个数的倍数： 18的倍数：18、36、54、72 12的倍数：12、24、36、48 再找出两个数的最小公倍数： 18的倍数：18、36、54、72 12的倍数：12、24、36、48 ②单列举法：如，求18和12的最小公倍数 先找出一个数的倍数： 18的倍数有：18、36、54、72 再按从小到大的顺序找这些倍数中那个又是另一个数的倍数，找出最小公倍数： 36 ③大数翻倍法：如，求18和12的最小公倍数 把较大的数翻倍（2倍开始），每次翻倍后看结果是不是另一个数的倍数，直到找到最小公倍数为止。 如，求18和12的最小公倍数。可以把18翻倍：18×2=36，36又是12的倍数，所以36是18和12的最小公倍数。 ④短除法：用这两个数同时除以一个质数（要能整除） 如，求18和12的最小公倍数，先用18和12同时除以质数2，再同时除以质数3，除到两个商是互质数（公因数只有1）为止。 2 18 12 3 除数 商 3 2 9 6 求最大公约数教案 道真县中等职业学校张学东 教学目标： 1．使学生进一步理解和掌握公约数和最大公约数的意义。 2．使学生理解和掌握用短除法、分解质因数的方法两个数的最大公约数的算理。 教学难点：用分解质因数的方法求两个数的最大公约数的算理。 教学设计： 一约数 【引例】看下面的式子： 18÷6 25÷5 24÷3 99÷11 169÷13这些除式中，商都是整数，余数为0.我们在数的整除中已经知道，这些除式都是整除式。 【小结】如果一个整数a除以整数b（b≠0）除得的商正好是整数而没有余数，那么我们就说a能被b整除，或b能整除a。a称为b的倍数，b称为a的约数。 上式中6是18的约数，5是25的约数，3是24的约数，11是99的约数，13是169的约数……，显然约数只存在于整除式中，故不是整除式就不存在约数。 二公约数及最大公约数 【引例】看下面的式子： 48÷8 24 ÷8 56÷8 ，显然，这些都是整除式，8是48、 24、56、这些所有整数的约数。 【小结】如果一个整数同时是几个整数的约数，那么就称这个 整数是它们的公约数。 公约数亦称公因数，公约数中最大的我们称它为最大公约数，若a 、b 的最大公约数为c ， 三 公约数与最大公约数的求法 求最大公约数的求法一般有：枚举法、短除法、分解质因数法、 1、短除法： 【讲解】 短除符号就像一个倒过来的除号，短除法就是先写出要求最大公因数的两个数A 、B ，再画一个短除号，接着在原本写除数的位置写两个数公有的质因数Z （通常从最小的质因数开始），然后在短除号的下方写出这两个数被Z 整除的商a 、b ，对a 、b 重复以上步骤，以此类推，直到最后的商互质为止，再把所有的除数相乘，其积即为A 、B 的最大公约数。 例1： 用短除法求12和18的最大公约数。 解:∵ ∴12和18的最大公约数为2×3=6 2、分解质因数法 【讲解】将要求最大公因数的两个数A 、B 分别分解质因数，再从中找出A 、B 公有的质因数，把这些公有的质因数相乘，即得到A 、2 12 18 6 9 3 求最大公因数和最小公倍数的方法 一、特殊情况： 1、倍数关系的两个数，最大公因数是较小的数，最小公倍数是较大的数。（如；6和12的最大公因数是6，最小公倍数是12。） 2、互质关系的两个数，最大公因数是１，最小公倍数是它们的乘积。（如，5和7的最大公因数时1，最小公倍数是5×7=35） 二、一般情况： 1、求最大公因数 2、求最小公倍数 ◆质数（prime number）又称素数，有无限个。一个大于1的自然数，除了1和它本身外， 不能被其他自然数整除，换句话说就是该数除了1和它本身以外不再有其他的因数；否则称为合数。 ◆根据算术基本定理，每一个比1大的整数，要么本身是一个质数，要么可以写成一系列 质数的乘积；而且如果不考虑这些质数在乘积中的顺序，那么写出来的形式是唯一的。 最小的质数是2。 ◆互质数为数学中的一种概念，即两个或多个整数的公因数只有1的非零自然数。公因数 只有1的两个非零自然数，叫做互质数。 ◆最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。 a，b的最大公约数记为（a，b），同样的，a，b，c的最大公约数记为（a，b，c），多 个整数的最大公约数也有同样的记号。求最大公约数有多种方法，常见的有质因数分解法、短除法、辗转相除法、更相减损法。与最大公约数相对应的概念是最小公倍数，a，b的最小公倍数记为[a，b]。 ◆两个或多个整数公有的倍数叫做它们的公倍数。 ◆两个或多个整数的公倍数里最小的那一个叫做它们的最小公倍数。整数a，b的最小公 倍数记为[a，b]，同样的，a，b，c的最小公倍数记为[a，b，c]，多个整数的最小公倍数也有同样的记号。 ◆与最小公倍数相对应的概念是最大公约数，a，b的最大公约数记为（a，b）。 ◆关于最小公倍数与最大公约数，我们有这样的定理： ◆(a,b)[a,b]=ab(a,b均为整数) 二、辗转相除法与裴蜀定理 4、辗转相除法与裴蜀定理 定义对于整数a，b，若 a b, 则称 a 是 b 的约数; 而 b 是 a 的倍数. 定义对于不全为零的整数a i(i 1,2,L ,n)，若 a a i对i 1,2,L ,n都成立, 则称a是a1,a2,L a n的公约数. 定义对于非零整数a i(i 1,2,L ,n)，若a i a对i 1,2,L ,n都成立, 则称a是a1,a2,L a n的公倍数. 定义 整数a i(i 1,2,L ,n) 的公约数中，最大的一个，称为整数a i(i 1,2,L ,n) 的最大公约数，记作(a1,a2,L a n). 整数a i(i 1,2,L ,n) 的公倍数中，最小的一个，称为整数a i(i 1,2,L ,n) 的最小公倍数， 记作[ a1,a2,L a n]. 定义若(a, b) =1,则称a, b 互质或互素. 显然有下列性质： 性质 1 (a, b) = (b, a) = (a, -b) = (- a, -b) ； 性质 2 ab = (a, b) [a, b] , 特别地当a>0, b>0 时，ab = (a, b) [a, b] . 下面我们介绍辗转相除法与裴蜀定理定理若 a = qb+r ，则(a, b) = (b, r) . 注：本定理也可写成： (a, b) = ( a bq , b), 就是说，在计算(a, b)时，可用 b 的任意整数倍数bq 去减 a. 下面我们介绍辗转相除法，对于给定的整数a, b (b>0) ，我们反复运用带余除法就有： a = q1 b + b1 , 0 b 1 < b，如b1 0，则我们继续 b = q2b1+ b2 , 0 b 2 < b1，如b2 0，则我们继 续b1 = q3 b2+b3 , 0 b 3 < b2，如b3 0，则我们继续? 我们知道，由于小于 b 的自然数是有限的，因此上述过程不可能无穷下去，在有限步之后，应有余数等于零，设在第n+1 步余数为零，于是 b n – 2 = q n – 1 b n – 1 + b n , 0 b n < b n –1 b n – 1 = q n b n + 0 上述过程称为辗转相除法，显然(a, b) = (b, b1) = (b1, b2)= (b2, b3) =?= (b n – 1 , b n ) = b n . 由于(a, b) = (a, - b ) ，从上述过程可以看到，辗转相除法是求两个整数最大公约数的一个很好的方法。 将上述前n 个式子联立方程组，消去b1,b2, ?, b n – 1 , 则可得到：u a + v b = b n ，其中u, v都是只与q1, q2, ?,q n – 1 有关的整数. 设(a, b) = d，则u a + v b = d .于是我们有以下定理：定理若ab 0, 设(a, b) = d，则存在整数u, v，使得u a + v b = d . [注]定理中的u, v 不唯一. 裴蜀定理(a, b) = 1 的充要条件是存在整数u, v 使得u a + v b =1. 并且若ab>0，则可以选择u>0，v< 0 或u<0 ，而v>0 . 证明：必要性显然，下面证明充分性. 对于整数a, b，存在整数u, v 使得u a + v b =1 ，我们设(a, b) = d，则 d a, d b，于是 d 1，又 d 1，所以 d = 1，即(a, b) = 1. 若ab>0，则a,b 同号，所以要使u a + v b =1 成立，u, v 必须异号，所以u>0 ，v< 0 或u<0，而v>0. 综上所述，裴蜀定理成立. 5．最大公约数与最小公倍数的性质 性质 1 若(a, b) =1, 且 a bc，则 a c； 性质 2 若(a, b) =1, 则(a, bc) = (a, c)； 性质 3 若(a i, b j) =1, i 1,2,L m, j 1,2,L n,则(a1a2L a m, b1b2 L b n) 1 性质 4 若(a, b) =1, 且n, m 是非负整数，则(a n, b m) = 1； 性质 5 若m a, m b，则m (a, b) ； 性质 6 设正整数a, b 的质因数分解式如下 a = p11 p22p k k，b = p11p22p k k, 其中 用短除法求最大公因数练习题精品文档 用短除法求最大公因数练习题 一、求几个数的最大公因数 12和30 4和36 39和72和84 36和6045和60 45和745和60 42、105和564、36和48 二、给下面的分数约分 24 36 45 75 16358 2420 1680 1751 10 三、求几个数的最小公倍数。 25和304和309和78 60和18和20 126和60 5和75 12和2445和60 76和80和60 7和72 1 / 9 精品文档 42、105和5624、36和48 四、将下列各组分数通分。 5 和32 81 14和35 7112和 和35 9和639951827 2 4和721210和1751 1和43910和2233 2 4和3527和51557和18237和109 六、用短除法求几个数的最大公因数与最小公倍数。 45和606和60 7和7276和80、12和247、21和498、12和36 七. 填空题。 1. 都是自然数，如果 =10 ，的最大公约数是，最小公倍数是。 2. 甲=2×3×，乙=2×3×，甲和乙的最大公约数是×,，甲和乙的最小公倍数是×××,。 3. 所有自然数的公约数为。 2 / 9 精品文档 4. 如果m和n是互质数，那么它们的最大公约数是，最小公倍数是。 5. 在4、9、10和16这四个数中，和是互质数，和是互质数，和是互质数。ab 6. 用一个数去除15和30，正好都能整除，这个数最大是。 7. 两个连续自然数的和是21，这两个数的最大公约数是，最小公倍数是。 8. 两个相邻奇数的和是16，它们的最大公约数是，最小公倍数是。 9. 某数除以3、5、7时都余1，这个数最小是。 10. 根据下面的要求写出互质的两个数。 两个质数和。 连续两个自然数和。 1和任何自然数和。 两个合数和。 奇数和奇数和。 奇数和偶数和。 八、写出下列各数的最大公因数和最小公倍数 15和5的最大公因数是和3的最大公因数是 9和18的最大公因数是和44的最大公因数是最小公倍数是 3 / 9 精品文档 30和60 的最大公因数是最小公倍数是13和91 的最大公因数是最小公倍数是7和12的最大公因数是和11的最大公因数是最小公倍数是 1和9的最大公因数是最小公倍数是8和10的最大公因数是最小公倍数是6和9的最大公因数是最小公倍数是8和6的最大公因数是最小公倍数是辗转相除算法的简介
最大公约数的算法
辗转相除法教学设计
最大公约数和最小公倍数怎么求
用迭代法求两个数的最大公约数和最小公倍数
算法案例——辗转相除法
辗转相除法证明
第五讲 最大公约数与最小公倍数
论最小公倍数和最大公约数的方法
用辗转相除法求最大公约数
初中数学竞赛讲座——数论部分4(辗转相除法与最大公约数)
求最大公因数和最小公倍数的方法(简单实用)
求最大公约数教学设计
求最大公因数和最小公倍数的方法
辗转相除法与裴蜀定理
用短除法求最大公因数练习题