初等数论 第四章 同余式

2024/5/61第四章同余式§4.1基本概念及一次同余式2024/5/62一、基本概念是关于模m的同余方程，或同余式。则称为n次同余方程。

则剩余类里的元素都满足该方程。

定义12024/5/63定义2

设a是整数，当

成立时，则称是同余方程(1)的一个解。

即与a同余的一切整数作为（1）式的一个解。注：同余方程(1)的解数是指它的关于模m互不同余的所有解的个数，也即在模m的一个完全剩余系中的解的个数。显然，同余方程(1)的解数不超过m。2024/5/64二、等价同余式定理1

下面的结论成立：（1）设b(x)是整系数多项式，则同余方程(1)与f(x)

b(x)

b(x)(modm)等价；（2）设b是整数，(b,m)=1，则同余方程(1)与

bf(x)

0(modm)等价；（3）设m是素数，f(x)=g(x)h(x)，g(x)与h(x)都是整系数多项式，又设x0是同余方程(1)的解，则x0必是同余方程g(x)

0(modm)或h(x)0(modm)的解。2024/5/65三、一次同余方程的基本解法定理2

设a，b是整数，a0(modm)。则同余方程

ax

b(modm)(2)

有解的充要条件是(a,m)

b。

若有解，则恰有d=(a,m)个解。

特别地，若(a,m)＝1，则方程（2）有唯一解。证明ax

b(modm)

同余方程(2)等价于不定方程

ax

my=b，(3)因此，第一个结论可由第二章第一节定理1〔P25〕得出。2024/5/66若同余方程(2)有解x0，则存在y0，使得x0与y0是方程(3)的解，由式(4)所确定的x都满足方程(2)。

ax

b(modm)(2)

ax

my=b

(3)此时，方程(3)的解是记d=(a,m)，以及t=dq

r，q

Z，r=0,1,2,

,d

1.0

r

d

1。

2024/5/67容易验证，当r=0,1,2,

,d

1时，相应的解对于模m是两两不同余的，所以同余方程(2)恰有d个解。解方程(2)的方法：先求出相应不定方程

ax

my=b的一个特解

2024/5/68例1解同余式故原同余式有3个解。所以原同余式的解为2024/5/69四、其他解法定理3ax

b(modm)证:直接验算，有

ax

b

ym

b(modm)。

注：

将一个对于较大模m的同余方程转化为一个对于较小模a的同余方程，设m

r(moda)，r<a，则又可继续转化成一个对于更小的模r的同余方程。

——减小模2024/5/610例2

解同余方程325x

20(mod161)

解d=1,原同余方程即是3x

20(mod161)。解同余方程161y

20(mod3)，2y

1(mod3)，得到y

2(mod3)，因此原方程的解是2024/5/611补充说明2024/5/612例1解同余式另解：先解同余方程2024/5/613四、其他解法——减小系数定理4设a>0，且(a,m)=1，a1是m对模a的最小非负剩余，则同余方程等价于同余方程ax

b(modm)

证：设x是ax

b(modm)的解，

即x是同余方程

的解。

由假设条件知：这两个同余方程都有且只有一个解，所以这两个同余方程等价。2024/5/614例3解同余方程6x

7(mod23)。解由定理4，依次得到6x

7(mod23)

5x

7

3

2(mod23)

3x

2

4

8(mod23)

2x

8×7

10(mod23)

x

5(mod23)。ax

b(modm)

2024/5/615定理5四、其他解法——应用欧拉定理设(a,m)=1，并且有整数

>0使得

a

1

(modm)，

则同余方程ax

b(modm)的解是x

ba

1

(modm).注1：直接验证即可。注2：由定理5及Euler定理可知，若(a,m)=1，则x

ba

(m)

1

(modm)是同余方程ax

b(modm)的解。例4解同余方程解：x

ba

(21)

1

2024/5/616五、简单同余方程组〔模相同〕的解法例5解同余方程组解:将(*)的前一式乘以2，后一式乘以3，相减得到(*)19y

4(mod7)，即5y

4(mod7)，y

2(mod7)。再代入(*)的前一式得到

3x

10

1(mod7)，

x

4(mod7)。即同余方程组(*)的解是x

4，y

2(mod7)。注：同余方程组的解法与方程组的解法相似。2024/5/617§4.2孙子定理2024/5/618问题：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何。〔《孙子算经》〕分析：设所求物数为x，则有

称之为同余式组。即要求这些同余式的公共解。2024/5/619问题：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何。〔《孙子算经》〕为什么啊？除数余数最小公倍数衍数乘率各总答数最小答数323×5×7=1055×7235×2×3140+63+30=233233-2×105=23533×7121×1×3723×5115×1×22024/5/620问题1：今有物不知其数，三三数之剩二，五五数之剩二，七七数之剩二，问物几何。问题2：今有物不知其数，三三数之剩二，五五数之剩三，问物几何。x-2是3、5、7的公倍数。2024/5/621问题：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何。〔《孙子算经》〕2024/5/622一、同余式组的解法——中国剩余定理定理1[孙子定理]m1,m2,

,mk是两两互质的正整数，

记m=m1m2

mk，

则(1)的解为

其中，整数Mi

（1

i

k），满足MiMi

1(modmi).

设有同余式组2024/5/623证明：由(Mi,mi)=1，利用辗转相除法可以求出Mi

与yi，使得MiMi

yimi=1，

aiMiMi

ai(modmi)，1

i

k。2024/5/624反之，若是（1）的解，

又m1,m2,

,mk两两互质，

故方程（1）的解只能为（2）式。2024/5/625例1解同余式组衍数乘率2024/5/626例2〔韩信点兵〕有兵一队，若列成五行纵队，则末行1人；成六行纵队，则末行5人；成七行纵队，则末行4人；成十一行纵队，则末行10人。求兵数。——余数——衍数2024/5/627列表如下：5

1

2310

462

6

5

385

7

4

330

11

10

210

其他略1×462×3

5×385×1

4×330×1

10×210×1

673131112024/5/628定理2

在定理1的条件下，若式(1)中的a1,a2,

,ak分别通过模m1,m2,,mk的完全剩余系，则式(2)中的x通过模m1m2

mk的完全剩余系。证明：则x通过m1m2

mk个整数，

且容易它们是两两不同余的。2024/5/629二、同余方程组解的存在性及解数的判定引理：设a1，a2是整数，m1，m2是正整数，则同余方程组有解的充要条件是a1

a2(mod(m1,m2))

(4)若有解，则对模[m1,m2]是唯一的，即若x1与x2都是同余方程组(3)的解，则x1

x2(mod[m1,m2])。(5)证

〔必要性〕2024/5/630〔充分性〕记(m1,m2)＝d.若式(4)成立，则同余方程m2y

a1

a2(modm1)有解y

y0(modm1)，

记x0=a2

m2y0，则x0

a2(modm2).并且x0=a2

m2y0

a2

a1

a2

a1(modm1)，因此x0是同余方程组(3)的解。若x1与x2都是方程组(3)的解，

则x1

x2(modm1)，x1

x2(modm2)，从而有x1

x2(mod[m1,m2])。2024/5/631定理3

同余方程组(1)有解的充要条件是ai

aj(mod(mi,mj))，1

i,j

n。(6)2024/5/6322024/5/6332024/5/634§4.3高次同余式的解数及解法2024/5/635一、化合数模为两两互质的模例1解同余方程

5x2

6x

49

0(mod60)。（1）解：∵60=3

4

5，∴同余方程(1)等价于同余方程组5x2

6x

49

0(mod3)即-x2

1

0(mod3)(2)5x2

6x

49

0(mod4)即x2

2x

1

0(mod4)(3)5x2

6x

49

0(mod5)即x-10(mod5)(4)由(2)得：x1(1)

1，x2(1)

1(mod3)，由(3)得：x1(2)

1，x2(2)

1(mod4)，由(4)得：x1(3)

1(mod5)2024/5/636这样，同余方程(1)的解x可由下面的方程组决定：x1(1)

1，x2(1)

1(mod3)，x1(2)

1，x2(2)

1(mod4)，x1(3)

1(mod5)x

a1(mod3)，x

a2(mod4)，x

a3(mod5)，其中a1=1或1，a2=1或1，a3=1。

利用孙子定理，其中m1=3，m2=4，m3=5，m=60.M1=20，M2=15，M3=12，M1

=2，M2

=

1，M3

=3，则x

40a1

15a2

36a3(mod60)。将a1，a2，a3所有可能的取值代入上式，得到方程(1)的全部解是x1

1(mod60)，x2

19(mod60)，x3

31(mod60)，x4

11(mod60)。2024/5/637注：由定理4及算术基本定理，解一般模的同余方程可以转化为解模为素数幂的同余方程。定理4

设m=m1m2

mk，其中m1,m2,,mk是两两互素的正整数，f(x)是整系数多项式，以T与Ti（1

i

k）分别表示同余方程f(x)0(modm)（1）与f(x)0(modmi)，1

i

k.（2）的解的个数，则T=T1T2…Tk。2024/5/638定理的证明：因为a

b(modmi

)，1

i

k

a

b(modm)，所以同余方程(1)等价于同余方程组（2）f(x)0(modm)（1）f(x)0(modmi)，1

i

k.（2）对于每个i（1

i

k），设同余方程(2)的全部解是则同余方程组(3)等价于下面的T1T2…Tk个方程组：其中通过式(3)中的数值，即通过方程(2)的全部解。2024/5/639f(x)0(modm)（1）f(x)0(modmi)，1

i

k.（2）由孙子定理，对于选定的每一组同余方程组(4)对模m有唯一解。

而且，由§4.2－定理2，

当每个通过(3)式中的值时，

所得到的T1T2…Tk个同余方程组(4)的解对于模m都是两两不同余的。2024/5/640二、方幂模的解法若x0是同余方程f(x)

0(modp

)

(1)的解，则必是方程f(x)

0(modp

-1)

(2)的解.因此，必有与x0相应的方程(2)的某个解x1，使x0

x1(modp)，x0=x1

p

-1

t0，即可以从方程(2)的解中去求方程(1)的解。但对于方程(2)的每个解x1，是否必有方程(1)的解x0与之对应？若有，如何去确定它？

2024/5/641定理5

设p是素数，n

2，f(x)=anxn

a1x

a0是整系数多项式，又设x1是同余方程(2)的一个解。以f

(x)表示f(x)的导函数。则对于t=0，1,2,

,p

1，式(3)中的x都是方程(1)的解。f(x)

0(modp

)

(1)f(x)

0(modp

-1)

(2)是方程(1)的解。2024/5/642证明：如何确定式(3)中的t，使x1

p

1t满足同余方程(1)，

an(x1+p

1t)n+an

1(x1+p

1t)n

1+

+a1(x1+p

1t)+a0

0(modp

)

即要使由二项式定理展开可得

f(x1)

p

1tf

(x1)

0(mod

p

)

（4）f(x)

0(modp

)

(1)f(x)

0(modp

-1)

(2)下面考虑两种情形2024/5/643(1)若f

(x1)0(modp)，

则关于t的同余方程(5)有唯一解t

t0(modp)，

即t=t0

pk（k

Z），

于是

x

x1

p

1t0

(modp

)

是同余方程(1)的解。(2)若f

(x1)0(modp)，并且f(x1)0(modp

)，

则式(5)对于任意的整数t成立，

即同余方程(5)有p个解

t

i(modp)，0

i

p

1。于是x

x1

p

1i(modp

)，0

i

p

1，都是同余方程(1)的解。

2024/5/6442024/5/645例2解同余方程考虑方程：则(2)的解可表示为：代入(2)，得2024/5/646则(2)的解可表示为：即(2)的解可表示为：从而(1)的解可表示为：2024/5/647推论1若x

a(modp)是同余方程

2024/5/648推论22024/5/649三、一般高次同余式的解法例3解同余方程x3

3x

14

0(mod45)

解：原同余方程等价于同余方程组x3

3x

14

0(mod9)，(1)x3

3x

14

0(mod5).(2)先求(1)的解：x3

3x

14

0(mod3)的解为x

2(mod3)。令x=2

3t并代入方程(1)，得到(2

3t)3

3(2

3t)

14

0(mod9)，恒成立。于是方程(1)的解是x

2，5，8(mod9)。

2024/5/650例3解同余方程x3

3x

14

0(mod45)

(2)的解为：x

1，2(mod5)。解：原同余方程等价于同余方程组x3

3x

14

0(mod9)，(1)x3

3x

14

0(mod5).(2)(1)的解是：x

2，5，8(mod9)。x

a1(mod9)，a1=2，5，8，x

a2(mod5)，a2=1，2。因此，原同余方程的解是下面六个同余方程组的解：利用孙子定理解这六个方程组.2024/5/651记m1=9，m2=5，m=45，M1=5，M2=9，

将a1和a2的不同取值代入，得到所求的解是x1

10

2

9

1

11(mod45)，x2

10

2

9

2

2(mod45)，x3

10

5

9

1

41(mod45)，x4

10

5

9

2

32(mod45)，x5

10

8

9

1

26(mod45)，x6

10

8

9

2

17(mod45)

2024/5/652§4.4质数模的同余式2024/5/653在上节证明了，对于素数p，模p

的同余方程的求解可以转化为模p的同余方程的求解。本节要对素数模的同余方程做些初步研究。以下，设f(x)=anxn

a1x

a0是整系数多项式，

2024/5/654f(x)=anxn

a1x

a0

0(modp)(1)定理1

同余方程与一个次数不超过p-1的同余式等价。证：由带余数除法，存在整系数多项式由费马定理知，2024/5/655定理2

设k

n，若同余方程(1)有k个不同的解其中fk(x)是一个次数为n

k的整系数多项式，x1,x1,

,xk，则对有f(x)

(x

x1)(x

x2)

(x

xk)fk(x)(modp)，并且它的xn

k项的系数是an.证明：由多项式除法，有f(x)=(x

x1)f1(x)

r1，(2)f1(x)是首项系数为an的n

1次整系数多项式，r1是常数。

在式(2)两边令x=x1，则可知f(x1)=r1

0(modp)，

因此，式(2)成为

f(x)

(x

x1)f1(x)(modp)

(3)即当k=1时，定理成立。

2024/5/656如果k>1，在(3)式中，令x=xi（i=2,3,

,k），

则有0

f(xi)(xi

x1)f1(xi)(modp)

(4)由于x1,

x2,

,xk对于模p是两两不同余的，

f1(xi)

0(modp)，i=2,

,k。(5)所以，由(4)式得出由此及归纳法，即可证明定理。f(x)

(x

x1)f1(x)(modp)

(3)2024/5/657定理3(1)若p是素数，则对于任何整数x，有

x

p

1

1

(x

1)(x

2)

(x

p

1)(modp)。(2)〔Wilson定理〕

证明:(1)由Fermat定理，数1,2,

,p

1是同余方程x

p

1

1(modp)，即x

p

1

1

0(modp)的解，

因此，利用定理2可得

x

p

1

1

(x

1)(x

2)

(x

p

1)fk(x)(modp)其中fk(x)＝an＝1，所以x

p

1

1

(x

1)(x

2)

(x

p

1)(modp)。2024/5/658定理4

同余方程(1)的解数

n。证明:假设同余方程(1)有n+1个不同的解x

xi(modp)，1

i

n

1。由定理2，有f(x)

an(x

x1)

(x

xn)(modp)，

因此0

f(xn+1)

an(xn+1

x1)

(xn+1

xn)(modp)。

矛盾！2024/5/659定理5设n

p，则同余方程f(x)=xn

an

1xn

1

a1x

a0

0(modp)(1)有n个解的充要条件是

存在整数多项式q(x)和r(x)，r(x)的次数<n，使得

x

p

x=f(x)q(x)

p

r(x)。

证明〔必要性〕由多项式除法，存在整系数多项式

q(x)与r1(x)，r1(x)