(定理)ユークリッド互除法
整数a,bについて、ある整数q,rが存在して
a=bq+r
を満たすならば
gcd(a,b)=gcd(b,r)
ここでgcd(a,b)はaとbの最大公約数です
qはaをbで割った商、rは余りです
(証明）
gcd(a,b)=d_1
とすると
a=a´・d_1
b=b´・d_1
と書ける
r=a-bq=a´・d_1-b´・d_1・q=d_1(a´-b´・q)
となるので、rはd_1で割り切れる
また、d_1はbとrの公約数でもある
よって
d_1≦gcd(b,r)=d_2・・・・・・①
gcd(b,r)=d_2より
b=b´´・d_2
r=r´・d_2
ここで
a=bq+r=b´´・d_2・q-r´・d_2=d_2（b´´・q-r´)
よってaはd_2で割り切れるのでd_2はaとbの公約数
つまり
d_2≦gcd(a,b)=d_1・・・・・・②
①、②より
d_1=d_2
つまり
gcd(a,b)=gcd(b,r)
(証明終わり)
以下計算例を書きます
gcd(48,36)を求めます
48=36・1+12
より
gcd(48,36)=gcd(36,12)
36=12・3+0
より
gcd(48,36)=gcd(36,12)=gcd(12,0)=12
