第四章 (8) 高次同余式的解法、质数模的同余式

第一章 整数的可除性§1 整除的概念·带余除法 1．证明定理3定理3 若12n a a a ，，，都是m 得倍数，12n q q q ，，，是任意n 个整数，则1122n n q a q a q a +++是m 得倍数．证明：12,,n a a a 都是m 的倍数。

∴ 存在n 个整数12,,n p p p 使 1122,,,n n a p m a p m a p m ===又12,,,n q q q 是任意n 个整数1122n n q a q a q a ∴+++1122n n q p m q p m q p m =+++ 1122()n n p q q p q p m =+++即1122n n q a q a q a +++是m 的整数2．证明 3|(1)(21)n n n ++ 证明(1)(21)(1)(2n n n n n n n ++=+++-(1)(2)(1)(n n n n n n =+++-+ 又(1)(2)n n n ++，(1)(2)n n n -+是连续的三个整数故3|(1)(2),3|(1)(1)n n n n n n ++-+3|(1)(2)(1)(1)n n n n n n ∴+++-+从而可知3|(1)(21)n n n ++3．若00ax by +是形如ax by +（x ，y 是任意整数，a ，b 是两不全为零的整数）的数中最小整数，则00()|()ax by ax by ++．证：,a b 不全为0∴在整数集合{}|,S ax by x y Z =+∈中存在正整数，因而有形如ax by +的最小整数00ax by +,x y Z ∀∈，由带余除法有0000(),0ax by ax by q r r ax by +=++≤<+则00()()r x x q a y y q b S =-+-∈，由00ax by +是S 中的最小整数知0r =00|ax by ax by ∴++00|ax by ax by ++ （,x y 为任意整数） 0000|,|ax by a ax by b ∴++ 00|(,).ax by a b ∴+ 又有(,)|a b a ，(,)|a b b00(,)|a b ax by ∴+ 故00(,)ax by a b +=4．若a ，b 是任意二整数，且0b ≠，证明：存在两个整数s ，t 使得||,||2b a bs t t =+≤成立，并且当b 是奇数时，s ，t 是唯一存在的．当b 是偶数时结果如何？ 证：作序列33,,,,0,,,,2222b b b b b b ---则a 必在此序列的某两项之间即存在一个整数q ，使122q q b a b +≤<成立 ()i 当q 为偶数时，若0.b >则令,22q qs t a bs a b ==-=-，则有 02222b q q qa bs t ab a b b t ≤-==-=-<∴<若0b < 则令,22q qs t a bs a b =-=-=+，则同样有2b t < ()ii 当q 为奇数时，若0b >则令11,22q q s t a bs a b ++==-=-，则有若 0b <，则令11,22q q s t a bs a b ++=-=-=+，则同样有2b t ≤，综上所述，存在性得证．下证唯一性当b 为奇数时，设11a bs t bs t =+=+则11()t t b s s b -=-> 而111,22b bt t t t t t b ≤≤∴-≤+≤ 矛盾 故11,s s t t == 当b 为偶数时，,s t 不唯一，举例如下：此时2b为整数 11312(),,22222b b b b b b b t t ⋅=⋅+=⋅+-=≤§2 最大公因数与辗转相除法 1．证明推论4.1推论4.1 a ，b 的公因数与（a ，b ）的因数相同． 证：设d '是a ，b 的任一公因数，∴d '|a ，d '|b 由带余除法111222111111,,,,,0n n n n n n n n n n a bq r b r q r r r q r r r q r r r r b---++-=+=+=+==≤<<<<∴(,)n a b r =∴d '|1a bq -1r =， d '|122b rq r -=，┄, d '|21(,)n n n n r r q r a b --=+=, 即d '是(,)a b 的因数。

素数模的同余方程素数模的同余方程是数论中的一个重要问题。

在数论中，同余方程是指形如ax ≡ b (mod p)的方程，其中a，b和p都是整数，p是一个素数。

同余方程的解是使得方程成立的整数x。

在解决素数模的同余方程前，首先需要理解一些基本概念。

首先，模运算是指在整数集上定义的一种运算，即对一个数除以另一个数得到的余数。

例如，5 mod 3 = 2，表示将5除以3得到的余数是2。

其次，素数是一种只能被1和自身整除的正整数，没有其他因数。

对于给定的同余方程ax ≡ b (mod p)，我们想要找到满足方程的整数x。

为了解这个问题，我们可以利用同余方程的性质和数论中的定理。

首先，同余方程的一个基本性质是如果a≡b (mod p)，那么对于任意整数n，na≡nb (mod p)。

这个性质可以通过对方程两边同时乘以n来证明。

第二，如果对于整数a和整数p，a和p互质（即它们没有公因数），那么同余方程ax ≡ b (mod p)有唯一解。

这个定理被称为费马小定理。

根据费马小定理的推论，如果p是一个素数，那么对于任意整数a，a^p ≡ a (mod p)。

这个推论对于解决素数模的同余方程非常有用。

例如，对于方程x^2 ≡ 1 (mod p)，其中p是一个素数，我们可以利用费马小定理的推论来求解。

我们首先观察到，如果a是方程的一个解，那么p-a也是方程的一个解。

因为根据模运算的性质，如果a ≡ b (mod p)，那么p-a ≡ p-b (mod p)。

因此，我们只需要找到方程的一个解，然后可以通过计算p-a来得到另一个解。

为了找到方程的一个解，我们可以利用费马小定理的推论。

根据这个推论，我们知道a^2 ≡ 1 (mod p)对于每个不被p整除的整数a成立。

因此，我们只需要找到一个不被p整除的整数a，计算a^2 mod p，然后检查是否等于1。

如果等于1，则a是方程的一个解；否则，我们需要继续寻找下一个候选解。

通过这种方式，我们可以找到方程x^2 ≡ 1 (mod p)的所有解。

初等数论学习总结本课程只介绍初等数论的的基本内容。

由于初等数论的基本知识和技巧与中学数学有着密切的关系， 因此初等数论对于中学的数学教师和数学系(特别是师范院校)的本科生来说，是一门有着重要意义的课程，在可能情况下学习数论的一些基础内容是有益的．一方面通过这些内容可加深对数的性质的了解，更深入地理解某些他邻近学科，另一方面，也许更重要的是可以加强他们的数学训练，这些训练在很多方面都是有益的．正因为如此，许多高等院校，特别是高等师范院校，都开设了数论课程。

最后，给大家提一点数论的学习方法，即一定不能忽略习题的作用，通过做习题来理解数论的方法和技巧，华罗庚教授曾经说过如果学习数论时只注意到它的内容而忽略习题的作用，则相当于只身来到宝库而空手返回而异。

数论有丰富的知识和悠久的历史，作为数论的学习者，应该懂得一点数论的常识，为此在辅导材料的最后给大家介绍数论中着名的“哥德巴赫猜想”和费马大定理的阅读材料。

初等数论自学安排第一章：整数的可除性（6学时）自学18学时整除的定义、带余数除法 最大公因数和辗转相除法 整除的进一步性质和最小公倍数 素数、算术基本定理[x]和{x}的性质及其在数论中的应用习题要求3p ：2，3 ； 8p ：4 ；12p ：1；17p ：1，2，5；20p ：1。

第二章：不定方程（4学时）自学12学时二元一次不定方程c by ax =+多元一次不定方程c x a x a x a n n =++ 2211 勾股数 费尔马大定理。

习题要求29p ：1，2，4；31p ：2，3。

第三章：同余（4学时）自学12学时同余的定义、性质 剩余类和完全剩余系 欧拉函数、简化剩余系欧拉定理、费尔马小定理及在循环小数中的应用 习题要求43p ：2，6；46p ：1；49p ：2，3；53p 1，2。

第四章：同余式（方程）（4学时）自学12学时同余方程概念 孙子定理高次同余方程的解数和解法 素数模的同余方程 威尔逊定理。

高次同余方程解法高次同余方程是数论中一种经典问题，它涉及到模运算和数的整除性质。

解决高次同余方程的方法有很多，本文将介绍其中的几种常见方法。

首先，我们来了解一下什么是高次同余方程。

高次同余方程指的是形如 $ax^n \equiv b \pmod{m}$ 的方程，其中 $a, b, m$ 是已知整数，$n$ 是已知正整数。

解决这类方程的目标是找到一个满足条件的整数解。

一种解决高次同余方程的方法是试位法。

这种方法的基本思想是通过尝试不同的取值来找出满足方程的整数解。

具体步骤如下：1. 准备一个数列 $S$，根据 $n$ 的大小可以选择不同的增量。

例如，如果 $n = 2$，可以选择 $S=\{0,1,2,3,\ldots\}$；如果 $n = 3$，可以选择$S=\{0,1,2,3,4,5,\ldots\}$。

2. 遍历数列 $S$，对于每个数 $s$，计算 $as^n \bmod m$ 的结果。

3. 如果找到某个数 $s$，使得 $as^n \equiv b \pmod{m}$ 成立，则 $s$ 是方程的一个解。

4. 继续遍历数列 $S$，直到找到所有满足条件的解。

试位法的优点是简单易懂，但缺点是效率较低。

当 $m$ 较大、$n$ 较大时，试位法的计算量会非常大，很难在合理的时间内求解。

另一种解决高次同余方程的方法是费马小定理。

费马小定理是数论中的一条重要定理，它表明如果 $p$ 是一个素数，$a$ 是一个不被 $p$ 整除的整数，则 $a^{p-1} \equiv 1 \pmod{p}$。

利用费马小定理，可以简化高次同余方程的求解过程。

具体步骤如下：1. 如果 $n$ 不是一个素数，可以将方程转化为 $a^{n-1} \cdot a \equiv b\pmod{m}$ 的形式。

2. 如果 $n$ 是一个素数，根据费马小定理，可以得到 $a^{n-1} \equiv 1\pmod{n}$。

即方程可简化为 $a \equiv b \pmod{m}$ 的形式。

§4同余式1 基本概念及一次同余式定义 设()110nn n n f x a x a xa --=+++ ，其中()0,0,1,,i n a i n >= 是整数，又设0m >，则()()0mod f x m ≡ （1）叫做模m 的同余式.若()0mod n a m ≡，则n 叫做同余式（1）的次数. 如果0x 满足()()00mod ,f x m ≡则()0mod x x m ≡叫做同余式（1）的解.不同余的解指互不同余的解.当m 及n 都比较小时，可以用验算法求解同余式.如 例1 同余式()543222230mod 7x x x x x +++-+≡仅有解()1,5,6mod 7.x ≡例2 同余式()410mod16x -≡有8个解()1,3,5,7,9,11,13,15mod16x ≡例3 同余式()230mod 5x +≡无解。

定理 一次同余式()()0mod ,0mod ax m a m ≡≡ （2）有解的充要条件是(),.a m b若（2）有解，则它的解数为(),d a m =. 以及当同余式（2）有解时，若0x 是满足（2）的一个整数，则它的(),d a m =个解是()0mod ,0,1,,1mx x k m k d d≡+=- （3） 证 易知同余式（2）有解的充要条件是不定方程ax my b =+ （4）有解. 而不定方程（4）有解的充要条件为()(),,.a m a m b =-当同余式（2）有解时，若0x 是满足（2）的一个整数，则()0mod ,0,1,, 1.m a x k b m k d d ⎛⎫+≡=- ⎪⎝⎭下证0,0,1,,1mx k k d d +=- 对模m 两两部同余. 设 ()00mod ,01,1m mx k x k m k d k d d d ''+≡+≤≤-≤≤-则()mod ,mod ,.m m m k k d k k d k k d d d ⎛⎫'''≡≡= ⎪⎝⎭再证满足（2）的任意一个整数1x 都会与某一个()001mx k k d d+≤≤-对模m 同余. 由()()01mod ,mod ax b m ax b m ≡≡得()101010mod ,mod ,.a a m m ax ax m x x x x d d d d ⎛⎫⎛⎫≡≡≡ ⎪ ⎪⎝⎭⎝⎭故存在整数t 使得10.mx x t d=+由带余除法，存在整数,q k 使得 ,0 1.t dq k k d =+≤≤-于是()()100mod .m mx x dq k x k m d d=++≡+故（2）有解时，它的解数为(),d a m =. 以及若0x 是满足（2）的一个整数，则它的(),a m 个解是()0mod ,0,1,,1mx x k m k d d≡+=- (5) 例1求同余式 ()912m o d 15x ≡ （6）的解. 解 因为()9,15 3.=又因312,故同余式（6）有解，且有三个解.先解()5mod 43≡x , 得().5mod 3≡x 故同余式（6）的三个解为()158mod15,0,1,2.3x k k ≡+= 即 ()3,8,13m o d 15.x ≡ 例2 求同余式 ()6483mod105x ≡ （7）的解. 解 ()831,1105,64= ,同余式有一个解. 将同余式表为21051921916152161054716476418864105836483+≡≡≡+≡≡≡+≡≡x ().105mod 622124≡≡例3 解同余式 325x ≡ 20 (mod 161) 解 ()1161,325= 同余式有一个解, 同余式即是3x ≡ 20 (mod 161) 即.161203y x +=解同余式 161y ≡ -20 (mod 3)， 即2y ≡ 1 (mod 3)， 得到y ≡ 2 (mod 3)，因此同余式的解是x ≡3161220⋅+= 114 (mod 161). 例4 设(a , m ) = 1，并且有整数δ > 0使得 a δ ≡ 1 (mod m )， 则同余式(2)的解是x ≡ ba δ - 1 (mod m ). 解 直接验证即可.注：由例4及Euler 定理可知，若(a , m ) = 1，则x ≡ ba ϕ(m ) - 1 (mod m ) 总是同余式(2)的解.注：本例使用的是最基本的解同余方程的方法，一般说来，它的计算量太大，不实用. 例5 解同余方程组⎩⎨⎧≡-≡+)7(mod 232)7(mod 153y x y x (8) 解 将(8)的前一式乘以2后一式乘以3再相减得到19y ≡ -4 (mod 7)，5y ≡ -4 (mod 7)， y ≡ 2 (mod 7).再代入(8)的前一式得到3x + 10 ≡ 1 (mod 7)，x ≡ 4 (mod 7)即同余方程组(8)的解是x ≡ 4，y ≡ 2 (mod 7).例6 设a 1，a 2是整数，m 1，m 2是正整数，证明：同余方程组⎩⎨⎧≡≡)(mod )(mod 2211m a x m a x (9) 有解的充要条件是a 1 ≡ a 2 (mod (m 1, m 2)). (10)若有解，则对模[m 1, m 2]是唯一的，即若x 1与x 2都是同余方程组(9)的解，则x 1 ≡ x 2 (mod [m 1, m 2]) (11)解 必要性是显然的.下面证明充分性.若式(10)成立，由定理2，同余方程m 2y ≡ a 1 - a 2 (mod m 1)有解y ≡ y 0 (mod m 1)，记x 0 = a 2 + m 2y 0，则x 0 ≡ a 2 (mod m 2)并且x 0 = a 2 + m 2y 0 ≡ a 2 + a 1 - a 2 ≡ a 1 (mod m 1)，因此x 0是同余方程组的解。

第四章 同余式三、解答题1、设(,)1a m =，k 与m 是正整数，又设0(mod )k x a m ≡，证明同余方程(mod )kx a m ≡的一切解x 都可以表示成0(mod )x yx m ≡，其中y 满足同余方程1(mod )ky m ≡。

解：设1x 是0(mod )kx a m ≡的任意一个解，则一次同余方程01(mod )yx x m ≡有解y ，再由001()(mod )k k k k ky a y x yx x a m ≡≡≡≡得1(mod )ky m ≡，即1x 可以表示成0(mod )x yx m ≡，其中y 满足同余方程1(mod )ky m ≡； 反之，易知如此形式的x 是(mod )kx a m ≡的解。

2、解同余方程组()()31mod1047mod15x x ≡⎧⎪⎨≡⎪⎩解：这同余方程组的解与同余方程组()()()()31mod 2,31mod5,47mod3,47mod5x x x x ≡⎧⎪≡⎪⎨≡⎪⎪≡⎩的解相同，但第二个同余方程()31mod5x ≡可化为()2mod5x ≡, 第四个同余方程()47mod5x ≡可化为()2mod5x ≡-, 与()2mod5x ≡矛盾，所以原同余方程组无解.3、设素数2p >,求同余方程()21mod lx p ≡的解 解：同余方程可写为()()()110mod lx x p-+≡由于()1,1|2x x -+,所以上式等价于()10mod lx p -≡或()10mod lx p+≡因此，对任意的1l ≥解为()1,1mod l x p ≡- 解数为2.4、求同余式32()4560(mod 27)f x x x x =-+-≡ 解：∵()0(mod3),()0(mod3)f x f x '≡≡无公解∴20有唯一解0(mod3)x ≡以13x t =代入()0(mod9)f x ≡得1(0)3(0)0(mod9)f t f '+≡ 但(0)3(mod9)f ≡，(0)5(mod9)f '≡故1360(mod 9)t +≡，2120(mod 3)t +≡，11(mod 3)t ≡ 因此12213,39t t x t =+=+是()0(mod9)f x ≡的唯一解将239x t =+代入()0(mod 27)f x ≡得2(3)9(3)0(mod 27)f t f '+≡ 但(3)0(mod 27)f ≡，(3)8(mod 27)f '≡故2890(mod 27)t ⋅≡，280(mod 3)t ≡，20(mod3)t ≡设2333,327,3(mod 27)t t x t x ==+≡是()0(mod 27)f x ≡的唯一解。

第一章 整数的可除性§1 整除的概念·带余除法 1．证明定理3定理3 若12n a a a ，，，都是m 得倍数，12n q q q ，，，是任意n 个整数，则1122n n q a q a q a +++是m 得倍数．证明：12,,n a a a 都是m 的倍数。

∴ 存在n 个整数12,,n p p p 使 1122,,,n n a p m a p m a p m ===又12,,,n q q q 是任意n 个整数1122n nq a q a q a ∴+++1122n n q p m q p m q p m =+++1122()n n p q q p q p m =+++即1122n n q a q a q a +++是m 的整数2．证明 3|(1)(21)n n n ++ 证明(1)(21)(1)(21)n n n n n n n ++=+++-(1)(2)(1)(1)n n n n n n =+++-+ 又(1)(2)n n n ++，(1)(2)n n n -+是连续的三个整数故3|(1)(2),3|(1)(1)n n n n n n ++-+3|(1)(2)(1)(1)n n n n n n ∴+++-+从而可知3|(1)(21)n n n ++3．若00ax by +是形如ax by +（x ，y 是任意整数，a ，b 是两不全为零的整数）的数中最小整数，则00()|()ax by ax by ++．证：,a b 不全为0∴在整数集合{}|,S ax by x y Z =+∈中存在正整数，因而有形如ax by +的最小整数00ax by +,x y Z ∀∈，由带余除法有0000(),0ax by ax by q r r ax by +=++≤<+则00()()r x x q a y y q b S =-+-∈，由00ax by +是S 中的最小整数知0r =00|ax by ax by ∴++00|ax by ax by ++ （,x y 为任意整数） 0000|,|ax by a ax by b ∴++ 00|(,).ax by a b ∴+ 又有(,)|a b a ，(,)|a b b 00(,)|a b ax by ∴+ 故00(,)ax by a b +=4．若a ，b 是任意二整数，且0b ≠，证明：存在两个整数s ，t 使得||,||2b a bs t t =+≤成立，并且当b 是奇数时，s ，t 是唯一存在的．当b 是偶数时结果如何？ 证：作序列33,,,,0,,,,2222b b b b b b ---则a 必在此序列的某两项之间即存在一个整数q ，使122q q b a b +≤<成立 ()i 当q 为偶数时，若0.b >则令,22q qs t a bs a b ==-=-，则有 02222b q q qa bs t ab a b b t ≤-==-=-<∴<若0b < 则令,22q qs t a bs a b =-=-=+，则同样有2b t <()ii 当q 为奇数时，若0b >则令11,22q q s t a bs a b ++==-=-，则有若 0b <，则令11,22q q s t a bs a b ++=-=-=+，则同样有2b t ≤，综上所述，存在性得证．下证唯一性当b 为奇数时，设11a bs t bs t =+=+则11()t t b s s b -=-> 而111,22b bt t t t t t b ≤≤∴-≤+≤ 矛盾 故11,s s t t == 当b 为偶数时，,s t 不唯一，举例如下：此时2b为整数 11312(),,22222b b b b b b b t t ⋅=⋅+=⋅+-=≤§2 最大公因数与辗转相除法 1．证明推论4.1推论4.1 a ，b 的公因数与（a ，b ）的因数相同． 证：设d '是a ，b 的任一公因数，∴d '|a ，d '|b 由带余除法111222111111,,,,,0n n n n n n n n n n a bq r b r q r r r q r r r q r r r r b---++-=+=+=+==≤<<<<∴(,)n a b r =∴d '|1a bq -1r =， d '|122b r q r -=，┄, d '|21(,)n n n n r r q r a b --=+=,即d '是(,)a b 的因数。

高次同余式的解数及解法本节初步讨论高次同余式的解数与解法：先把合数模的同余式化成质数模的同余式，然后通过下一节来解质数模的同余式。

A回顾与强调二、同余式解的相关定理上一节由孙子定理：设m1,m2,L,mk是正整数，(mi,mj)=1，m=m1m2Lmk，Mi=，MiMi＇≡1(modmi)，同余式组（同余方程组）(1)的解为(modm)。

反过来，解同余式，可将它化为同余式组，于是，有下面的定理B重要定理证明的讲解定理1设m=m1m2Lmk，其中m1,m2,L,mk是两两互素的正整数，f(某)是整系数多项式，则A：同余式f(某)≡0(modm)（1）与同余式组f(某)≡0(modmi)（1≤i≤k）（2）等价；B：以T与T（分别表示f(某)≡0(modm)与f(某)≡0i1≤i≤k）(modmi)（1≤i≤k）的解的个数，则T=T1T2…Tk证明A：设某0是适合（1）的解，即f(某0)≡0(modm)，由整除的性质知f(某0)≡0(modmi)，1≤i≤k，反之，设某0是适合（2）的解，即f(某0)≡0(mo dmi)，1≤i≤k，则m1,m2,L,mk是两两互素的正整数知，f(某0)≡0(modm)，故（1）与（2）同解。

B：设同余方程(2)的全部解是(modmi)，（3）即模mi有Ti个解，则同余方程组(2)等价于下面的T1T2…Tk个方程组：（4）其中通过式(3)中的数值，即通过同余方程(1)的全部解。

由孙子定理，对于选定的每一组{}，同余方程组(4)对模m有唯一解，而当每个通过(3)式中的值时，由孙子定理的证明知所得到的T1T2…Tk个同余方程组(4)的解对于模m都是两两不同余的。

证毕。

由定理4及算术基本定理，设，从而，解一般模的同余方程可以转化为解模为素数幂的同余方程组下面我们利用数学中的化归思想对模pα的同余方程做进一步讨论容易看出，若某0是同余方程f(某)≡0(modpα)(5)的解，则它必是方程f(某)≡0(modpα-1)(6)的解，因此，必有与某0相应的方程(6)的某个解某1，使某0≡某1(modpα-1)，某0=某1+pα-1t0，t0∈Z。

第四章 同余式§1 基本概念及一次同余式作为一个解。

中的一切数，即成立，故把都能使中的任意整数，则剩余类的合理性：若定义的一个解。

叫做成立的一个整数，则是使若称为次数。

，则的同余式。

若称为模，则，其中，设余方程）的求解问题。

课题是研究同余式（同初等数论中的一个基本)(mod )(mod 0)()(mod 0)(2)(mod 0)()(mod )(mod 0)()(mod 0)(mod 0)()(011m a x K m a f a K m a f m x f m a x m a f a n m a m m x f a a x a x a x f m a a n i n n n n ≡≡''≡≡≡≡≡/≡∈+++=∈--+定义2定义1Z Z 。

，解数为，的解为同余式，所以，，的一切整数解为因为不定方程。

有解不定方程有解同余式的任一个解。

是同余式其中，，个解，它们是余式共有。

当此条件成立时，同有解的充分必要条件是，则一次同余式设d d k m dmk x x m b ax t t dmx x b my ax b d b my ax m b ax m b ax x d k m dmk x x d b d m b ax d m a 1,,1,0)(mod )(mod )2(|)(mod )1()(mod 1,,1,0)(mod |)(mod ),(0000-=⋅+≡≡∈+==+⇔=+⇔≡≡-=⋅+≡≡= Z 证明定理。

解时，一次同余式有唯一当)(mod 1),(1)(m b a x m a m -≡=ϕ注同余式的解法1、代入法（适用于模较小时） 。

，得的完全剩余系逐一代入以，，所以同余式有唯一解因为解同余式)17(mod 6171)17,3()17(mod 13≡=≡x x 解例1 2、公式法（适用于模较小时） 。

从而，，，所以同余式有唯一解因为解同余式)11(mod 8656)2()2()3(98981)11,8()11(mod 98491101)11(≡⋅≡⋅-≡-⋅-≡⋅≡⋅≡=≡--ϕx x 解例23、变换系数法。

§4 质数模的同余式本节考虑质数模的同余式()()()1100mod ,,n n n n f x p f x a x a x a --≡=+++ （1）其中p 是质数，()/0mod .n a p ≡定理1 设()/|,p x x f x -则同余式（1）与一个次数不超过1p -的质数模p 的同余式等价。

证 因多项式p x x -的首项系数为1，故由多项式的带余除法得，存在两个整系数多项式使得()()()()()(), 1.p f x x x q x r x r x p =-+∂≤-由费马定理得，对任意整数x ，总有()()()mod .f x r x p ≡故同余式（1）与同余式()()0mod r x p ≡等价。

定理2 设,k n ≤而()()mod 1,2,,i x p i k α≡=是（1）的k 个不同的解，则存在一个一个首项系数为1的n k -次整系数多项式()k f x 使得，对任意整数x 总有()()()()()12.k k f x x x x f x ααα≡--- （2）证 对k 作数学归纳法。

（ⅰ） 由多项式的带余除法得，存在一个首项系数为n a 的1n -次整系数多项式()1f x 及整数r 使得()()()11.f x x f x r α=-+由此易得，()1.r f α=但有假设得，()()10mod .f p α≡故()0mod .r p ≡于是，对任意整数x ，总有()()()()11mod .f x x f x p α≡-即命题结论对1k =成立。

（ⅱ）假设命题结论对()12k k -≥成立，下证命题结论对k 也成立。

由归纳假设，存在一个首项系数为n a 的()1n k --次整系数多项式()1k f x -使得，对任意整数x ，总有()()()()()()1211mod .k k f x x x x f x p ααα--≡--- （3）因k α为（1）的一个解，故由（3）得()()()()()12110mod .k k k k k k f p ααααααα-----≡但12,,,k ααα两两对模p 不同余，故/|,1,2,, 1.k i p i k αα-=-于是由上式得()()10mod ,k k f p α-≡即()mod k x p α≡为同余式()()10mod k f x p -≡的一个解。