初等数论同余式

《初等数论同余式》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、或除去一个数k，为了保持其同解性，必须（k,m）=1，这一点和同余的性质有区别。例等价于等价于即，同余方程和不定方程一样，我们同样要考虑以下三个问题，即有解的条件，解数及如何求解，一般地说，对于一般的同余方程，由于仅有有限个解，只要把模m的一个完全剩余系一一代入即可，满足同余方程的就是解。但当模较大或次数较高时应寻求简洁而实用的解法.这一章主要讨论1、一次同余方程ax≡b(modm)２、一次同余方程组x≡b1(modm1)x≡b2(modm2)…x≡bk(modmk)３的求解。§2一次同余方程一次同余

3、方程的一般形式为ax≡b(modm)，有2.1定理：a,b为整数，，则ax≡b(modm)有解的充要条件是(a,m)

4、b,若有解则有d=(a,m)个关于模m的解证明：由同余的定义知ax≡b(modm)等价于不定方程ax=b-my，而此不定方程有解的充要条件是(a,m)

5、b。在有解的情况下，设不定方程的解为此时同余方程有d个解，为因当　时，2.2一次同余方程ax≡b(modm)的解法。（1）化为不定方程ax+my=b例：解同余式解因为(45,132)=3¦21,所以同余式有3个解.化简为等价的同余方程我

6、们再解不定方程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，原同余方程有解，利用形式分数的性质，同余方程

7、解为§3一次同余方程组的解法定义:如下(*)称为一次同余方程组x≡b1(modm1)x≡b2(modm2)……（*）x≡bk(modmk)有解判定定理：同余方程组（*）有解的充要条件是下面给出k=2时的证明.证:若(1)有解,则有(2)即反之由(1)得代入(2)有因为由一次同余方程有解条件知t有解,即同余方程组有解.下面给出一个例子，并用代入法求解例：解一次同余式组解：因为(4,6)=2

8、3-1,所以有解,由(1)式得x=3+4t代入(2)得即得代入x=3+4t得即为一次同余式组的解。下面我们给出模两

9、两互素的情形，此时显然满足有解的条件，即孙子定理：设两两互素，则同余式(*)组的解为其中证明：因为两两互素，所以有中的存在，又对任意的有有所以即是(*)的解若是满足(*)的两个整数，则有又,所以有,即,说明是惟一解。例：解一次同余式组解:因为7，8,9两两互素，可以利用孙子定理.m=504,进而有所以有是原一次同余式组的解。注：若给出的同余方程组不是标准形式，必须注意化为标准形式，同时我们得到的有解的判别定理及求解方法都是在这一标准形式得到的。同余方程组（1）有解的条件(mi,mj)∣bi-bj，1≤

10、i，j≤k。在使用时一定要对所有的组合进行验算，进行有解的判别求解一次同余方程组（*）有两种方法：待定系数法和孙子定理,二种方法各有特长。待定系数法适应的范围较广，对模没有什么要求。孙子定理有一个具体的公式，形式也较漂亮。但对模要求是两两互素。次数大于1的同余方程称为高次同余方程，一般地高次同等方程可转化一系列的高次同余方程组。然后将每一个高次同余方程的解都求出，最后利用孙子定理可求出原高次同余方程的解。§4高次同余方程定义1、次数大于1的同余方程称为高次同余方程对一般模的高次同余方程我们要通过“小模

11、”和“降次”的方法来得到一般模的高次同余方程的解。1、小模：即把一般模高次同等方程转化为一系列模两两互素的高次同余方程组，即有定理：设，两两互素，则（1）等价于下面方程组（2）设和的解数为则有下面来看证明.证明：若是（1）的解，即则从而有，即即（1）的解就是（2）的解，反之若是（2）的解，则有即从而有由于两两互素，所以，从而有即即（2）的解也是（1）的解。又由于（2）中第i个方程有个解，则（2）一共可组合成个一次同余式组，由孙子定理每一个同余式组有惟一解