1、基本概念及一次同余式：

一、同余式的基本概念

定义1.1：

设m是一个正整数，f(x)为多项式f(x) = a_nxⁿ + ··· + a₁x + a₀，其中ai是整数，则f(x) ≡ 0（mod m）（*）叫作模m同余式。html

若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的彻底剩余系中，使得同余式 * 成立的剩余个数叫作同余式 * 的解数。spa

同余式求解的基本思路：

1. 求解归约（f(x)（mod m）<=== f(x)（mod pα）<=== f(x)（mod p））；
2. 解的存在性（如定理1.1）；
3. 解的个数（如定理1.3，4.4，4.5）；
4. 具体求解（定理2.1，定理4.1）。

二、一次同余式

一次同余式求解的基本思路：

（a，m）= 1，ax ≡ 1（mod m）===> （a，m）= 1，ax ≡ b（mod m）===> ax ≡ b（mod m）03d

定理1.1：

设m是一个正整数，a是知足m  a的整数，则一次同余式ax ≡ 1（mod m）（*）有解的充分必要条件是（a，m）= 1。并且，当同余式 * 有解时，其解是惟一的。htm

定义1.2：

设m是一个正整数，a是一个整数。若是存在整数a'使得a · a' ≡ a' ` a ≡ 1（mod m）成立，则a叫作模m可逆元。blog

根据定理1.1，在模m的意义下，a'是惟一存在的。这是a'叫作a的模m逆元，记做a' = a^-1（mod m）。递归

所以，在定理3.1的条件下，同余式（*）即ax ≡ 1（mod m）的解可写成x ≡ a^-1（mod m）。get

定理1.2：

设 m 是一个正整数，则整数 a 是模 m简化剩余的充要条件是整数 a 是模 m 逆元。

定理1.3：

2、中国剩余定理：

一、中国剩余定理：“物不知数”与韩信点兵

定理2.1：

二、两个方程的中国剩余定理

定理2.2：

定理2.3：

三、中国剩余定理之构造证实

四、中国剩余定理之递归证实

五、中国剩余定理之应用 —— 算法优化

例2.1：

例2.2：

例2.3：

定理2.4：

命题2.1：

推论：

3、高次同余式的解数及解法：

一、高次同余式的解数

定理3.1：

二、高次同余式的提高

定理3.2：

三、高次同余式的提高 —— 具体应用

例3.1：

4、素数模的同余式：

一、素数模的多项式欧几里得除法

引理4.1（多项式欧几里得除法）：

设f(x) = a_nxⁿ + ··· + a₁x + a₀为n次整系数多项式，g(x) = x^m + ··· + b₁x + b₀为m ≥ 1次首一整系数多项式，则存在整系数多项式q(x)和r(x)使得f(x) = q(x) · g(x) + r(x)，deg r(x) < deg g(x)。

二、素数模的同余式的简化

定理4.1：

同余式与一个次数不超过p - 1的模p同余式等价。 

三、素数模的同余式的因式分解

定理4.2：

设1 ≤ k ≤ n。若是x ≡ a_i（mod p），i = 1，···，k，是同余式的k个不一样解，则对任何整数x，都有f(x) ≡ f_k(x) · (x - a₁) · ··· ·(x - a_k)（mod p），其中f_k(x)是n - k次多项式，首项系数是a_n。

定理4.3：

四、素数模的同余式的解数估计

定理4.4：

同余式的解数不超过它的次数。

推论：

次数 < p的整系数多项式对全部整数取值模p为0的充要条件是其系数被p整除。

定理4.5：

设p是一个素数，n是一个正整数，n ≤ p。那么同余式f(x) = x_n + ··· + a₁x + a₀ ≡ 0（mod p）有n个解得充分必要条件是x^p - x被f(x)除所得余式的全部系数都是p的倍数。

推论：

设p是一个正整数，d是p - 1的正因数，那么多项式x^d - 1模p有d个不一样的根。

上一篇：

http://www.noobyard.com/article/p-yvtxgcbt-oa.html