初 等 数 论 辅导课程七 主讲教师：曹洪平
第四章 同 余 式 1. 同余式的概念与一次同余式的解法 2. 孙子定理 3. 高次同余式的解数与解法 4. 质数模的同余式
同余式的概念与一次同余式 掌握同余式的概念及同余式的解的定义 掌握一次同余式的一般形式 掌握一次同余式有解的判定 重点掌握一次同余式的解法
同余式的定义 设f(x)=anxn+an-1xn-1+…+a0, 其中ai是整 数, m为一个正整数, 则 f(x)0(mod m) (1) 叫做模m的同余式. 若an≢ 0(mod m), 则n 叫做(1)的次数.
注 若整数a满足f(a)0(mod m), 则当 整数b满足ba(mod m)时, b也满足 f(b)0(mod m), 因此a所在的剩余类中 的每个数都满足(1). 定义 若整数a满足同余式(1), 则称xa(mod m)为(1)的一个解.
例 对同余式x2+x+10(mod 7), 整数2满 足该同余式, 于是x2(mod 7)是它的一个 解. 又整数4也满足该同余式, 于是x4(mod 7)也是它的一个解.
一次同余式 一次同余式的一般形式 形如 axb(mod m), a≢0(mod m) (2) 的同余式叫一次同余式. 例如 3x4(mod 7)与21x3(mod 9) 都是一次同余式.
一次同余式有解的判定 定理 一次同余式(2)有解的充要条件 是(a, m)|b. 并且在(2)有解时, (2)的解数 是d=(a, m).
证明 (2)有解的充要条件是ax-my=b有解, 由不定方程有解的充要条件知, (2)有解的充要条件是(a, m)|b. 设d=(a, m), 由不定方程的通解公式知, 适合不定方程ax-my=b的一切整数x可写成x=m1t+x0, m1=m/d, t取一切整数, 此式对模m来说可以写成d个同余式, 即: xx0+km1(mod m), k=0, 1, …, d-1. 这是同余式(2)的d个不同的解.
解法 要解同余式(2), 我们先解不定方程 ax-my=b, 求出x的一切整数值的表达式, 再写成模m的 d个同余式即可.
例 解同余式3x6(mod 12). 解 因为(3, 12)=3, 而3|6, 所以同余式 有解, 且有3个解. 由3x-12y=6得: x=2+4t, y=t, t取一切整数. 所以同余式的3个解为: x2, 6, 10(mod 12).
注 实际上对同余式(1), 我们可将数0, 1, 2,…,m-1依次代如(1)检查, 若数a满足(1), 则xa(mod m)为(1)的一个解, 在数0, 1, 2,…,m-1中有几个数满足(1), 则(1)就有 几个解, 并且这样求出的是(1)的全部的解.
例 解同余式3x≡2(mod 5). 解 将0, 1, 2, 3, 4代入检验, 当x取4时有 3×4≡2(mod 5), 当x取0, 1, 2, 3时都不 满足要求, 所以同余式有一个解, 即 x≡4(mod 5).
孙子定理 掌握孙子定理的内容 会用孙子定理解一次同余式组
讨论同余式组: xb1(mod m1), xb2(mod m2), ………… (1) xbk(mod mk). 其中m1, m2, … , mk是两两互素的正整数.
孙子定理 令m=m1m2…mk, m=miMi, i=1, 2,…,k, 则同余式组(1)的解是 其中
例 解同余式组 x1(mod 2), x2(mod 5), x3(mod 7), x4(mod 9).
解 m1=2, m2=5, m3=7, m4=9, m=630, M1=315, M2=126, M3=90, M4=70. 由 , 得 . 同理可得: . 所以其解为: x157(mod 630).
注 孙子定理只适用于m1, m2, … , mk是两两互素的正整数的情况 注 孙子定理只适用于m1, m2, … , mk是两两互素的正整数的情况. 当m1, m2, … , mk不是两两互素的情况时, 可用下例的方法做, 且这一方法也适用于可用孙子定理的情况. 例 解同余式组 x7(mod 12), x3(mod 8).
解 满足第一个同余式的一切x可表为: x=7+12y, y取一切整数. 将x的这一表达式代入第二个同余式, 得: 7+12y3(mod 8). 解此同余式得y1(mod 2), 即y=2z+1, z 取一切整数, 所以满足原同余式组的一切 整数x为: x=19+24z, 解为x19(mod 24).