ユークリッドの互除法

ユークリッドの互除法は、

x ≧ y のとき、gcd(x, y) と gcd(y, x%y) は等しい

という定理を用いて、x と y の最大公約数を効率良く求めるアルゴリズムです。
（ここで、x%y は x を y で割った余りを示します）

具体的な例を見てみましょう。

gcd(54, 20)		(54 % 20 = 14)
= gcd(20, 14)		(20 % 14 = 6)
= gcd(14, 6)		(14 % 6 = 2)
= gcd(6, 2)		(6 % 2 = 0)
= gcd(2, 0)
= 2

ユークリッドの互除法を実装したプログラム例です。

001 int gcd( int x, int y ){
002     int r;
003     // x ≧ y を満たすことを保障する
004     if ( x < y ) swap( x, y );
005     
006     while ( y > 0 ){
007         r = x % y;
008         x = y;
009         y = r;
010     }
011     
012     return x;
013 }

定理の証明,,,,