【欧几里得算法及其证明】欧几里得算法是用来求两个数的最大公约数（greatest common divisor(gcd)），其具体过程如下：
有a , b a,b a,b 两个正整数，现在按以下步骤求它们最大公约数,即g c d ( a , b ) gcd(a,b) gcd(a,b) :
a/b
= q 1 ? ? r 1 a \ /\ b \ \;
= q_1 \cdots\cdots r_1 a / b =q1???r1?
b/r 1
= q 2 ? ? r 2 b\ /\ r_1 \;
= q_2 \cdots\cdots r_2 b / r1?=q2???r2?
r 1 / r 2= q 3 ? ? r 3 r_1 / r_2 \ = q_3 \cdots\cdots r_3 r1?/r2? =q3???r3?
? ? \cdots\cdots ??
r m / r n = q t ? ? 0 r_m / r_n = q_t \cdots\cdots 0 rm?/rn?=qt???0
如此反复迭代直至余数为0，最终得到的r n r_n rn? 就是a , b a,b a,b 的最大公约数，这就是欧几里得算法。
欧几里得算法的证明可以转化为g c d ( a , b ) = g c d ( b , r 1 ) = g c d ( r 1 , r 2 ) = ? = g c d ( r m , r n ) gcd(a,b) = gcd(b,r_1) = gcd(r_1,r_2) = \cdots = gcd(r_m,r_n) gcd(a,b)=gcd(b,r1?)=gcd(r1?,r2?)=?=gcd(rm?,rn?) 的证明，实际只要证明 g c d ( a , b ) = g c d ( b , r 1 ) gcd(a,b) = gcd(b,r_1) gcd(a,b)=gcd(b,r1?) ，后面的式子同理可得，其证明如下：
前提公理：若a = m d , b = n d a=md,b=nd a=md,b=nd( m 、 n 、 d 1 m、n、d_1 m、n、d1? 为正整数)，
则m , n m,n m,n 互质
?
\iff ?d d d 为a 、 b a、b a、b 的最大公约数。
假设g c d ( a , b ) = d 1 gcd(a,b)=d_1 gcd(a,b)=d1? 即 a 、 b a、b a、b 最大公约数为d 1 d_1 d1?，并且有
a = m d 1 , b = n d 1 ( m 、 n 、 d 1 为 正 整 数 ) a = md_1 , b = nd_1(m、n、d_1为正整数) a=md1?,b=nd1?(m、n、d1?为正整数)
又有 a = b q + r 1 , b = n d 1 a = bq + r_1, b = nd_1 a=bq+r1?,b=nd1?，则
r 1 = a ? b q = ( m ? n q ) d 1 r_1 = a -bq = (m-nq)d_1 r1?=a?bq=(m?nq)d1?
现在只要证明 n 、 ( m ? n q ) n、(m-nq) n、(m?nq) 互质再利用前提公理就可证明g c d ( b , r 1 ) = d 1 gcd(b,r_1)=d_1 gcd(b,r1?)=d1?
假设n 、 ( m ? n q ) n、(m-nq) n、(m?nq)不是互质的，有g c d ( n , m ? n q ) = d 2 ( d 2 >
1 ) gcd(n,m-nq)=d_2 (d_2>
1) gcd(n,m?nq)=d2?(d2?>1) 且
n = x d 2 , m ? n q = y d 2 ( x 、 y 、 d 2 为 正 整 数 ) n=xd_2,m-nq = yd_2(x、y、d_2 为正整数) n=xd2?,m?nq=yd2?(x、y、d2?为正整数)
则
m = n q + y d 2 = ( x q + y ) d 2 m = nq + yd_2 = (xq + y)d_2 m=nq+yd2?=(xq+y)d2?
那么 a = m d = ( x q + y ) d 1 d 2 a = md =(xq+y)d_1d_2 a=md=(xq+y)d1?d2?
b = n d = x d 1 d 2 b = nd =xd_1d_2 b=nd=xd1?d2?
a 、 b a、b a、b 的最大公约数变成d 1 d 2 d_1d_2 d1?d2? ,不符合假设条件g c d ( a , b ) = d 1 gcd(a,b)=d_1 gcd(a,b)=d1? ，故n 、 ( m ? n q ) n、(m-nq) n、(m?nq) 互质。
由前提公理可得：
g c d ( b , r 1 ) = d 1 gcd(b,r_1)=d_1 gcd(b,r1?)=d1?
故
g c d ( a , b ) = g c d ( b , r 1 ) = d 1 gcd(a,b) = gcd(b,r_1) = d_1 gcd(a,b)=gcd(b,r1?)=d1?
由此证明欧几里得算法。
