tft每日頭條

 > 知識

 > 輾轉相除法原理

輾轉相除法原理

知識 更新时间:2024-07-30 20:22:43

  輾轉相除法原理是設兩數為a、b(a>b),用gcd(a,b)表示a,b的最大公約數,r=a(modb)為a除以b的餘數,k為a除以b的商,即a÷b=k.......r。輾轉相除法即是要證明gcd(a,b)=gcd(b,r)。

  輾轉相除法,又名歐幾裡德算法(Euclideanalgorithm)乃求兩個正整數之最大公因子的算法。它是已知最古老的算法,其可追溯至公元前300年前。

  設兩數為a、b(a>b),求a和b最大公約數(a,b)的步驟如下:用a除以b,得a÷b=q......r1(0≤r1)。若r1=0,則(a,b)=b;若r1≠0,則再用b除以r1,得b÷r1=q......r2 (0≤r2).若r2=0,則(a,b)=r1,若r2≠0,則繼續用r1除以r2,……如此下去,直到能整除為止。其最後一個餘數為0的除數即為(a,b)的最大公約數。

更多精彩资讯请关注tft每日頭條,我们将持续为您更新最新资讯!

查看全部

相关知識资讯推荐

热门知識资讯推荐

网友关注

Copyright 2023-2024 - www.tftnews.com All Rights Reserved