初等数论同余式.ppt

第四章同余式
§1同余方程的基本概念定义：设,则叫做模m的同余方程若,则称n为同余方程的次数。
若，则称为同余式的解
模m的一个完全剩余系中满足同余方程的个数称为满足同余方程的解数。注：对模m互相同余的解是同一个解。
例：同余式
次数为2，是解，也是解，因为
所以为同一解，解数是1，
为了求方程的解经常有等价变形的问题，对于同余方程同样也有等价变形，即使原同余方程和新的同余方程互相等价的若干变换。常用的变换有
（1）移项运算是传统的，
（2）同余方程两边也可以加上模的若干倍。相当于同余方程两边加“零”。
（3）乘上一数k或除去一个数k，为了保持其同解性，必须（k,m）=1，这一点和同余的性质有区别。例等价于

等价于
即
，
同余方程和不定方程一样，我们同样要考虑以下三个问题，
即有解的条件，解数及如何求解，
一般地说，对于一般的同余方程，由于仅有有限个解，只要把模m的一个完全剩余系一一代入即可，满足同余方程的就是解。
但当模较大或次数较高时应寻求简洁而实用的解法.
这一章主要讨论
1、一次同余方程ax≡b(modm)
２、一次同余方程组
x≡b1(modm1)
x≡b2(modm2)
…
x≡bk(modmk)
３的求解。
证明：由同余的定义知ax≡b(modm)等价于不定方程ax=b-my，而此不定方程有解的充要条件是(a,m)|b。在有解的情况下，设不定方程的解为

此时同余方程有d个解，为

因当时，
2.2一次同余方程ax≡b(modm)的解法。
（1）化为不定方程ax+my=b
例：解同余式
解因为(45,132)=3¦21,所以同余式有3个解.
化简为等价的同余方程
我们再解不定方程15x-44y=7,得到一解(21,7).,
方程3个解为
即为2)利用欧拉定理若(a,m)=1,则有
ax≡b(modm),两边同乘，则有
即
因为
所以例:解同余式
解：因为(8,11)=1,所以由欧拉定理有

(3)用形式分数
定义1：当（a，m）=1时，若ab1(modm)，则记b(modm)称为形式分数。
根据定义和记号，有性质
1、

2、（d，m）=1，且，则
利用形式分数的性质把分母变成1，从而求出一次同余式的解。例：解一次同余方程
解：∵（17，25）=1，原同余方程有解，利用形式分数的性质，同余方程解为

下面给出k=2时的证明.下面我们给出模两两互素的情形，此时显然满足有解的条件，即
孙子定理：设两两互素，
则同余式(*)组的解为

其中

证明：因为两两互素，
所以有中的存在，又对任意的有有
所以即是(*)的解
若是满足(*)的两个整数，则有
又,所以有,即
,说明是惟一解。注：若给出的同余方程组不是标准形式，必须注意化为标准形式，同时我们得到的有解的判别定理及求解方法都是在这一标准形式得到的。
同余方程组（1）有解的条件
(mi,mj)∣bi-bj，1≤i，j≤k。
在使用时一定要对所有的组合进行验算，进行有解的判别求解一次同余方程组（*）有两种方法：待定系数法和孙子定理,二种方法各有特长。待定系数法适应的范围较广，对模没有什么要求。孙子定理有一个具体的公式，形式也较漂亮。但对模要求是两两互素。
次数大于1的同余方程称为高次同余方程，一般地高次同等方程可转化一系列的高次同余方程组。然后将每一个高次同余方程的解都求出，最后利用孙子定理可求出原高次同余方程的解。
§4高次同余方程
定义1、次数大于1的同余方程称为高次同余方程

对一般模的高次同余方程我们要通过“小模”和“降次”的方法来得到一般模的高次同余方程的解。证明：若是（1）的解，即则从而有，即即（1）的解就是（2）的解，反之若是（2）的解，则有
即从而有由于两两互素，所以
，从而有即即（2）的解也是（1）的解。又由于（2）中第i个方程有个解，则（2）一共可组合成个一次同余式组，由孙子定理每一个同余式组有惟一解，所以有个解，又由于（1）（2）的等价性，所以有

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

即有
所以有4解，由孙子定理为
由于所以
等价于同余方程组
从而从理论上说只要能解即可，而由性质可知若x是的解，则一定是的解
所以只要在的解中找的解。
所以理论上只要解素数模同余方程即可。对素数模同余方程，可以降次，看下面的
定理：设p是素数，是整系数多项式，设是的一个解，则有
（1）则存在整数t使得
是的解。
（2）且，则当t=0，1，2…P-1时，都是的解。所以有代入有两边同除25有
有代入x有
即是方程的解。
同理从可得到另一解（作练习）
从上可知解最后可归结为解即可，下面讨论的解法。§5素数模同余方程（*）定理2：设同余方程（*）有k个不同的解,则对于任意的x有
,其中是一个次数为n-k的整系数多项式，且它的的系数为
注:这个定理同一般方程类