必修3《小结》新课标PPT课件优质课下载

必修3《小结》新课标PPT课件优质课下载

由于282和470都是偶数，则需用2约简得：141和235

辗转相除法

（1）辗转相除法，又叫欧几里得法，提出于公元前300年左右，是一种求两个正整数的 最大公约数 的古老而有效的算法。

（2）辗转相除法是指对于给定的两

个数，用 大数 除以 小数 ，若余数

不为零，则将余数和 较小数 构成新

的一对数，继续上面的除法，直到

大数被小数除尽，则这时 小数 就是

原来两个数的最大公约数。

更相减损术

更相减损术是我国古代数学专著《九章算术》中介绍的一种求?两个数的最大公约数?的算法.?提出于公元一世纪左右。

“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之”

问题一：辗转相除法的关键步骤是做带余除法：

被除数=除数×商+余数。

其中被除数、除数和除数、余数有相同的最大公约数，即：gcd（被除数，除 数）=gcd（除数，余数）,为什么呢？

gcd(470,282) = gcd(282,188) = gcd(188,94)= 94

已知 ， 求证：

下面说明c为最大公约数，即： 与b互质

令 ，则设 ，

故c也为n和r的约数。

∴ 与 有公约数cd，且cd>c。

与 产生矛盾

（反证法）假设 ，

则

∴ 假设不成立，原结论成立