不妨設(shè)a,b的最大公約數(shù)就是c
則存在m,n都是整數(shù),使得a=mc,b=nc,且（m,n）=1
方程c=sa+tb等價于方程1=ms+nt
因為（m,n）=1,
如果m不等于n,則必然有一個大于1,不妨設(shè)n>1
所以m,2m,3m,……,(n-1)m這n-1個數(shù)兩兩模n互質(zhì),它們都不整除n從而其中必然存在一個數(shù) i,使得im除以n的余數(shù)是1
也就是存在整數(shù)t,使得im=nt+1
所以im+（-t）n=1
所以此時方程1=ms+nt存在整數(shù)解
如果m,n相等,那么m=n=1,則原來方程等價于s+t=1,顯然有整數(shù)解
所以綜上：整數(shù)a,b的最大公約數(shù)可以寫成gcd(a,b)=sa+tb的形式,其中s,t為整數(shù)