最小公倍数与最大公因数.doc

学院学 术 论 文题 目 最小公倍数与最大公因数 姓 名 所在学院 专业班级 学 号 指导教师 日 期 关键字：公倍数 公因数 求法Keywords : GongYinShu LCD Is introduced摘要：我们主要是通过列举法，短除法,矩阵法和辗转相除法来解决最大公因数和最小公倍数的问题Abstract: we mainly through the list, short division, matrix method and Euclidean algorithm To solve GongYinShu maximum and minimum of LCD最大公因数和最小公倍数在计算的时候我们一般采用的方法是短除的方法，它们在计算时的最大区别在于所需要的质因数是不同的，最大公因数是取公有的质因数，最小公倍数是公有的质因数（代表）和独有的质因数都要。但是在两个数不容易看出公因数的时候，我们也可以采取辗转相除的方法进行计算。具体的方法是：先用小的一个数除大的一个数，得第一个余数，再用第一个余数除小的一个数，得到第二个余数；又用第二个余数除第一个余数，得第三个余数，这样逐次用后一个余数去除前一个余数，直到余数是0为止。那么最后一个除数就是所求的最大公约数。最大公因数和最小公倍数之间还存在着性质：两个自然数的乘积等于这两个自然数的最大公约数和最小公倍数的乘积。 若a、b表示两个自然数，则 ab=（a，b）a，b在利用最大公因数和最小公倍数解决实际生活中的问题的时候，首先要分清计算的是哪个？然后再进行计算。（一）求三个数的最大公因数和最小公倍数的方法。 例1. 求20、30和36的最大公因数和最小公倍数 （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 分解质因数的方法 20=225 30=253 36=2233 （20，30，36）=2 短除的方法 （20，30，36）=2 （2）我们再来计算它们的最小公倍数 列举法 20的倍数有：20、40、60、80 30的倍数有：30、60、90、 36的倍数有：36、72、分解质因数的方法 20=225 30=253 36=2233 20，30，36=22353=180短除的方法 （20，30，36）=2 20，30，36=22353=180 （3）对比 比较分解质因数的方法 20=225 30=2 5 3 36=22 33 （20，30，36）=2 20，30，36=22353=180 比较短除的方法 （20，30，36）=2 20，30，36=22353=180（4）小结：在计算三个数的最大公因数和最小公倍数的时候，最大公因数要找三个数的公有的质因数，如果其中的两个商还有质因数的话，也不要往下除。 最小公倍数的计算要把三个数的公有质因数和独有质因数都要找全，最后除到两两互质为止。（二）辗转相除法。 1. 方法介绍：辗转相除法是求两个数的最大公约数的一种方法。辗转相除法又叫做欧几里德除法。 2. 用辗转相除法计算两个数的最大公约数。 用辗转相除法求两个数的最大公约数的步骤如下：先用小的一个数除大的一个数，得第一个余数，再用第一个余数除小的一个数，得到第二个余数；又用第二个余数除第一个余数，得第三个余数，这样逐次用后一个余数去除前一个余数，直到余数是0为止。那么最后一个除数就是所求的最大公约数（如果最后的余数是1，那么原来的两个数互质）。 例2. 求792和1134的最大公约数。 1134792=1342 792342=2108 342108=318 10818=6 （没有余数） （792，1134）= 18用辗转相除法在短除计算两个数的最大公约数有困难的时候，效果尤其显著。 3. 如何用辗转相除法计算两个数的最小公倍数呢？先计算出最大公约数，再用两数之积除以最大公约数，商就是最小公倍数。（三）矩阵消去法我们通过矩阵的初等行变换，把（，a）（n为数字的个数）的第n+1列的n个元素化为零最后的一个数就是最大公因数当n=2时 求 d不算难事当 n2时， 用辗转相除法求 d就有些繁琐了因为辗转相除法每次只能求两个数，要反复多次使用 才能求出 d 这时再据求d过程这里提出了一十求 d的方 法 消去法 操作简便 程序清晰， 计算量也不大 例 1 求整数列 A=(,A)=D=17例 2 求A=（,A）=d=(78.234,195,273)=(0,0,0,39)=39（四）最大公约数和最小公倍数的性质。 例4. 求18和24的最大公约数和最小公倍数 （1）用分解质因数的方法独立完成 （18，24）=23=6 18，24=23322=72 （2）观察