一次同余方程

时间:2021-04-12 05:18:19

设m>0,方程

                  ax ≡ c(mod m)

称作一次同余方程,使上述方程成立的整数称作方程的解.其中方程不一定有解。方程有解的充分必要条件是d=gcd(a,m),当d |c时,有d个解。

 设x0是上述式子的解,不难验证所有与x0模m同余的数都是该式子的解,从而可以写成x ≡ x0(mod m)。于是,只对模m的每个等价类娶一个代表,验证是否使方程成立,就能找到所有的解。

定义:如果ab ≡ 1(mod m),则称b是a的模m的逆,记作a-1(mod m)。

a 的模的逆的方程是    ax ≡ 1(mod m)  该方程的解存在的充分必要条件是 a 与 m互素.