《初等数论同余式》由会员分享，可在线阅读，更多相关《初等数论同余式（41页珍藏版）》请在金锄头文库上搜索。
1、第四章 同余式 1 同余方程的基本概念 定义：设 , 则 叫做模m的同余方程 若 ,则称n为同余方程的次数。若 ， 则 称为同余式的解模m的一个完全剩余系中满足同余方程的个数称为满足同余方程的解数。,注：对模m互相同余的解是同一个解。例：同余式次数为2， 是解， 也是解，因为 所以为同一解，解数是1，,为了求方程的解经常有等价变形的问题， 对于同余方程同样也有等价变形，即使原同余方程和新的同余方程互相等价的若干变换。常用的变换有（1）移项运算是传统的，（2）同余方程两边也可以加上模的若干倍。相当于同余方程两边加“零”。（3）乘上一数k或除去一个数k，为了保持其同解性，必须（k ,m）=1，这一
2、点和同余的性质有区别。,例 等价于 等价于 即 ，,同余方程和不定方程一样，我们同样要考虑以下三个问题，即有解的条件，解数及如何求解，一般地说，对于一般的同余方程，由于仅有有限个解，只要把模m的一个完全剩余系一一代入即可，满足同余方程的就是解。 但当模较大或次数较高时应寻求简洁而实用的解法.,这一章主要讨论1、一次同余方程axb(mod m)、一次同余方程组xb1(mod m1)xb2(mod m2) xbk(mod mk) 的求解。, 2 一次同余方程一次同余方程的一般形式为axb(mod m)， 有2.1定理：a,b为整数， ，则axb(mod m)有解的充要条件是(a,m)|b,若有解则
3、有d=(a,m)个关于模m的解,证明：由同余的定义知axb(mod m)等价于不定方程ax=b-my，而此不定方程有解的充要条件是(a,m)|b。在有解的情况下，设不定方程的解为 此时同余方程有d个解，为因当 时，,2.2 一次同余方程axb(mod m)的解法。（1）化为不定方程ax+my=b例：解同余式解 因为(45,132)=321,所以同余式有3个解. 化简为等价的同余方程 我们再解不定方程15x-44y=7,得到一解(21,7)., 方程3个解为即为,2) 利用欧拉定理 若(a,m)=1,则有 axb(mod m),两边同乘 ，则有 即 因为 所以,例: 解同余式解：因为(8,11)
4、=1,所以由欧拉定理 有,(3)用形式分数定义1：当（a，m）=1时，若ab 1(modm)，则记b (modm)称为形式分数。根据定义和记号， 有性质1、2、（d，m）=1，且 ，则利用形式分数的性质把分母变成1，从而求出一次同余式的解。,例：解一次同余方程解：（17，25）=1，原同余方程有解，利用形式分数的性质，同余方程解为,3 一次同余方程组的解法定义:如下(*)称为一次同余方程组 xb1(mod m1) xb2(mod m2) （*） xbk(mod mk)有解判定定理：同余方程组（*）有解的充要条件是,下面给出k=2时的证明.,证: 若 (1)有解,则有 (2) 即反之由(1)得
5、代入(2)有 因为由一次同余方程有解条件知t有解,即同余方程组有解.,下面给出一个例子，并用代入法求解例：解一次同余式组解：因为(4,6)=2|3-1,所以有解,由(1)式得x=3+4t代入(2)得 即 得 代入x=3+4t 得 即 为一次同余式组的解。,下面我们给出模两两互素的情形，此时显然满足有解的条件，即孙子定理：设 两两互素， 则同余式(*)组的解为其中,证明：因为 两两互素，所以有 中的 存在，又对任意的 有 有所以 即是(*)的解若 是满足 (*)的两个整数，则有又 ,所以有 ,即 ,说明是惟一解。,例：解一次同余式组解 :因为7，8,9两两互素，可以利用孙子定理. m=504,进
6、而有所以有是原一次同余式组的解。,注：若给出的同余方程组不是标准形式，必须注意化为标准形式，同时我们得到的有解的判别定理及求解方法都是在这一标准形式得到的。同余方程组（1）有解的条件(mi ,mj) bi-bj ，1i，jk 。在使用时一定要对所有的组合进行验算，进行有解的判别,求解一次同余方程组（*）有两种方法： 待定系数法和孙子定理,二种方法各有特长。待定系数法适应的范围较广，对模没有什么要求。孙子定理有一个具体的公式，形式也较漂亮。但对模要求是两两互素。 次数大于1的同余方程称为高次同余方程，一般地高次同等方程可转化一系列的高次同余方程组。然后将每一个高次同余方程的解都求出，最后利用孙子
7、定理可求出原高次同余方程的解。,4 高次同余方程定义1、次数大于1的同余方程称为高次同余方程对一般模的高次同余方程我们要通过“小模”和“降次”的方法来得到一般模的高次同余方程的解。,1、小模：即把一般模高次同等方程转化为一系列模两两互素的高次同余方程组，即有定理：设 ， 两两互素， 则 （1） 等价于下面方程组 （2）设 和 的解数为 则有下面来看证明.,证明：若 是（1）的解，即 则 从而有 ，即 即（1）的解就是（2）的解， 反之若 是（2）的解，则有 即 从而有 由于 两两互素，所以 ， 从而 有 即 即（2）的解也是（1）的解。,又由于（2）中第i个方程有 个解，则（2）一共可组合成 个一次同余式组，由孙子定理每一个同余式组有惟一解，所以有 个解，又由于（1）（2）的等价性，所以有,例：同余方程解：原同余方程等价于同余方程组 即有所以有4解，由孙子定理为,由于 所以等价于同余方程组从而从理论上说只要能解 即可，而由性质可知若x是 的解，则一定是 的解所以只要在 的解中 找 的解。所以理论上只要解素数模 同余方程即可。,对素数模同余方程，可以降次，看下面的定理：设p是素数， 是整系数多项式，设 是 的一个解，则有（1） 则存在整数t使得 是 的解。（2） 且 ， 则 当t=0，1，2P-1时， 都是 的解。,
