数学中的辗转相除法是怎样的?
辗转相除法(也称为欧几里得算法)。求几个数目较大的数的最大公约 数,又不易看出它们的质因数,可以采用辗转相除法。用这种方法求这两个 数的最大公约数,步骤如下:
先用较小的一个数除较大的一个数,得第一个余数;再用第一个余数除 较小的一个数,得第二个余数;又用第二个余数除第一个余数得第三个余数; 这样逐次用后一个余数去除前一个余数,直到余数是0为止。 那么最后一个 除数就是所求的最大公约数(如果最后的除数是1,那么原来的这两个数互 质)。
例如求377, 319的最大公约数。
第一次:用319除377,商1余58;
第二次:用58除319,商5余29;
第三次:用29除58,商2余0。
...全部
辗转相除法(也称为欧几里得算法)。求几个数目较大的数的最大公约 数,又不易看出它们的质因数,可以采用辗转相除法。用这种方法求这两个 数的最大公约数,步骤如下:
先用较小的一个数除较大的一个数,得第一个余数;再用第一个余数除 较小的一个数,得第二个余数;又用第二个余数除第一个余数得第三个余数; 这样逐次用后一个余数去除前一个余数,直到余数是0为止。
那么最后一个 除数就是所求的最大公约数(如果最后的除数是1,那么原来的这两个数互 质)。
例如求377, 319的最大公约数。
第一次:用319除377,商1余58;
第二次:用58除319,商5余29;
第三次:用29除58,商2余0。
377, 319的最大公约数是29。
求三个或三个以上的数的最大公约数,可以先求出其中两个数的最大公 约数,再求所得的数与第三个数的最大公约数等等,一直继续到最后一个数, 最后得到的最大公约数就是所求的最大公约数。
例如求418,494,589的最大公约数,可以先求得418,494的最大公约 数是38,再求得38, 589的最大公约数是19。最后得到418, 494, 589的最 大公约数是19。
。
收起