最大公約数とユークリッドアルゴリズム

a,bの最大公約数はgcd(a,b)と記す.
ここで、最大公約数についての議論は、gcd(a,b)=gcd(|a|,|b|)が明らかにあるため、非負の整数に限られる.
最大公約数を計算するEuclidアルゴリズムは次の定理に基づいている.
任意の非負の整数aおよび任意の正の整数bに対して、gcd(a,b)=gcd(b,a%b)である.
Euclidアルゴリズムの最も簡単な再帰版(C言語版)は以下の通りである.

1 int Euclid(int a,int b)
2 {
3     if(b)return Euclid(b,b%a);else return a;
4 }

反復バージョン(C言語版)は次のとおりです.

1 int Euclid(int a,int b)
2 {
3     while(a=a%b)a^=b^=a^=b;
4     return b;
5 }

Euclidアルゴリズム実行時間分析
【引数】a>b≧1、Euclid(a,b)がk≧1回の再帰呼び出しを実行した場合、a≧Fk+2、b≧Fk+1.(FkはFabonacciのk番目の項)
【Lamé定理】任意のk≧1に対して、a>b≧1であり、bO(logb)はこのアルゴリズムの粗い境界であり,実際にbが決定した後,Euclid(a,b)の平均反復回数は(12 ln 2/π2)に近似した.×lnb.
 
上記のEuclidアルゴリズムに加えて、剰余演算を求めないバイナリ最大公約アルゴリズムがある.