Question

如何证明一次同余方程ax≡b（modm）有解的充要条件（a,m）│b?

Answer 1

ax≡b(mod m),

存在整数k,使得b=ax-km,

∴d=(a,m)整除b.

反过来,若d|b,因(a/d,m/d)=1,故存在整数x,k,使得(a/d)x-k(m/d)=b/d,

∴ax-km=b,

∴方程ax≡b(mod m)有解.