初等数论同余式.ppt

第四章 同余式 1 同余方程的基本概念 定义：设 , 则 叫做模m的同余方程 若 ,则称n为同余方程的次数。 若 ， 则 称为同余式的解 模m的一个完全剩余系中满足同余方程的个数称为满足同余方程的解数。,注：对模m互相同余的解是同一个解。 例：同余式 次数为2， 是解， 也是解，因为 所以为同一解，解数是1，,为了求方程的解经常有等价变形的问题， 对于同余方程同样也有等价变形，即使原同余方程和新的同余方程互相等价的若干变换。常用的变换有 （1）移项运算是传统的， （2）同余方程两边也可以加上模的若干倍。相当于同余方程两边加“零”。 （3）乘上一数k或除去一个数k，为了保持其同解性，必须（k ,m）=1，这一点和同余的性质有区别。,例 等价于 等价于 即 ，,同余方程和不定方程一样，我们同样要考虑以下三个问题， 即有解的条件，解数及如何求解， 一般地说，对于一般的同余方程，由于仅有有限个解，只要把模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,若有解则有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)=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)得 代入(2)有 因为 由一次同余方程有解条件知t有解,即同余方程组有解.,下面给出一个例子，并用代入法求解 例：解一次同余式组 解：因为(4,6)=2|3-1,所以有解,由(1)式得x=3+4t代入(2)得 即 得 代入x=3+4t 得 即 为一次同余式组的解。,下面我们给出模两两互素的情形，此时显然满足有解的条件，即 孙子定理：设 两两互素， 则同余式(*)组的解为 其中,证明：因为 两两互素， 所以有 中的 存在，又对任意的 有 有 所以 即是(*)的解 若 是满足 (*)的两个整数，则有 又 ,所以有 ,即 ,说明是惟一解。,例：解一次同余式组 解 :因为7，8,9两两互素，可以利用孙子定理. m=504, 进而有 所以有 是原一次同余式组的解。,注：若给出的同余方程组不是标准形式，必须注意化为标准形式，同时我们得到的有解的判别定理及求解方法都是在这一标准形式得到的。 同余方程组（1）有解的条件 (mi ,mj) bi-bj ，1i，jk 。 在使用时一定要对所有的组合进行验算，进行有解的判别,求解一次同余方程组（*）有两种方法： 待定系数法和孙子定理,二种方法各有特长。待定系数法适应的范围较广，对模没有什么要求。孙子定理有一个具体的公式，形式也较漂亮。但对模要求是两两互素。 次数大于1的同余方程称为高次同余方程，一般地高次同等方程可转化一系列的高次同余方程组。然后将每一个高次同余方程的解都求出，最后利用孙子定理可求出原高次同余方程的解。,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时， 都是 的解。,证明：由已知 是 的解，可设 代入 ，则有 两边同除 得 由 所以上式有惟一解， 代入x有 是 的解。 又若 且 ，则（*）对任意t都成立。即当t=0，1，2P-1时， 都是 的解。从而证明了定理。,例：解方程 解：因为 的解为 即x=2+3t，因为 由定理因为有 所以当t=0，1，2时，即 都是方程的解。,例：解方程 解：因为 等价于 其解为 因 令x=1+5t代入 有 即 即 即有 代入x=1+5t有,所以有 代入 有 两边同除25有 有 代入x有 即 是方程的解。 同理从 可得到另一解（作练习） 从上可知解 最后可归结为解 即可， 下面讨论 的解法。,5 素数模同余方程 （*）,定理：同余方程（*）或者有P个解，或者与一个次数不超过p-1次的素数模同余方程等价。 证：由多项式除法，存在q（x）和r（x）使得 由费马定理 因此若 的系数全为p的倍数，则同余方程（*）有p个解，若 的系数不都是p的倍数，则 的次数不超过p-1次，且对任意的x有是 ，即同余方程（*）等价 证毕。,定理2： 设同余方程（*）有k 个不同的解 , 则对于任意的x有 , 其中 是一个次数为n-k的整系数多项式，且它的 的系数为 注:这个定理同一般方程类似,有一个 ,则从 f(x)中就可分解出 下面来看证明.,证：由多项式除 ,因 有 ，即 , 令 有 由于 是有k 个不同的解，所以有 (i=2,3,k),由归纳假设有 代入得有 证毕。,由定理2我们可得到下面的推论 推论1： p是素数，对任意的x有 证：由欧拉定理 有解，且其解为1,2p-1 由定理2知即得。,推论2(威尔逊定理）： p是素数，则有 证：由推论1 令x=p代入则有， 反之若 ,则m是素数。（自己证明） 注：所以威尔逊定理可用来判定一个数是否为素数。,定理3：同余方程（*）的解数不超过它的次数。 证：假设同余方程（*）有n+1个解，设为 由定理2知，对前n个解有 对第n+1个解有 由于 ,所以有i使得 和已知矛盾，所以假设错误。即同余方程（*）的解数不超过它的次数。,定理4： 同余方程（*）有n个解的充要条件是存在q（x）和r（x），使得 r(x)的次数小于n. 证：必要性 由多项式除法，存在q（x）和 使得 若同余方程（*）有n个解，由费马定理有 ,i=1,2,