1基本概念及一次同余式
- 格式：doc
- 大小：391.00 KB
- 文档页数：7
下载文档原格式
合集下载
初等数论(严蔚敏版) 第四章同余式
故原方程组的解是
x 3 936 2 ( 1) 143 1 (1) 792 1730(mod10296).
x 1(mod 2) x 2(mod 5) (ii)依题意得 x 3(mod 7) x 4(mod 9)
x 1 315 2 126 3 6 90 4 4 70 3307 157(mod 63
4 x 5 mod15
44 x 20 mod15
15 x x 20 mod15
x0 10(mod15) 与 x0 5(mod 45) 也一样
所以原同余式的 3 个解是 x 10 15t （ｔ＝０、１、２） 即 x1 10(mod15) ， x2 25(mod15) ， x3 40(mod15)
《初等数论》习题解答（第三版）新乡学院
x 2(mod 3) 例、解同余方程组 x 3(mod 5) x 2(mod 7)
解： 3,5,7 互质，故原方程组对模 m 3 5 7 有唯一解
35M 1 1(mod 3) M 1 2(mod 3) 1(mod 5) 21M 2 1(mod 5) M 1M 1 1(mod 3) 即 M 2 1(mod 7) 15M 3 1(mod 7) M3
30 由 144x 2 125 mod 215 得 x 80 mod 215 5
原同余式的解是 x 80 215t mod1935 , t 0,18.
4 / 36
《初等数论》习题解答（第三版）新乡学院
x 4 y 29 0(mod143) 的解。 2、求联立同余式 2 x 9 y 84 0(mod143)
x 3 936 2 ( 1) 143 1 (1) 792 1730(mod10296).
x 1(mod 2) x 2(mod 5) (ii)依题意得 x 3(mod 7) x 4(mod 9)
x 1 315 2 126 3 6 90 4 4 70 3307 157(mod 63
4 x 5 mod15
44 x 20 mod15
15 x x 20 mod15
x0 10(mod15) 与 x0 5(mod 45) 也一样
所以原同余式的 3 个解是 x 10 15t （ｔ＝０、１、２） 即 x1 10(mod15) ， x2 25(mod15) ， x3 40(mod15)
《初等数论》习题解答（第三版）新乡学院
x 2(mod 3) 例、解同余方程组 x 3(mod 5) x 2(mod 7)
解： 3,5,7 互质，故原方程组对模 m 3 5 7 有唯一解
35M 1 1(mod 3) M 1 2(mod 3) 1(mod 5) 21M 2 1(mod 5) M 1M 1 1(mod 3) 即 M 2 1(mod 7) 15M 3 1(mod 7) M3
30 由 144x 2 125 mod 215 得 x 80 mod 215 5
原同余式的解是 x 80 215t mod1935 , t 0,18.
4 / 36
《初等数论》习题解答（第三版）新乡学院
x 4 y 29 0(mod143) 的解。 2、求联立同余式 2 x 9 y 84 0(mod143)
第三章2 同余的应用
下面证明(ii) 。
证明
(1) 将同余式 ax≡b (mod m) 转化 a1x≡b1 (mod m1)。 设a＝da1，b＝db1，m＝dm1。则一次同余式
ax≡b (mod m)为da1x≡db1 (mod dm1)。 根据定理2.1.10，有 a1x≡b1 (mod m1)。 (2) 同余式a1x≡b1 (mod m1) 有唯一解x≡r (mod m1)
＝{7k ＋ 2|k∈Z} ＝ {… , - 12, -5, 2, 9, 16, …}
的每个数，都是同余式 x5＋x＋1≡0 (mod 7) 的解。 所以x≡2 (mod 7) 是同余式的一个解。
例6 模 7 的 5 次同余式 x5＋x＋1≡0 (mod 7) 当 x＝4 时，有45＋4＋1＝1029＝7×147≡0 (mod 7) 所以， 4 也是同余式 x5＋x＋1≡0 (mod 7) 的解。 4 所在剩余类C4＝{c|c∈Z , c ≡ 4(mod 7)}
x≡r (mod m1)是一次同余式a1x≡b1 (mod m1)的解， 即a1r≡b1 (mod m1)。 因此m1|(a1r－b1)， 于是dm1|(da1r－db1)，也就是m|(ar－b)， 即，ar≡b (mod m)。 故一次同余式a1x≡b1 (mod m1)的解 也是一次同余式ax≡b (mod m)的解。
(ii) 当同余式 (2) 有解时，其解数为 d＝(a , m)。
(iii) 若x1是(2)的一个解，则它的全部解可表示为：
x
x1
t
m (a, m)
(mod
m)
,t
0,1,
,(a, m) 1
命题1 设 m 是一个正整数，a 是满足 (a, m)＝1的整 数则一次同余式 ax≡b (mod m) 有解，且其解数为1。
证明
(1) 将同余式 ax≡b (mod m) 转化 a1x≡b1 (mod m1)。 设a＝da1，b＝db1，m＝dm1。则一次同余式
ax≡b (mod m)为da1x≡db1 (mod dm1)。 根据定理2.1.10，有 a1x≡b1 (mod m1)。 (2) 同余式a1x≡b1 (mod m1) 有唯一解x≡r (mod m1)
＝{7k ＋ 2|k∈Z} ＝ {… , - 12, -5, 2, 9, 16, …}
的每个数，都是同余式 x5＋x＋1≡0 (mod 7) 的解。 所以x≡2 (mod 7) 是同余式的一个解。
例6 模 7 的 5 次同余式 x5＋x＋1≡0 (mod 7) 当 x＝4 时，有45＋4＋1＝1029＝7×147≡0 (mod 7) 所以， 4 也是同余式 x5＋x＋1≡0 (mod 7) 的解。 4 所在剩余类C4＝{c|c∈Z , c ≡ 4(mod 7)}
x≡r (mod m1)是一次同余式a1x≡b1 (mod m1)的解， 即a1r≡b1 (mod m1)。 因此m1|(a1r－b1)， 于是dm1|(da1r－db1)，也就是m|(ar－b)， 即，ar≡b (mod m)。 故一次同余式a1x≡b1 (mod m1)的解 也是一次同余式ax≡b (mod m)的解。
(ii) 当同余式 (2) 有解时，其解数为 d＝(a , m)。
(iii) 若x1是(2)的一个解，则它的全部解可表示为：
x
x1
t
m (a, m)
(mod
m)
,t
0,1,
,(a, m) 1
命题1 设 m 是一个正整数，a 是满足 (a, m)＝1的整 数则一次同余式 ax≡b (mod m) 有解，且其解数为1。
同余式
例 8 利用同余理论为 N 支球队安排一个单循环比赛表。 解 当 N 为奇数时，总有一队要轮空，可以采用如下办法来 克服这种困难：加入一支假想的队 N 0 ，然后安排这个队在内 的 N 1支队的单循环比赛程序表， 在每轮比赛中， 安排和 N 0 比赛的球队轮空即可。所以下面的处理均假定 N 为偶数，给 每支队一个编号分别为 1, 2, , N ，每支队的比赛总场数为
2
解数为 0。
例 4 求同余式 15 x 15 x 30 0(mod 15) 的解。
2
解
取 模 15
的 绝 对 值 最 小 完 全 剩 余 系 ：
7,6, ,1,0,1, ,6,7 ，直接计算可知所有整数都是同余
式的 15 x 15 x 30 0(mod 15) 解，所以该同余式的解为
N 1，即有 N 1轮比赛，共有 N ( N 1) / 2 场比赛。
设 x 属于集合 {1, 2, , N 1}，在第 k 轮中，以 xk 表示与 x 进 行比赛的编号，同样有 xk 属于集合 {1, 2, , N 1}。 我们使用 同余式
x x k (mod N 1)
a
称所有这些整数为同余式（1）的一个解，记为
x a (mod m)
所有对模 m 两两不同余的解的个数称为是同余式（1 ）的解 数，记为 T ( f , m) 。从定义可以看出来，同余式（1）的解数 一定不超过 m ，即 T ( f , m ) m 。
例 1 求同余式 4 x 12 x 7 0(mod 15) 的解。
2
x 5, 2,5(mod 15)
解数为 3。
例 3 求同余式 4 x 12 x 3 0(mod 15) 的解。
1 基本概念及一次同余式
1 基本概念及一次同余式定义 设()110n n n n f x a x a x a --=+++，其中()0,0,1,,i n a i n >=是整数，又设0m >，则()()0mod f x m ≡ （1）叫做模m 的同余式。
若()0mod n a m ≡，则n 叫做同余式（1）的次数。
如果0x 满足()()00mod ,f x m ≡则()0mod x x m ≡叫做同余式（1）的解。
不同余的解指互不同余的解。
当m 及n 都比较小时，可以用验算法求解同余式。
如例1 同余式()543222230mod7x x x x x +++-+≡仅有解()1,5,6mod7.x ≡例2 同余式()410mod16x -≡有8个解()1,3,5,7,9,11,13,15mod16x ≡例3 同余式()230mod5x +≡无解。
定理 一次同余式()()0mod ,0mod ax m a m ≡≡ （2）有解的充要条件是(),.a m b若（2）有解，则它的解数为(),d a m =。
以及当同余式（2）有解时，若0x 是满足（2）的一个整数，则它的(),d a m =个解是()0mod ,0,1,,1m x x k m k d d ≡+=- （4）证 易知同余式（2）有解的充要条件是不定方程ax my b =+ （5）有解。
而不定方程（5）有解的充要条件为()(),,.a m a m b =-当同余式（2）有解时，若0x 是满足（2）的一个整数，则()0mod ,0,1,, 1.m a x k b m k d d ⎛⎫+≡=- ⎪⎝⎭ 下证0,0,1,,1m x k k d d+=-对模m 两两部同余。
设 ()00mod ,01,1m m x k x k m k d k d d d''+≡+≤≤-≤≤- 则()mod ,mod ,.m m m k k d k k d k k d d d ⎛⎫'''≡≡= ⎪⎝⎭ 再证满足（2）的任意一个整数1x 都会与某一个()001m x k k d d+≤≤-对模m 同余。
zsl第三章第1节1
第三章
同余式
1
3.1 基本概念及一次同余式
定义1 设m是一个正整数, f ( x )为多项式 f ( x ) a n x n a n 1 x n 1 其中ai 是整数,则 f ( x ) 0 (mod m ) (1) 叫做模m的同余式.若an 0 (mod m ), 则n叫做f ( x ) 的次数, 记为 deg f , (1)式又叫做模m的n次同余式.
例1 x 5 x 1 0 (mod 7) 是首项系数为1的 模7同余式. 因
2 2 1 0 (mod 7),
5
所以 x 2 (mod 7) 是该同余式的解.
另外在模7的完全剩余系中, x 4 (mod 7)也是 解,故同余式解数是2.
3
定理1 一次同余式 ax b (mod m ), a (2) 0 (mod m ) 有解 (a , m ) | b. 且当同余式(2)有解时,其解数为 d (a , m ).
4
首先求出同余式 a m x 1 (mod ) (a , m ) (a , m ) m 的一个解 x x0 (mod ); (a , m ) 其次, 写出同余式ax b (mod m)的一个特解 x0 b x (mod m ) (a , m ) 最后, 写出同余式ax b (mod m)的全部解
x0 b m x t (mod m ), t 0,1, (a , m ) (a , m ) ,(a, m ) 1
5
例2 求解一次同余式 57 x 531 (mod123)
例3 求解一次同余式 37 x 3819 (mod 10)
6
定理2 设m是一个正整数,(a , m ) 1, 则一次同 余式 ax 1 (mod m ) 有唯一解 x a ' (mod m ).
同余式
1
3.1 基本概念及一次同余式
定义1 设m是一个正整数, f ( x )为多项式 f ( x ) a n x n a n 1 x n 1 其中ai 是整数,则 f ( x ) 0 (mod m ) (1) 叫做模m的同余式.若an 0 (mod m ), 则n叫做f ( x ) 的次数, 记为 deg f , (1)式又叫做模m的n次同余式.
例1 x 5 x 1 0 (mod 7) 是首项系数为1的 模7同余式. 因
2 2 1 0 (mod 7),
5
所以 x 2 (mod 7) 是该同余式的解.
另外在模7的完全剩余系中, x 4 (mod 7)也是 解,故同余式解数是2.
3
定理1 一次同余式 ax b (mod m ), a (2) 0 (mod m ) 有解 (a , m ) | b. 且当同余式(2)有解时,其解数为 d (a , m ).
4
首先求出同余式 a m x 1 (mod ) (a , m ) (a , m ) m 的一个解 x x0 (mod ); (a , m ) 其次, 写出同余式ax b (mod m)的一个特解 x0 b x (mod m ) (a , m ) 最后, 写出同余式ax b (mod m)的全部解
x0 b m x t (mod m ), t 0,1, (a , m ) (a , m ) ,(a, m ) 1
5
例2 求解一次同余式 57 x 531 (mod123)
例3 求解一次同余式 37 x 3819 (mod 10)
6
定理2 设m是一个正整数,(a , m ) 1, 则一次同 余式 ax 1 (mod m ) 有唯一解 x a ' (mod m ).
同余的基本概念和性质
4 16，28 256，216 154，232 1 (mod 641)。
例3 说明 是否被641整除。
因此 0 (mod 641)，
即641 。
第一节 同余的基本性质
第一节 同余的基本性质
设式(4)对于n = k成立，则有 1 (mod 2k + 2) = 1 q2k + 2， 其中qZ，所以
=(1 q2k + 2)2=1 q 2k + 31(mod 2k + 3)， 其中q 是某个整数。这说明式(4)当n = k 1也成立。 由归纳法知式(4)对所有正整数n成立。
第一节 同余的基本性质
a2 1 (mod p) pa2 1 = (a 1)(a 1)，
证明 由
pa 1或pa 1，
所以必是
a 1或a 1 (mod p)。
例8 设p是素数，a是整数，则由a2 1(mod p)可以推出
即a 1 (mod p)或a 1 (mod p)。
解 因为792 = 8911，故 792n 8n，9n及11n。 我们有 8n 8 z = 6，
证明 留作习题。
定理5 下面的结论成立： (ⅰ) a b (mod m), dm, d>0 a b (mod d); (ⅱ) a b (mod m), k > 0, kN ak bk (mod mk)； (ⅲ) a b (mod mi )，1 i k a b (mod [m1, m2, , mk])； (ⅳ) a b (mod m) (a, m) = (b, m)； (ⅴ) ac bc(modm), (c, m) =1 a b (mod m).
定义1 给定正整数m，如果整数a与b之差被m整除，则称a与b对于模m同余，或称a与b同余，模m，记为 a b (mod m)， 此时也称b是a对模m的同余
例3 说明 是否被641整除。
因此 0 (mod 641)，
即641 。
第一节 同余的基本性质
第一节 同余的基本性质
设式(4)对于n = k成立，则有 1 (mod 2k + 2) = 1 q2k + 2， 其中qZ，所以
=(1 q2k + 2)2=1 q 2k + 31(mod 2k + 3)， 其中q 是某个整数。这说明式(4)当n = k 1也成立。 由归纳法知式(4)对所有正整数n成立。
第一节 同余的基本性质
a2 1 (mod p) pa2 1 = (a 1)(a 1)，
证明 由
pa 1或pa 1，
所以必是
a 1或a 1 (mod p)。
例8 设p是素数，a是整数，则由a2 1(mod p)可以推出
即a 1 (mod p)或a 1 (mod p)。
解 因为792 = 8911，故 792n 8n，9n及11n。 我们有 8n 8 z = 6，
证明 留作习题。
定理5 下面的结论成立： (ⅰ) a b (mod m), dm, d>0 a b (mod d); (ⅱ) a b (mod m), k > 0, kN ak bk (mod mk)； (ⅲ) a b (mod mi )，1 i k a b (mod [m1, m2, , mk])； (ⅳ) a b (mod m) (a, m) = (b, m)； (ⅴ) ac bc(modm), (c, m) =1 a b (mod m).
定义1 给定正整数m，如果整数a与b之差被m整除，则称a与b对于模m同余，或称a与b同余，模m，记为 a b (mod m)， 此时也称b是a对模m的同余
第四章 同余式 (2)
“小模”和“降次”的方法来得到一般 模的高次同余方程的解。
1、小模：即把一般模高次同等方程转化为 一系列模两两互素的高次同余方程组，即有
m 定理：设m m1m2 mk ， 1, m2 ,mk 两两互素， f ( x) 0(mod m) 等价于下面方程组 则 （1）
例：同余方程 x3 x2 x 1 0(mod15)
解：原同余方程等价于同余方程组
x3 x2 x 1 0(mod3)
x3 x2 x 1 0(mod5)
即有
x 1,2(mod 3) x 1,4(mod 5)
所以有4解，由孙子定理为
x 1,4,11,14(mod15)
9 9 4
6 2） 30 8(mod11 （ )
4
(3)用形式分数
定义1：当（a，m）=1时，若ab 1(modm)， 则记b 1 (modm)称为形式分数。 a
c 1 (mod m) 根据定义和记号， 有性质 a
c a
1、
c c mt1 (mod m), t1 , t2 Z a a mt 2
（1）移项运算是传统的，
（2）同余方程两边也可以加上模的若干倍。 相当于同余方程两边加“零”。 （3）乘上一数k或除去一个数k，为了保持其 同解性，必须（k ,m）=1，这一点和同余的性 质有区别。
例
15x2 17x 5(mod12) 等价于 3x2 5x 5(mod12)
12 7
x 2x 6x 8 0(mod5)
x0 m1t2 mk x0 m1t2 mod m) （
2.2 一次同余方程ax≡b(mod m)的解法。
（1）化为不定方程ax+my=b
1、小模：即把一般模高次同等方程转化为 一系列模两两互素的高次同余方程组，即有
m 定理：设m m1m2 mk ， 1, m2 ,mk 两两互素， f ( x) 0(mod m) 等价于下面方程组 则 （1）
例：同余方程 x3 x2 x 1 0(mod15)
解：原同余方程等价于同余方程组
x3 x2 x 1 0(mod3)
x3 x2 x 1 0(mod5)
即有
x 1,2(mod 3) x 1,4(mod 5)
所以有4解，由孙子定理为
x 1,4,11,14(mod15)
9 9 4
6 2） 30 8(mod11 （ )
4
(3)用形式分数
定义1：当（a，m）=1时，若ab 1(modm)， 则记b 1 (modm)称为形式分数。 a
c 1 (mod m) 根据定义和记号， 有性质 a
c a
1、
c c mt1 (mod m), t1 , t2 Z a a mt 2
（1）移项运算是传统的，
（2）同余方程两边也可以加上模的若干倍。 相当于同余方程两边加“零”。 （3）乘上一数k或除去一个数k，为了保持其 同解性，必须（k ,m）=1，这一点和同余的性 质有区别。
例
15x2 17x 5(mod12) 等价于 3x2 5x 5(mod12)
12 7
x 2x 6x 8 0(mod5)
x0 m1t2 mk x0 m1t2 mod m) （
2.2 一次同余方程ax≡b(mod m)的解法。
（1）化为不定方程ax+my=b
[自然科学]同余式
7 同余式.而 x≡2(mod 7) 是该同余式的解.事实 上，我们有
25 + 2 +1=35=5·7≡0( mod 7) 还有解 x≡4(mod 7) , 解数为 2.
12.12.2020
h
4
同余式的基本定理
定理1 若(a , m) = 1,则 ax ≡ b (mod m) 有一解.
证明：因(a , m ) = 1 , 故 0 ,a ,2a , … , (m - 1)a
为m的完全剩余系.故其中有且只有一个r使 ar ≡ b (mod )
故得：x ≡ r (mod m ) 是同余式的唯一解.
12.12.2020
h
5
同余式的基本定理
定理2 若(a , m) = d > 1, d b ,则 ax ≡ b (mod m) 没有解. 证明 若有解 ，则可得: ax ≡ b (mod m) 而d | m, 故由2.1 定理11得到 ax ≡ b (mod d) 从而有 d | b,这与d b 矛盾，所以原同余式无解.
1 (m,a) 事实上，如果同时有同余式
12.12.2020
h
14
同余式的基本定理
ax≡ b(mod m)和 ax1 ≡ b(mod m) 成立， 两式相减得到 a(x- x1 )≡ 0 (mod m) 根据 2.1 定理 10 和定理 8，这等价于
x ≡ x1 (mod m) 因此， 同余式(2)的全部解可写成(7)式，证毕.
第三章 同余式
▪ 同余式的基本概念 ▪ 一次同余式相关定理 ▪ 一次同余式的解法
12.12.2020
h
1
同余式的基本概念
定义 1 设 m 是一个正整数，设 f(x)为多项式
25 + 2 +1=35=5·7≡0( mod 7) 还有解 x≡4(mod 7) , 解数为 2.
12.12.2020
h
4
同余式的基本定理
定理1 若(a , m) = 1,则 ax ≡ b (mod m) 有一解.
证明：因(a , m ) = 1 , 故 0 ,a ,2a , … , (m - 1)a
为m的完全剩余系.故其中有且只有一个r使 ar ≡ b (mod )
故得：x ≡ r (mod m ) 是同余式的唯一解.
12.12.2020
h
5
同余式的基本定理
定理2 若(a , m) = d > 1, d b ,则 ax ≡ b (mod m) 没有解. 证明 若有解 ，则可得: ax ≡ b (mod m) 而d | m, 故由2.1 定理11得到 ax ≡ b (mod d) 从而有 d | b,这与d b 矛盾，所以原同余式无解.
1 (m,a) 事实上，如果同时有同余式
12.12.2020
h
14
同余式的基本定理
ax≡ b(mod m)和 ax1 ≡ b(mod m) 成立， 两式相减得到 a(x- x1 )≡ 0 (mod m) 根据 2.1 定理 10 和定理 8，这等价于
x ≡ x1 (mod m) 因此， 同余式(2)的全部解可写成(7)式，证毕.
第三章 同余式
▪ 同余式的基本概念 ▪ 一次同余式相关定理 ▪ 一次同余式的解法
12.12.2020
h
1
同余式的基本概念
定义 1 设 m 是一个正整数，设 f(x)为多项式
《初等数论(闵嗣鹤、严士健-高等教育出版社)》习题解答完整版
第一章 整数的可除性§1 整除的概念·带余除法 1．证明定理3定理3 若12n a a a ，，，都是m 得倍数，12n q q q ，，，是任意n 个整数，则1122n n q a q a q a +++ 是m 得倍数．证明： 12,,n a a a 都是m 的倍数。
∴ 存在n 个整数12,,n p p p 使 1122,,,n n a p m a p m a p m ===又12,,,n q q q 是任意n 个整数1122n n q a q a q a ∴+++ 1122n n q p m q p m q p m =+++ 1122()n n p q q p q p m =+++即1122n n q a q a q a +++ 是m 的整数 2．证明 3|(1)(21)n n n ++ 证明 (1)(21)(1)(2n n n n n n n ++=+++-(1)(2)(1)(n n n n n n =+++-+又(1)(2)n n n ++ ，(1)(2)n n n -+是连续的三个整数 故3|(1)(2),3|(1)(1)n n n n n n ++-+3|(1)(2)(1)(1)n n n n n n ∴+++-+从而可知3|(1)(21)n n n ++3．若00ax by +是形如ax by +（x ，y 是任意整数，a ，b 是两不全为零的整数）的数中最小整数，则00()|()ax by ax by ++．证： ,a b 不全为0∴在整数集合{}|,S ax by x y Z =+∈中存在正整数，因而有形如ax by +的最小整数00ax by +,x y Z ∀∈，由带余除法有0000(),0ax by ax by q r r ax by +=++≤<+则00()()r x x q a y y q b S =-+-∈，由00ax by +是S 中的最小整数知0r =00|ax by ax by ∴++00|ax by ax by ++ （,x y 为任意整数） 0000|,|ax by a ax by b ∴++ 00|(,).ax by a b ∴+ 又有(,)|a b a ，(,)|a b b00(,)|a b ax by ∴+ 故00(,)ax by a b +=4．若a ，b 是任意二整数，且0b ≠，证明：存在两个整数s ，t 使得||,||2b a bs t t =+≤成立，并且当b 是奇数时，s ，t 是唯一存在的．当b 是偶数时结果如何？证：作序列33,,,,0,,,,2222b b b bb b --- 则a 必在此序列的某两项之间 即存在一个整数q ，使122q q b a b +≤<成立 ()i 当q 为偶数时，若0.b >则令,22q qs t a bs a b ==-=-，则有 02222b q q qa bs t ab a b b t ≤-==-=-<∴<若0b < 则令,22q qs t a bs a b =-=-=+，则同样有2b t < ()ii 当q 为奇数时，若0b >则令11,22q q s t a bs a b ++==-=-，则有若 0b <，则令11,22q q s t a bs a b ++=-=-=+，则同样有2b t ≤，综上所述，存在性得证．下证唯一性当b 为奇数时，设11a bs t bs t =+=+则11()t t b s s b -=-> 而111,22b bt t t t t t b ≤≤∴-≤+≤ 矛盾 故11,s s t t == 当b 为偶数时，,s t 不唯一，举例如下：此时2b为整数 11312(),,22222b b b b b b b t t ⋅=⋅+=⋅+-=≤§2 最大公因数与辗转相除法 1．证明推论4.1推论4.1 a ，b 的公因数与（a ，b ）的因数相同． 证：设d '是a ，b 的任一公因数，∴d '|a ，d '|b 由带余除法111222111111,,,,,0n n n n n n n n n n a bq r b r q r r r q r r r q r r r r b ---++-=+=+=+==≤<<<<∴(,)n a b r =∴d '|1a bq -1r =， d '|122b rq r -=，┄, d '|21(,)n n n n r r q r a b --=+=, 即d '是(,)a b 的因数。
初等数论第五章同余方程
第五章同余方程本章主要介绍同余方程的基础知识，并介绍几类特殊的同余方程的解法。
第一节同余方程的基本概念本节要介绍同余方程的基本概念及一次同余方程。
在本章中，总假定m是正整数。
定义1设f(x) = a n x n a1x a0是整系数多项式，称f(x) 0 (mod m) (1)是关于未知数x的模m的同余方程，简称为模m的同余方程。
若a n≡/0 (mod m)，则称为n次同余方程。
定义2设x0是整数，当x = x0时式(1)成立，则称x0是同余方程(1)的解。
凡对于模m同余的解，被视为同一个解。
同余方程(1)的解数是指它的关于模m互不同余的所有解的个数，也即在模m的一个完全剩余系中的解的个数。
由定义2，同余方程(1)的解数不超过m。
定理1下面的结论成立：(ⅰ) 设b(x)是整系数多项式，则同余方程(1)与f(x) b(x) b(x) (mod m)等价；(ⅱ) 设b是整数，(b, m) = 1，则同余方程(1)与bf(x) 0 (mod m)等价；(ⅲ) 设m是素数，f(x) = g(x)h(x)，g(x)与h(x)都是整系数多项式，又设x0是同余方程(1)的解，则x0必是同余方程g(x) 0 (mod m) 或h(x) 0 (mod m)的解。
证明 留做习题。
下面，我们来研究一次同余方程的解。
定理2 设a ，b 是整数，a ≡/0 (mod m )。
则同余方程ax b (mod m ) (2)有解的充要条件是(a , m )b 。
若有解，则恰有d = (a , m )个解。
证明 显然，同余方程(2)等价于不定方程ax my = b ， (3)因此，第一个结论可由第四章第一节定理1得出。
若同余方程(2)有解x 0，则存在y 0，使得x 0与y 0是方程(3)的解，此时，方程(3)的全部解是⎪⎪⎩⎪⎪⎨⎧-=+=t m a a y y t m a m x x ),(),(00，t Z 。
(4) 由式(4)所确定的x 都满足方程(2)。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
1 基本概念及一次同余式定义 设()110n n n n f x a x a x a --=+++，其中()0,0,1,,i n a i n >=是整数，又设0m >，则()()0mod f x m ≡ （1）叫做模m 的同余式。
若()0mod n a m ≡，则n 叫做同余式（1）的次数。
如果0x 满足()()00mod ,f x m ≡则()0mod x x m ≡叫做同余式（1）的解。
不同余的解指互不同余的解。
当m 及n 都比较小时，可以用验算法求解同余式。
如例1 同余式()543222230mod7x x x x x +++-+≡仅有解()1,5,6mod7.x ≡例2 同余式()410mod16x -≡有8个解()1,3,5,7,9,11,13,15mod16x ≡例3 同余式()230mod5x +≡无解。
定理 一次同余式()()0mod ,0mod ax m a m ≡≡ （2）有解的充要条件是(),.a m b若（2）有解，则它的解数为(),d a m =。
以及当同余式（2）有解时，若0x 是满足（2）的一个整数，则它的(),d a m =个解是()0mod ,0,1,,1m x x k m k d d ≡+=- （4）证 易知同余式（2）有解的充要条件是不定方程ax my b =+ （5）有解。
而不定方程（5）有解的充要条件为()(),,.a m a m b =-当同余式（2）有解时，若0x 是满足（2）的一个整数，则()0mod ,0,1,, 1.m a x k b m k d d ⎛⎫+≡=- ⎪⎝⎭ 下证0,0,1,,1m x k k d d+=-对模m 两两部同余。
设 ()00mod ,01,1m m x k x k m k d k d d d''+≡+≤≤-≤≤- 则()mod ,mod ,.m m m k k d k k d k k d d d ⎛⎫'''≡≡= ⎪⎝⎭ 再证满足（2）的任意一个整数1x 都会与某一个()001m x k k d d+≤≤-对模m 同余。
由 ()()01mod ,mod ax b m ax b m ≡≡得()101010mod ,mod ,.a a m m ax ax m x x x x d d d d ⎛⎫⎛⎫≡≡≡ ⎪ ⎪⎝⎭⎝⎭故存在整数t 使得10.m x x t d=+由带余除法，存在整数,q k 使得 ,0 1.t dq k k d =+≤≤-于是()()100mod .m m x x dq k x k m d d=++≡+ 故（2）有解时，它的解数为(),d a m =。
以及若0x 是满足（2）的一个整数，则它的(),a m 个解是()0mod ,0,1,,1m x x k m k d d ≡+=-例1求同余式 ()912mod15x ≡ （6）的解。
解 对如下的整数矩阵作初等列变换9150303301052522501313113--⎛⎫⎛⎫⎛⎫⎛⎫ ⎪ ⎪ ⎪ ⎪→--→--→- ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪-⎝⎭⎝⎭⎝⎭⎝⎭故()9,15 3.=又因312,故同余式（6）有解，且由三个解。
由以上初等变换还可知 ()()()()921513,924151412,9812mod15.⨯+⨯-=⨯⨯+⨯-⨯=⎡⎤⎣⎦⨯≡故同余式（6）的三个解为 ()158mod15,0,1,2.3x k k ≡+=即()3,8,13mod15.x ≡例2 求同余式()6483mod105x ≡ （7）的解。
解 对64,105作辗转相除法。
10564141,6441123,4123118,231815,18533,5312,3211,212,=⨯+=⨯+=⨯+=⨯+=⨯+=⨯+=⨯+=⨯故()64,1051,=同余式（7）有唯一解。
由以上过程还可知 ()()()()()()()()()()()()()()()132135311513251185321825718223181723718923741231941923164196441116=+⨯-=+-⨯⨯-=⨯-+⨯=⨯-+-⨯⨯=⨯+⨯-=⨯+-⨯⨯-=⨯-+⨯=⨯-+-⨯⨯=⨯+⨯-=⨯+-⨯⨯-()()()()64164125641610564125105256441=⨯-+⨯=⨯-+-⨯⨯=⨯+⨯-故()()()()1052564411,105258364418383,64340383mod105.⨯+⨯-=⨯⨯+⨯-⨯=⨯-≡故同余式（7）的解为()3403mod105x ≡-即()62mod105.x ≡习题1．求下列同余式的解：（ⅰ）256179(mod337).x ≡ （ⅱ） 1215560(mod 2755).x ≡（ⅲ）12961125(mod935).x ≡解（ⅰ）因256337256811381101141010131133131042510425104319791979⎛⎫⎛⎫⎛⎫ ⎪ ⎪ ⎪→-→-→ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪-⎝⎭⎝⎭⎝⎭⎛⎫⎛⎫⎛⎫ ⎪ ⎪ ⎪-→-→* ⎪ ⎪ ⎪ ⎪ ⎪ ⎪---*⎝⎭⎝⎭⎝⎭故()256,3371=，于是该同余式有解，且对模337有唯一解。
并且()()()()()256104337791,25610417933760179179,256104179179mod337,⨯+⨯-=⨯⨯+⨯-⨯=⎡⎤⎣⎦⨯⨯≡但是()1041791861681mod337,⨯=≡故()25681179337.⨯≡于是该同余式的唯一解为()81mod337.x ≡ （ⅱ）由辗转相除法，可得(1215,2755)5,5560,=故该同余式有解.由辗转相除法，还可得1215(195)275586 5.⋅-+⋅=在这个等式两边同时乘以112，得 1215(21840)27559632560.⋅-+⋅=故1215(21840)560(mod 2755).⋅-≡因21840200(mod 2755),-≡故1215200560(mod 2755).⋅≡故该同余式的全部解为2755200(mod 2755),0,1,,4.5x k k ≡+=即200,751,1302,1853,2404(mod 2755).x ≡2．求联立同余式()()4290mod143,29840mod143x y x y +-≡-+≡的解。
解 由同余式()4290mod143x y +-≡得()429mod143x y ≡-+代入同余式()29840mod143x y -+≡得()()()()24299840mod143,171420mod143,171mod143.y y y y -+-+≡-+≡≡-对17,143做辗转相除法。
因 1431787,17723,7321,313,=⨯+=⨯+=⨯+=⨯ 故()17,1431,=且()()()()()()()173271772217275172143178514351742.=+⨯-=+-⨯⨯-=⨯-+⨯=⨯-+-⨯⨯=⨯+⨯-故 ()()()()143517421,17421mod143,17421mod143.⨯+⨯-=⨯-≡⨯≡-故由()171mod143y ≡-可得()42mod143.y ≡由()42mod143y ≡及()4290mod143x y +-≡得()()442290mod143,4mod143.x x +⨯-≡≡于是可得，该联立同余式的解为()()4mod143,42mod143.x y ≡≡3.（ⅰ）设m 是正整数，(,)1a m =，证明()1(mod )m x ba m ϕ-≡是同余式(mod )ax b m ≡的解。
（ⅱ）设p 是质数，0a p <<，证明1(1)(1)(1)(mod )!a p p a xb p a ---+≡- 是同余式(mod )ax b p ≡的解。
证（ⅰ）因m 是正整数，(),1,a m =故同余式()mod ax b m ≡有唯一解。
由欧拉定理得 ()()()1mod .m m aba ba b m ϕϕ-=≡故()1m x ba ϕ-≡是同余式()mod ax b m ≡的解。
（ⅱ）因p 是质数，0a p <<，故(,)1a p =，同余式(mod )ax b p ≡有惟一解。
因 (1)!(1)(1)a p p a ---+,故 1(1)(1)(1)(1)!(mod(1)!).a p p a a a ----+≡--易知 11(1)(1)(1)(1)!(1)(1)((1))(1)!(mod ).a a p p a a a a p -----+--≡----=-而((1)!,)1a p -=，故1(1)(1)(1)(1)!(mod (1)!).a p p a a p a ----+≡--因此 1(1)(1)(1)1(mod ).(1)!a p p a p a ---+-≡-因!(1)(1),(!,)1a p p p a a p --+=，故!(1)(1).a p p a --+于是 11(1)(1)(1)(1)(1)(1)(mod ).!(1)!a a p p a p p a ab b b p a a ----+--+-=-≡- 因此，1(1)(1)(1)(mod )!a p p a xb p a ---+≡-是同余式(mod )ax b p ≡的解。