初等数论_第五章__同余方程

《初等数论_第五章__同余方程》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第五章同余方程本章主要介绍同余方程的基础知识，并介绍几类特殊的同余方程的解法。第一节同余方程的基本概念本节要介绍同余方程的基本概念及一次同余方程。在本章中，总假定m是正整数。定义1设f(x)=anxn+L+a1x+a0是整系数多项式，称f(x)º0(modm)(1)是关于未知数x的模m的同余方程，简称为模m的同余方程。若an0(modm)，则称为n次同余方程。定义2设x0是整数，当x=x0时式(1)成立，则称x0是同余方程(1)的解。凡对于模m同余的解，被视为同一个解。同余方程(1)的解数是指它的关于模m互不同余的所有解的个数，也即在模m的一个完全剩余系

2、中的解的个数。由定义2，同余方程(1)的解数不超过m。定理1下面的结论成立：(ⅰ)设b(x)是整系数多项式，则同余方程(1)与f(x)+b(x)ºb(x)(modm)等价；(ⅱ)设b是整数，(b,m)=1，则同余方程(1)与bf(x)º0(modm)等价；(ⅲ)设m是素数，f(x)=g(x)h(x)，g(x)与h(x)都是整系数多项式，又设x0是同余方程(1)的解，则x0必是同余方程g(x)º0(modm)或h(x)º0(modm)36的解。证明留做习题。下面，我们来研究一次同余方程的解。定理2设a，b是整数，a0(modm)。则同余方程axºb(mod

3、m)(2)有解的充要条件是(a,m)½b。若有解，则恰有d=(a,m)个解。证明显然，同余方程(2)等价于不定方程ax+my=b，(3)因此，第一个结论可由第四章第一节定理1得出。若同余方程(2)有解x0，则存在y0，使得x0与y0是方程(3)的解，此时，方程(3)的全部解是，tÎZ。(4)由式(4)所确定的x都满足方程(2)。记d=(a,m)，以及t=dq+r，qÎZ，r=0,1,2,L,d-1，则x=x0+qm+(modm)，0£r£d-1。容易验证，当r=0,1,2,L,d-1时，相应的解对于模m是两两不同余的，所以同余方程(2)恰有d个解。证毕。

4、在定理的证明中，同时给出了解方程(2)的方法，但是，对于具体的方程(2)，常常可采用不同的方法去解。例1设(a,m)=1，又设存在整数y，使得a½b+ym，则xº(modm)是方程(2)的解。解直接验算，有axºb+ymºb(modm)。36注：例1说明，求方程(2)的解可以转化为求方程myº-b(moda)(5)的解，这有两个便利之处：第一，将一个对于大模m的同余方程转化为一个对于小模a的同余方程，因此有可能通过对模a的完全剩余系进行逐个验证，以求出方程(5)和(2)的解；第二，设mºr(moda)，r

5、。例2解同余方程325xº20(mod161)(6)解同余方程(6)即是3xº20(mod161)。解同余方程161yº-20(mod3)，2yº1(mod3)，得到yº2(mod3)，因此方程(6)的解是xº=114(mod161)。例3设a>0，且(a,m)=1，a1是m对模a的最小非负剩余，则同余方程a1xº-b(modm)(7)等价于同余方程(2)。解设x是(2)的解，则由m=+a1得到(modm)，即x是同余方程(7)的解。但是由假设条件可知同余方程(2)与(7)都有且只有一个解。所以这两个同余方程等价。注：用本例的方法，可以将同余方程(2)转

6、化成未知数的系数更小一些的同余方程，从而易于求解。例4解同余方程6xº7(mod23)。解由例3，依次得到6xº7(mod23)Û5xº-7×3º2(mod23)Û3xº-2×4º-8(mod23)36Û2xº-8(-7)º10(mod23)Ûxº5(mod23)。例5设(a,m)=1，并且有整数d>0使得adº1(modm)，则同余方程(2)的解是xºbad-1(modm)。解直接验证即可。注：由例5及Euler定理可知，若(a,m)=1，则xºbaj(m)-1(modm)总是同余方程(2)的解。例6解同余方程81x3+24x2+5x+23º0(mod

7、7)。解原同余方程即是-3x3+3x2-2x+2º0(mod7)。用x=0，±1，±2，±3逐个代入验证，得到它的解是x1º1，x2º2，x3º-2(mod7)。注：本例使用的是最基本的解同余方程的方法，一般说来，它的计算量太大，不实用。例7解同余方程组。(8)解将(8)的前一式乘以2后一式乘以3再相减得到19yº-4(mod7)，5yº-4(mod7)，yº2(mod7)。再代入(8)的前一式得到3x+10º1(mod7)，xº4(mod7)。即同余方程组(8)的解是xº4，yº2(mod7)。例8设a1，a2是整数，m1，m2是正整数，证明：同余方程

8、组(9)36有解的充要条件是a1ºa2(mod(m1,m2))。(10)若有解，