二十SECTION同余式.docVIP

§3 同余式 [同余及其性质] 设m为自然数,若整数a与b之差a-b为m的倍数,则称a与b对模m同余,记做 (mod m) 否则记为 (mod m) 表示a与b对模m不同余. 同余具有下列性质: 1( (mod m) (自反性) 2( 若(mod m),则(mod m) (对称性) 3( 若,(mod m),则(mod m) (传递性) 4( 若,(mod m),则 (mod m) (mod m) (mod m) 5( 若,(mod m),且,则(mod m). [完全剩余系与缩剩余系] 设以m为模,则由同余性质1(,2(,3(可将全体整数分为m个类,同类的数都同余,不同类的数不同余,称这样的类为同余类,每类中各取一数为代表,例如 构成一个完全剩余系. 在与m互素的各类中取一代表 构成一缩剩余系(简称缩系),此处((m)为不超过m且与m互素的数的个数(称为欧拉函数). 剩余系具有下列性质: 1( 若, x过m的一完全剩余系,过的一完全剩余系,则过的一完全剩余系. 2( 若, x过m的一缩系, 过的一缩系,则过的一缩系. 3( 若为模m的一缩系,且(k,m)=1,则 也为m的一缩系 [欧拉定理] 若(k,m)=1,则 (mod m) 式中((m)为欧拉函数. [费马定理] 若p为素数,则对所有整数(,有 (mod p) 显然费马定理是欧拉定理的特例. [一次同余方程可解条件] 同余方程 (modm) 有解的充分必要条件是: 当满足此条件时,其解数(对模m的不同余者)为 [一元一次同余方程的解法] 一元一次同余方程 (mod m) (1) 有解的充分必要条件是:,若有解则共有(a,m)个互不同余的解,modm.解法如下: 设(a,m)=d,,则原方程(1)化为 记作 (2) 首先由辗转相除法确定(见§1),使得 则 是同余方程(2)的解,最后得到 x=x’+m’t , t= 为原方程(1)的解,mod m.即有d个解 对模m不同余. [孙子定理*] 若，i≠j，则同余方程组 (3) 有唯一解, . 同余方程组(3)的解法如下: 因为,所以可由辗转相除法求出,满足 记 于是 最后计算 它就是同余方程组(3)的唯一解,. [二次剩余与二次非剩余] 设m为大于1的整数,(n,m)=1,若 (mod m) 可解,则称n为对模m的二次剩余,或二次剩余,mod m.否则,称n为对模m的二次非剩余. 两个二次剩余之积仍为二次剩余,mod p. 两个二次非剩余之积为二次剩余,mod p. 一个二次剩余与一个二次非剩余之积为一个二次非剩余,mod p. 设p为奇素数,则在模p的缩剩余系中,有个二次剩余: 有个二次非剩余, mod p. [勒让德符号及其性质] 设p为奇素数,pn又设 则称为勒让德符号. 勒让德符号具有下列性质: 1( 若(mod p), pn则 = 2( 欧拉判别条件: 设p为奇素数,则 (mod p) 3( 若p为奇素数, pmn ,则 4( 若p为奇素数,则 5( 若p为奇素数,则 6( 高斯互逆定律: 设p,q为两个不同的奇素数,则 [二次同余式的解数] 设l0, pn,若p为奇素数，则二次同余式 (mod ) 的解数为. 当p=2时,l=1时 有一解. [对模m的次数] 设h为一整数,(m,h)=1,满足 (mod m) 的最小正整数l称为h对模m的次数,或h的次数,mod m. 若(mod m),则,这里l为h的次数,mod m [素数模的原根与指数] 设p为素数,次数为p－1的数称为模p的原根. 设g