初等数论基础:同余方程的基本概念及求解

本节介绍同余方程的一些基本概念.

定义5.1.1　设f（x）=anxn+an-1xn-1+…+a1x+a0是整系数多项式.称f（x）≡0（modm）是关于未知数x的模m的同余方程，简称为模m的同余方程.若an≢0（modm），则称f（x）≡0（modm）的次数是n.显然，若f（x）≡0（modm）的次数为n，则f（x）的次数为n.但反之未必.例如，f（x）=3x3+2x2+1的次数为3，但f（x）≡0（mod3）的次数是2.

定义5.1.2　设f（x）≡0（modm）是模m的同余方程.若整数a满足f（a）≡0（modm），则集合｛s∈Z|s≡a（modm）｝中任何元素均满足同余方程f（x）≡0（modm）.此时，把a所在的模m的剩余类

｛s∈Z|s≡a（modm）｝

称为同余方程f（x）≡0（modm）的一个解，记为x≡a（modm）.根据这一约定，模m的同余方程最多有m个解.另外，若a1，a2，…，am是模m的完全剩余系且(www.xing528.com)

则f（x）≡0（modm）有t个解x≡aij（modm），j=1，2，…，t.

例5.1.3　求同余方程x5+x+1≡0（mod7）的解.

解　将模7的完全剩余系-3，-2，-1，0，1，2，3依次带入方程检验可知只有2和-3满足同余方程，故该同余方程的解为x≡2（mod7）和x≡-3（mod7）.解毕.

注5.1.4　当模很大时，利用例5.1.3的方法求解是很烦琐的，但这种方法仍然是解同余方程的唯一普遍方法.