摘要

线性同余方程

• 引理1 若ac≡bc(MOD m),且，gcd(c,m)=d,则,a≡b(MOD m/d) 证： 由m∣∣c(a−b)，即m/d ∣∣ c/d(a−b),而gcd(m/d,c/d)=1,所以m/d∣∣(a−b), 即a≡b(MODm/d)
• 引理2 丢番图方程 形如ax+by=c,其中a,b,c,为整数，有整数解，当且仅当d=gcd(a,b)∣∣c，且，若x0,y0为一组特解，则其所有解满足x=x0+b/d∗n,y=y0−a/d∗n 证明: 不存在解的情况是很显然的,由于d∣a,d∣b,所以d∣ax+by,这与d∤c矛盾 若x0,y0,为他的一组特解(可以通过扩展gcd求出来)
  将x=x0+b/d∗n,y=y0−a/d∗n 带入可以发现这样的 x,y 满足解。下证，他的任意解满足上式 ax+by=cax0+by0=c
  相减，我们可以得到