设m是一个正整数,f(x)为多项式f(x) = anxn + ··· + a1x + a0,其中ai是整数,则f(x) ≡ 0(mod m)(*)叫做模m同余式。
若an 0(mod m),则n叫做f(x) 的次数,记为degf。此时 * 式又叫做模m的n次同余式。
如果整数x = a使得 * 式成立,即f(a) ≡ 0(mod m)则a叫做该同余式 * 的解。
事实上,满足x ≡ a(mod m)的所有整数使得同余式 * 成立,即a所在剩余类Ca = { c | c ∈ Z,c ≡ a(mod m)}中的每个剩余都使得同余式 * 成立,因此,同余式 * 的解a通常写成x ≡ a(mod m)。
在模m的完全剩余系中,使得同余式 * 成立的剩余个数叫做同余式 * 的解数。
(a,m)= 1,ax ≡ 1(mod m)===> (a,m)= 1,ax ≡ b(mod m)===> ax ≡ b(mod m)0
设m是一个正整数,a是满足m a的整数,则一次同余式ax ≡ 1(mod m)(*)有解的充分必要条件是(a,m)= 1。而且,当同余式 * 有解时,其解是唯一的。
设m是一个正整数,a是一个整数。如果存在整数a'使得a · a' ≡ a' ` a ≡ 1(mod m)成立,则a叫做模m可逆元。
根据定理1.1,在模m的意义下,a'是唯一存在的。这是a'叫做a的模m逆元,记作a' = a-1(mod m)。
因此,在定理3.1的条件下,同余式(*)即ax ≡ 1(mod m)的解可写成x ≡ a-1(mod m)。
设 m 是一个正整数,则整数 a 是模 m简化剩余的充要条件是整数 a 是模 m 逆元。
设f(x) = anxn + ··· + a1x + a0为n次整系数多项式,g(x) = xm + ··· + b1x + b0为m ≥ 1次首一整系数多项式,则存在整系数多项式q(x)和r(x)使得f(x) = q(x) · g(x) + r(x),deg r(x) < deg g(x)。
同余式与一个次数不超过p - 1的模p同余式等价。
设1 ≤ k ≤ n。如果x ≡ ai(mod p),i = 1,···,k,是同余式的k个不同解,则对任何整数x,都有f(x) ≡ fk(x) · (x - a1) · ··· ·(x - ak)(mod p),其中fk(x)是n - k次多项式,首项系数是an。
同余式的解数不超过它的次数。
次数 < p的整系数多项式对所有整数取值模p为0的充要条件是其系数被p整除。
设p是一个素数,n是一个正整数,n ≤ p。那么同余式f(x) = xn + ··· + a1x + a0 ≡ 0(mod p)有n个解得充分必要条件是xp - x被f(x)除所得余式的所有系数都是p的倍数。
设p是一个正整数,d是p - 1的正因数,那么多项式xd - 1模p有d个不同的根。