求方程ax=c(mod b)的解
可将其转换为 ax+by=c
有解条件：(a,b)|c
设k*(a,b)=c
用拓展欧几里得求出方程ax+by=(a,b)的解(x,y)
x’=k*x,y’=k*y 就是方程的一个解
所以x’+i*(b/(a,b)) (i=0,1,2,..,(a,b)-1) 是原方程的解
证明：
设sx[i]=x’+i*(b/(a,b)),sy[i]=y’-i*(a/(a,b))
则需证明a*sx[i]+b*sy[i]=c
a*sx[i]+b*sy[i]
=a*(x’+i*(b/(a,b)))+b*(y’-i*(a/(a,b)))
=ax’+by’+a*i*b/(a,b)-b*i*a/(a,b)
=ax’+by’
=c 得证