a+tm=b+tn(mod l)
a-b=t(n-m)(mod l)
a+tm=b+tn+kl
(a-b)=t(m-n)+kl

 

ax+by=gcd(a,b)

 

 

 

 

 

 

 

ax1+by1=gcd(a,b)
(b)x2+(a%b)y2=gcd(b,a%b)
ax1+by1=bx2+(a-a/b)y2
ax1=(a-a/b)y2
by1=bx2
所以y1=x2
ax1=(a-a/b)y2

 手推