證明“輾轉相除法”
輾轉相除法,
又名歐幾裏德算法(euclidean
algorithm)乃求兩個正整數之最大公因子的算法。它是已知最古老的算法,
其可追溯至前300年。它首次出現於歐幾裏德的《幾何原本》(第vii卷,命題i和ii)中,而在中國則可以追溯至東漢出現的《九章算術》。它並不需要把二數作質因子分解。
[編輯]
算法
輾轉相除法是利用以下性質來確定兩個正整數
a
和
b
的最大公因子的:
1.
若
r
是
a
÷
b
的余數,
則
gcd(a,b)
=
gcd(b,r)
2.
a
和其倍數之最大公因子為
a。
另壹種寫法是:
1.
a
÷
b,令r為所得余數(0≤r
0
return
gcd(b,
a
mod
b);
else
return
a;
}
或純使用循環:
function
gcd(a,
b)
{
define
r
as
integer;
while
b
≠
0
{
r
:=
a
mod
b;
a
:=
b;
b
:=
r;
}
return
a;
}
其中“a
mod
b”是指取
a
÷
b
的余數。
例如,123456
和
7890
的最大公因子是
6,
這可由下列步驟看出:
a
b
a
mod
b
123456
7890
5106
7890
5106
2784
5106
2784
2322
2784
2322
462
2322
462
12
462
12
6
12
6
0
只要可計算余數都可用輾轉相除法來求最大公因子。這包括多項式、復整數及所有歐幾裏德定義域(euclidean
domain)。
輾轉相除法的運算速度為
o(n2),其中
n
為輸入數值的位數。