第五章同余方程
本章主要介绍同余方程的基础知识，并介绍几类特殊的同余方程的解法。
第一节同余方程的基本概念
本节要介绍同余方程的基本概念及一次同余方程。
在本章中，总假定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)
107
108 的解。
证明 留做习题。
下面，我们来研究一次同余方程的解。
定理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)。记d = (a , m )，以及
t = dq + r ，q ∈Z ，r = 0, 1, 2, , d - 1，
则
x = x 0 + qm +r d
m x r d m +≡0(mod m )，0 ≤ r ≤ d - 1。 容易验证，当r = 0, 1, 2, , d - 1时，相应的解
d
m d x d m x d m x x )1(20000-+++，，，， 对于模m 是两两不同余的，所以同余方程(2)恰有d 个解。证毕。 在定理的证明中，同时给出了解方程(2)的方法，但是，对于具体的方程(2)，常常可采用不同的方法去解。
例1 设(a , m ) = 1，又设存在整数y ，使得a ∣b + ym ，则
x ≡a
ym b +(mod m ) 是方程(2)的解。
解 直接验算，有
ax ≡ b + ym ≡ b (mod m )。
109 注：例1说明，求方程(2)的解可以转化为求方程
my ≡ -b (mod a ) (5)
的解，这有两个便利之处：第一，将一个对于大模m 的同余方程转化为一个对于小模a 的同余方程，因此有可能通过对模a 的完全剩余系进行逐个验证，以求出方程(5)和(2)的解；第二，设m ≡ r (mod a )，r < a ，则又可继续转化成一个对于更小的模r 的同余方程。
例2 解同余方程
325x ≡ 20 (mod 161) (6)
解 同余方程(6)即是
3x ≡ 20 (mod 161)。
解同余方程
161y ≡ -20 (mod 3)，
2y ≡ 1 (mod 3)，
得到y ≡ 2 (mod 3)，因此方程(6)的解是
x ≡3
161220?+= 114 (mod 161)。 例3 设a > 0，且(a , m ) = 1，a 1是m 对模a 的最小非负剩余，则同余方程
a 1x ≡ -
b ][a
m (mod m ) (7) 等价于同余方程(2)。
解 设x 是(2)的解，则由m =][a
m a + a 1得到 ][][])[(1a
m b a m ax x a m a m x a -≡-≡-=(mod m )， 即x 是同余方程(7)的解。但是由假设条件可知同余方程(2)与(7)都有且只有一个解。所以这两个同余方程等价。
注：用本例的方法，可以将同余方程(2)转化成未知数的系数更小一些的同余方程，从而易于求解。
例4 解同余方程6x ≡ 7 (mod 23)。
解 由例3，依次得到
6x ≡ 7 (mod 23) ? 5x ≡ -7?3 ≡ 2 (mod 23)
? 3x ≡ -2?4 ≡ -8 (mod 23)
110
? 2x ≡ -8(-7) ≡ 10 (mod 23)
? x ≡ 5 (mod 23)。
例5 设(a , m ) = 1，并且有整数δ > 0使得
a δ ≡ 1 (mod m )，
则同余方程(2)的解是
x ≡ ba δ - 1 (mod m )。
解 直接验证即可。
注：由例5及Euler 定理可知，若(a , m ) = 1，则
x ≡ ba ?(m ) - 1 (mod m )
总是同余方程(2)的解。
例6 解同余方程
81x 3 + 24x 2 + 5x + 23 ≡ 0 (mod 7)。
解 原同余方程即是
-3x 3 + 3x 2 - 2x + 2 ≡ 0 (mod 7)。
用x = 0，±1，±2，±3逐个代入验证，得到它的解是
x 1 ≡ 1，x 2 ≡ 2，x 3 ≡ -2 (mod 7)。
注：本例使用的是最基本的解同余方程的方法，一般说来，它的计算量太大，不实用。
例7 解同余方程组
???≡-≡+)7(m od 232)7(m od 153y x y x 。 (8) 解 将(8)的前一式乘以2后一式乘以3再相减得到
19y ≡ -4 (mod 7)，
5y ≡ -4 (mod 7)，
y ≡ 2 (mod 7)。
再代入(8)的前一式得到
3x + 10 ≡ 1 (mod 7)，
x ≡ 4 (mod 7)。
即同余方程组(8)的解是x ≡ 4，y ≡ 2 (mod 7)。
例8 设a 1，a 2是整数，m 1，m 2是正整数，证明：同余方程组
?
??≡≡)(m od )(m od 2211m a x m a x (9)
111
有解的充要条件是
a 1 ≡ a 2 (mod (m 1, m 2))。 (10)
若有解，则对模[m 1, m 2]是唯一的，即若x 1与x 2都是同余方程组(9)的解，则
x 1 ≡ x 2 (mod [m 1, m 2])。 (11)
解 必要性是显然的。下面证明充分性。
若式(10)成立，由定理2，同余方程
m 2y ≡ a 1 - a 2 (mod m 1)
有解y ≡ y 0 (mod m 1)，记x 0 = a 2 + m 2y 0，则
x 0 ≡ a 2 (mod m 2)
并且
x 0 = a 2 + m 2y 0 ≡ a 2 + a 1 - a 2 ≡ a 1 (mod m 1)，
因此x 0是同余方程组的解。
若x 1与x 2都是方程组(9)的解，则
x 1 ≡ x 2 (mod m 1)，x 1 ≡ x 2 (mod m 2)，
由同余的基本性质，得到式(11)。
习 题 一
1. 证明定理1。
2. 解同余方程：
(ⅰ) 31x ≡ 5 (mod 17)；
(ⅱ) 3215x ≡ 160 (mod 235)。
3. 解同余方程组：
?
??≡-≡+)47(m od 10)47(m od 3853y x y x 。 4. 设p 是素数，0 < a < p ，证明：
!
)1()2)(1()1(1
a a p p p
b x a +-???---≡-(mod p )。 是同余方程ax ≡ b (mod p )的解。
5. 证明：同余方程a 1x 1 + a 2x 2 + + a n x n ≡ b (mod m )有解的充要条件是
112 (a 1, a 2, , a n , m ) = d ∣b 。
若有解，则恰有d ?m n -1
个解，mod m 。
6. 解同余方程：2x + 7y ≡ 5 (mod 12)。 第二节 孙子定理
本节要讨论同余方程组
???????≡≡≡)
(m od )(m od )(m od 2211k k m a x m a x m a x 。 (1) 在第一节的例题中，我们已讨论了k = 2的情形。下面考察一般情形。 定理1(孙子定理) 设m 1, m 2, , m k 是正整数，
(m i , m j ) = 1，1 ≤ i , j ≤ k ，i ≠ j 。 (2)
记
m = m 1m 2 m k ，M i =i
m m ，1 ≤ i ≤ k ， 则存在整数M i '（1 ≤ i ≤ k ），使得
M i M i ' ≡ 1 (mod m i )， (3)
M i M i ' ≡ 0 (mod m i )，1 ≤ j ≤ k ，i ≠ j ， (4)
并且
i k
i i i M M a x '≡∑=10(mod m ) (5)
是同余方程组(1)对模m 的唯一解，即若有x 使方程组(1)成立，则
x ≡ x 0 (mod m )。 (6)
证明 由式(2)，有(M i , m i ) = 1，因此利用辗转相除法可以求出M i '与y i ，使得
M i M i ' + y i m i = 1，
即M i '满足式(3)和式(4)。由式(3)与式(4)，对于1 ≤ i ≤ k ，有
x 0 ≡ a i M i M i ' ≡ a i (mod m i )，1 ≤ i ≤ k 。
113
若x 也使式(1)成立，则
x ≡ x 0 (mod m i )，1 ≤ i ≤ k ，
因此
x ≡ x 0 (mod [m 1, m 2, , m k ])。
但是，由式(2)可知[m 1, m 2, , m k ] = m ，这就证明了式(6)。证毕。 定理2 在定理1的条件下，若式(1)中的a 1, a 2, , a k 分别通过模m 1, m 2, , m k 的完全剩余系，则式(5)中的x 0通过模m 1m 2 m k 的完全剩余系。 证明 这是第二章第二节习题6的特例。证毕。
定理3 同余方程组(1)有解的充要条件是
a i ≡ a j (mod (m i , m j ))，1 ≤ i , j ≤ n 。 (7)
证明 必要性是显然的。下面证明充分性。
当n = 2时，由第一节例8可知充分性成立。
假设充分性当n = k 时成立。
假设式(7)当n = k + 1时成立。我们来考虑同余方程组
x ≡ a i (mod m i )，1 ≤ i ≤ k + 1。
由第一节例8，存在b k ，使得x ≡ b k (mod [m k ，m k +1])满足同余方程组
x ≡ a k (mod m k )，x ≡ a k + 1 (mod m k + 1)。
在同余方程组
???????≡≡≡+--])
,[(m od )(m od )(m od 11111k k k k m m b x m a x m a x 中，由式(7)有
a i ≡ a j (mod (m i , m j ))，1 ≤ i , j ≤ k - 1，
因此，若能证明
a i ≡
b k (mod (m i , [m k , m k +1]))，1 ≤ i ≤ k - 1。 (8)
则由归纳假设就可以证明充分性。
由b k 的定义，有
a k ≡
b k (mod m k )，a k + 1 ≡ b k (mod m k + 1) (9)
而且，由于假设式(7)当n = k + 1时成立，所以，对于1 ≤ i ≤ k - 1有
a i ≡ a k (mod (m i , m k ))，a i ≡ a k + 1 (mod (m i , m k + 1))，
由此及式(9)得到，对于1 ≤ i ≤ k - 1，有
114 a i ≡ b k (mod (m i , m k ))，a i ≡ b k (mod (m i , m k + 1))。
因此
a i ≡
b k (mod [(m i , m k ), (m i , m k + 1)])。
由上式及第一章第六节例2，就得到式(8)。证毕。
定理4 设m = m 1m 2 m k ，其中m 1, m 2, , m k 是两两互素的正整数，f (x )是整系数多项式，以T 与T i （1 ≤ i ≤ k ）分别表示同余方程
f (x ) ≡ 0 (mod m ) (10)
与
f (x ) ≡ 0 (mod m i ) (11)
的解的个数，则T = T 1T 2…T k 。
证明 由第二章第一节定理5可知，同余方程(10)等价于同余方程组
f (x ) ≡ 0 (mod m i )，1 ≤ i ≤ k 。 (12)
对于每i （1 ≤ i ≤ k ），设同余方程(11)的全部解是
)()(2)(1,,,i T i i i
x x x x ≡(mod m i )， (13) 则同余方程组(12)等价于下面的T 1T 2…T k 个方程组：
????
?????≡≡≡)(m od )(m od )(m od )(
2)2(1)1(
21k k j j j m x x m x x m x x k ， (14) 其中)(
i j i
x 通过式(13)中的数值，即通过同余方程(11)的全部解。 由孙子定理，对于选定的每一组{)(
)2(
)1(
,,,21k j j j k
x x x }，同余方程组(14)对模m 有唯一解，而且，由定理2，当每个)(
i j i
x 通过(13)式中的值时，所得到的T 1T 2…T k 个同余方程组(14)的解对于模m 都是两两不同余的。证毕。
由定理4及算术基本定理，解一般模的同余方程可以转化为解模为素数幂的同余方程。
例1 求整数n ，它被3，5，7除的余数分别是1，2，3。
解 n 是同余方程组
n ≡ 1 (mod 3)，n ≡ 2 (mod 5)，n ≡ 3 (mod 7)
的解。在孙子定理中，取
m1 = 3，m2 = 5，m3 = 7，m = 3?5?7 = 105，
M1 = 35，M2 = 21，M3 = 15，
M1' =-1，M2' = 1，M3' = 1，
则
n≡ 1?35?(-1) + 2?21?1 + 3?15?1 ≡ 52 (mod 105)，
因此所求的整数n = 52 + 105t，t∈Z。
例2解同余方程
5x2+ 6x+ 49 ≡ 0 (mod 60)。(15) 解因为60 = 3?4?5，所以，同余方程(15)等价于同余方程组
5x2+ 6x+ 49 ≡ 0 (mod 3) (16)
5x2+ 6x+ 49 ≡ 0 (mod 4) (17)
5x2+ 6x+ 49 ≡ 0 (mod 5)。(18) 分别解同余方程(16)，(17)，(18)得到解
x1(1)≡ 1，x2(1)≡-1 (mod 3)，
x1(2)≡ 1，x2(2)≡-1 (mod 4)，
x1(3)≡ 1 (mod 5)，
这样，同余方程(15)的解x可由下面的方程组决定：
x≡a1 (mod 3)，x≡a2 (mod 4)，x≡a3 (mod 5)，
其中a1 = 1或-1，a2 = 1或-1，a3 = 1。利用孙子定理，取
m1 = 3，m2 = 4，m3 = 5，m = 60，
M1 = 20，M2 = 15，M3 = 12，
M1' = 2，M2' =-1，M3' = 3，
则
x≡ 40a1- 15a2+ 36a3 (mod 60)。
将a1，a2，a3所有可能的取值代入上式，得到方程(15)的全部解是
x1≡ 40?1- 15?1 + 36?1 ≡ 1 (mod 60)，
x2≡ 40?(-1)- 15?1 + 36?1 ≡-19 (mod 60)，
x3≡ 40?1- 15?(-1) + 36?1 ≡ 31 (mod 60)，
x4≡ 40?(-1)- 15?(-1) + 36?1 ≡ 11 (mod 60)。
115
116 习 题 二
1. 解同余方程组：???????≡≡≡≡。
)11(m od )7(m od )6(m od )5(m od 4321b x b x b x b x 2. 解同余方程组：??
???≡≡≡。)25(m od 13)8(m od 5)15(m od 8x x x
3. 有一队士兵，若三人一组，则余1人；若五人一组，则缺2人；若十一人一组，则余3人。已知这队士兵不超过170人，问这队士兵有几人？
4. 求一个最小的自然数n ，使得它的21是一个平方数，它的3
1是一个立方数，它的5
1是一个5次方数。 5. 证明：对于任意给定的n 个不同的素数p 1, p 2, …, p n ，必存在连续n 个整数，使得它们中的第k 个数能被p k 整除。
6. 解同余方程：3x 2 + 11x - 20 ≡ 0 (mod 105)。
第三节 模p α的同余方程
在第二节中，我们已经看到，求解模m 的同余方程可以转化为对模p α的同余方程的求解。本节要对模p α的同余方程做进一步讨论。 容易看出，若x 0是同余方程
f (x ) ≡ 0 (mod p α) (1)
的解，则它必是方程
f (x ) ≡ 0 (mod p α - 1) (2)
的解，因此，必有与x 0相应的方程(2)的某个解x 1，使
x 0 ≡ x 1 (mod p α - 1)，x 0 = x 1 + p α - 1t 0，
117 此处，t 0是某个适当的整数。
这提示我们：可以从方程(2)的解中去求方程(1)的解。于是，现在的问题是，对于方程(2)的每个解x 1，是否必有方程(1)的解x 0与之对应？若有，如何去确定它？
定理 设p 是素数，α ≥ 2是整数，f (x ) = a n x n + + a 1x + a 0是整系数多项式，又设x 1是同余方程(2)的一个解。以f '(x )表示f (x )的导函数。 (ⅰ) 若f '(x 1)≡/0 (mod p )，则存在整数t ，使得
x = x 1 + p α - 1t (3)
是同余方程(1)的解。
(ⅱ) 若f '(x 1) ≡ 0 (mod p )，并且f (x 1) ≡ 0 (mod p α)，则对于t = 0，1, 2, , p - 1，式(3)中的x 都是方程(1)的解。
证明 我们来说明，如何确定式(3)中的t ，使x 1 + p α - 1t 满足同余方程
(1)，即要使
a n (x 1+p α - 1t )n +a n - 1(x 1+p α - 1t )n - 1+ +a 1(x 1+p α - 1t )+a 0 ≡ 0 (mod p α)， (4) 即
f (x 1) + p α - 1tf '(x 1) ≡ 0 (mod p α)，
tf '(x 1) ≡ -1
1)(-αp x f (mod p )。 (5) 下面考虑两种情形。
(ⅰ) 若f '(x )≡/0 (mod p )，则关于t 的同余方程(5)有唯一解t ≡ t 0 (mod p )，即t = t 0 + pk （k ∈Z ），于是
x ≡ x 1 + p α - 1t 0 (mod p α)
是同余方程(1)的解。
(ⅱ) 若f '(x 1) ≡ 0 (mod p )，并且f (x 1) ≡ 0 (mod p α)，则式(5)对于任意的整数t 成立，即同余方程(5)有p 个解
t ≡ i (mod p )，0 ≤ i ≤ p - 1。
于是x ≡ x 1 + p α - 1i (mod p α)，0 ≤ i ≤ p - 1，都是同余方程(1)的解。证毕。
在定理中，没有对f '(x 1) ≡ 0 (mod p )并且 f (x 1)≡/0 (mod p α)的情形进行
讨论。事实上，此时，同余方程(5)无解。即，我们无法从同余方程(2)的解x 1出发去求得同余方程(1)的解。
由定理，可以把解同余方程(1)，转化为解同余方程
f (x ) ≡ 0 (mod p )。 (6)
事实上，由方程(6)的解，利用定理，可以求出方程f(x) ≡ 0 (mod p2)的解，再利用定理，又可以求出方程f(x) ≡ 0 (mod p3)的解， ，直到求出方程(1)的解。
推论使用定理的记号，
(ⅰ) 若x≡a (mod p)是同余方程(6)的解，并且f'(a)≡/0 (mod p)，则存在xα，xα≡a (mod p)，使得x≡xα (mod pα)是同余方程(1)的解。(ⅱ) 若f'(x) ≡ 0 (mod p)与同余方程(6)没有公共解，则对于任意的整数α≥ 1，同余方程(1)与(6)的解数相同。
证明留做习题。
例1解同余方程
x3+ 3x - 14 ≡ 0 (mod 45)。
解原同余方程等价于同余方程组
x3+ 3x - 14 ≡ 0 (mod 9)，(7)
x3+ 3x - 14 ≡ 0 (mod 5)。(8) 先解同余方程(7)。容易验证，同余方程x3+ 3x - 14 ≡ 0 (mod 3)的解是x≡ 2 (mod 3)。
令x = 2 + 3t并代入方程(7)，得到
(2 + 3t)3+ 3(2 + 3t)- 14 ≡ 0 (mod 9)，(9) 容易看出，这是一个对于任何整数t都成立的同余式，所以，方程(9)的解是t≡ 0，1，2 (mod 3)，于是方程(7)的解是
x≡ 2，5，8 (mod 9)。(10) 再解同余方程(8)。用x = 0，1，2，3，4去验证，得到(8)的解是
x≡ 1，2 (mod 5)。
因此，原同余方程的解是下面六个同余方程组的解：
x≡a1 (mod 9)，a1 = 2，5，8，
x≡a2 (mod 5)，a2 = 1，2。
利用孙子定理解这六个方程组，记
m1 = 9，m2 = 5，m = 45，M1 = 5，M2 = 9，M1' = 2，M2' =-1，
则
x≡ 10a1- 9a2 (mod 45)。
将a1和a2的不同取值代入，得到所求的解是
x1≡ 10?2- 9?1 ≡ 11 (mod 45)，
x2≡ 10?2- 9?2 ≡ 2 (mod 45)，
118
x3≡ 10?5- 9?1 ≡ 41 (mod 45)，
x4≡ 10?5- 9?2 ≡ 32 (mod 45)，
x5≡ 10?8- 9?1 ≡ 26 (mod 45)，
x6≡ 10?8- 9?2 ≡ 17 (mod 45)。
例2解同余方程
2x2+ 13x - 34 ≡ 0 (mod 53)。(11) 解容易验证，同余方程
2x2+ 13x - 34 ≡ 0 (mod 5) (12) 有两个解x ≡-1，2 (mod 5)。
令
x =-1 + 5t，(13) 代入同余方程
2x2+ 13- 34 ≡ 0 (mod 52)，(14) 得到
2(-1 + 5t)2+ 13(-1 + 5t)- 34 ≡ 0 (mod 25)，
-45 + 45t≡ 0 (mod 25)，
9t≡ 9 (mod 5)，t≡ 1 (mod 5)。(15) 于是，将式(15)与式(13)联合，得到方程(14)的解
x =-1 + 5(1 + 5t1) = 4 + 25t1，t1∈Z。(16) 将式(16)中的x代入同余方程(11)，得到
2(4 + 25t1)2+ 13(4 + 25t1)- 34 ≡ 0 (mod 53)，
50 + 725t1≡ 0 (mod 53)，
2 + 29t1≡ 0 (mod 5)，
t1≡ 2 (mod 5)。
将上式与(16)联合，得到同余方程(11)的一个解
x = 4 + 25t1 = 4 + 25(2 + 5t2) ≡ 54 (mod 53)。
(ⅱ) 从同余方程(12)的另一个解x≡ 2 (mod 5)出发利用上述方法，可以求出同余方程(11)的另一个解。（略，请读者补足）。
例3 解同余方程
x2≡ 1 (mod 2k)，k∈N。(17) 解若k = 1，则方程(17)的解是x≡ 1 (mod 2)。
若k = 2，则方程(17)的解是x≡ 1，-1 (mod 4)。
若k ≥ 3，则同余方程(17)，即
119
x2- 1 = (x+ 1)(x - 1) ≡ 0 (mod 2k)，
的解必是奇数，设x = 2y + 1，则同余方程(1)成为
(2y+ 2)2y≡ 0 (mod 2k)，
y(y+ 1) ≡ 0 (mod 2k- 2)。(18) 同余方程(18)的解是y1≡ 0，y2≡-1 (mod 2k- 2)，即
y1 = 2k- 2u，y2 =-1 + 2k- 2v，u, v∈Z，
所以，方程(17)的解是
x1 = 2k- 1u+ 1，x2 = 2k- 1v- 1，u, v∈Z，
即
x≡ 1，1 + 2k- 1，-1，-1 + 2k- 1 (mod 2k)。
例4解同余方程x2≡ 2 (mod 73)。
解设x是这个同余方程的解，则它可以表示成
x = x0+ 7x1+ 72x2，0 ≤x i≤ 6，0 ≤i ≤ 2，
代入原方程，得到
(x0+ 7x1+ 72x2)2≡ 2 (mod 73)，(19) 因此
(x0+ 7x1+ 72x2)2≡ 2 (mod 7)，
x02≡ 2 (mod 7)，
所以x0≡ 3或4 (mod 7)。于是x0 = 3或4。
(ⅰ) 若x0 = 3，由式(19)，有
(3 + 7x1+ 72x2)2≡ 2 (mod 72)，
9 + 42x1≡ 2 (mod 72)，
6x1≡-1 (mod 7)，
x1≡ 1 (mod 7)，x1 = 1。
再由式(19)，有
(3 + 7?1 + 72x2)2≡ 2 (mod 73)，
(10 + 49x2)2≡ 2 (mod 73)，
3x2≡-1 (mod 7)，x2≡ 2 (mod 7)，x2 = 2。
这样，求得原同余方程的一个解是
x≡ 3 + 7?1 + 72?2 = 108 (mod 73)。
(ⅱ) 若x0 = 4，用同样的方法求出另一个解。（略）。
注：例4中的方法是利用数的b进制表示，这一方法可以处理模b k的同余方程，而不必要求b是素数。
120
习题三
1.证明定理的推论。
2.将例2中略去的部分补足。
3.将例4中略去的部分补足。
4.解同余方程x2≡-1 (mod 54)。
5.解同余方程f(x) = 3x2+ 4x- 15 ≡ 0 (mod 75)。
6.证明：对于任意给定的正整数n，必存在m，使得同余方程x2≡ 1 (mod m)的解数T > n。
第四节素数模的同余方程
在上节中，我们证明了，对于素数p，模pα的同余方程的求解可以转化为模p的同余方程的求解。本节要对素数模的同余方程做些初步研究。
以下，设f(x) = a n x n+ +a1x+a0是整系数多项式，p是素数，p|/a n。定理1设k ≤n，若同余方程
f(x) = a n x n+ +a1x+a0≡ 0 (mod p) (1) 有k个不同的解x1, x1, , x k，则对于任意的整数x，有
f(x) ≡ (x-x1) (x-x2) (x-x k)f k(x) (mod p)，
其中f k(x)是一个次数为n-k的整系数多项式，并且它的x n-k项的系数是a n。
证明由多项式除法，有
f(x) = (x-x1)f1(x) +r1，(2) 其中f1(x)是首项系数为a n的n- 1次整系数多项式，r1是常数。在式(2)两边令x = x1，则由假设条件可知f(x1) = r1≡ 0 (mod p)，因此，式(2)成为
f(x) ≡ (x-x1)f1(x) (mod p)。(3) 因此，当k = 1时，定理成立。如果k > 1，在上式中，令x = x i（i = 2, 3, , k），则有
0 ≡f(x i) ≡ (x i-x1)f1(x i) (mod p)。(4)
121
由于x2, , x k对于模p是两两不同余的，所以，上式给出
f1(x i) ≡ 0 (mod p)，i = 2, , k。(5) 由此及归纳法，即可证明定理。证毕。
推论若p是素数，则对于任何整数x，有
x p- 1- 1 ≡ (x- 1)(x- 2) (x-p+ 1) (mod p)。
证明由Fermat定理（第二章第四节定理2），数1, 2, , p- 1是同余方程
x p- 1≡ 1 (mod p)
的解，因此，利用定理1即可得证。
定理2同余方程(1)的解数≤n。
证明假设同余方程(1)有n + 1个不同的解
x≡x i (mod p)，1 ≤i ≤n+ 1。
由定理1，有f(x) ≡a n(x-x1) (x-x n) (mod p)，因此
0 ≡f(x n + 1) ≡a n(x n + 1-x1) (x n + 1-x n) (mod p)。(6) 由于p|/a n，x n + 1≡/x i (mod p)，1 ≤i ≤n，所以式(6)不能成立。这个矛盾说明同余方程(1)不能有n+ 1个解。证毕。
推论若同余方程b n x n+ +b0≡ 0 (mod p)的解数大于n，则
p∣b i，0 ≤i ≤n。（7) 证明若式(7)不成立，设p|/b d，d ≤n，p∣b i，d< j ≤n。则
b n x n+ +b0≡b d x d+ +b0≡ 0 (mod p)。(8) 由定理2，同余方程(8)的解数不大于d，因而不大于n，这与假设矛盾。因此，式(7)必成立。证毕。
定理3同余方程(1)或者有p个解，或者存在次数不超过p- 1的整系数多项式r(x)，使得同余方程(1)与r(x) ≡ 0 (mod p)等价。
证明由多项式除法可知，存在整系数多项式g(x)与r(x)，使得
f(x) = g(x)(x p-x) +r(x)。(9) 由Fermat定理，对于任意的整数x，有x p≡x (mod p)，因此，如果r(x)的系数都是p的倍数，则对于任意的整数x，f(x) ≡ 0 (mod p)，即同余方程(1)有p个解。如果r(x)的系数不都是p的倍数，则r(x)的次数不超过p- 1。由式(9)看出，对于任意的整数x，f(x) ≡r(x) (mod p)，即同余方程(1)与r(x) ≡ 0 (mod p)等价。证毕。
定理4设n ≤p，则同余方程
122
123
f (x ) = x n + a n - 1x n - 1 + + a 1x + a 0 ≡ 0 (mod p ) (10)
有n 个解的充要条件是存在整数多项式q (x )和r (x )，r (x )的次数< n ，使得
x p - x = f (x )q (x ) + p ?r (x )。 (11)
证明 必要性 由多项式除法，存在整系数多项式q (x )与r 1(x )，r 1(x )的次数< n ，使得
x p - x = f (x )q (x ) + r 1(x )。 (12)
若同余方程(10)有n 个解x ≡ x i (mod p )（1 ≤ i ≤ n ），则由式(12)和Fermat 定理，得到
r 1(x i ) ≡ 0 (mod p )，1 ≤ i ≤ n 。
由此及定理2推论，可知r 1(x )的系数都能被p 整除，即
r 1(x ) = p ?r (x )，
其中r (x )是整系数多项式。这证明了式(11)。
充分性 若式(11)成立，由Fermat 定理，对于任何整数x ，有
0 ≡ x p - x ≡ f (x )q (x ) (mod p )， (13)
即同余方程
f (x )q (x ) ≡ 0 (mod p )
有p 个解，但是，q (x )是p - n 次多项式，所以由定理2，方程q (x ) ≡ 0 (mod p )的解数 ≤ p - n 。以λ表示同余方程(10)的解数，则由第一节定理1，有
λ + p - n ≥ p ，λ ≥ n ，
再利用定理2，得到λ = n 。 证毕。
注：若p |/
a n ，由辗转相除法可求出a n '，p |/a n '使得a n a n ' ≡ 1 (mod p )，于是，同余方程(1)与同余方程
a n 'f (x ) = x n + a n 'a n - 1x n - 1 + + a n 'a 1x + a n 'a 0 (mod p )
等价。因此，定理4是有普遍性的。
定理5 若p 是素数，n ∣p - 1，p |/
a 则 x n ≡ a (mod p ) (14)
有解的充要条件是
n p a 1
-≡1 (mod p )。 (15)
若有解，则解数为n 。
证明 必要性 若方程(14)有解x 0，则p |/
x 0，由Fermat 定理，得到
124 n p n n p x a 101)(--≡
= x 0p - 1 ≡1 (mod p )。
充分性 若式(15)成立，则 ，
)1()()()
1)((1111
1-+-=-+-=------n p n n p n p n p n p a x x P a x a a x x x x
其中P (x )是关于x 的整系数多项式。由定理4可知同余方程(14)有n 个解。证毕。
例1 判定同余方程2x 3 + 3x + 1 ≡ 0 (mod 7)是否有三个解。 解 因为2?4 ≡ 1 (mod 7)，所以，原方程与
4?2x 3 + 4?3x + 4 ≡ 0 (mod 7)
即
x 3 - 2x - 3 ≡ 0 (mod 7)
等价。由于
x 7 - x = ( x 3 - 2x - 3)(x 4 + 2x 2 + 3x + 4) + 12x 2 + 16x + 12，
所以，由定理4可知，原方程的解数小于3。
例2 解同余方程
3x 14 + 4x 10 + 6x - 18 ≡ 0 (mod 5)。
解 由Fermat 定理，x 5 ≡ x (mod 5)，因此，原同余方程等价于
2x 2 + x - 3 ≡ 0 (mod 5)。 (16)
将x ≡ 0，±1，±2 (mod 5)分别代入方程(16)进行验证，可知这个同余方程解是x ≡ 1 (mod 5)。 习 题 四
1. 解同余方程：
(ⅰ) 3x 11 + 2x 8 + 5x 4 - 1 ≡ 0 (mod 7)；
(ⅱ) 4x 20 + 3x 12 + 2x 7 + 3x - 2 ≡ 0 (mod 5)。
2. 判定
(ⅰ) 2x 3 - x 2 + 3x - 1 ≡ 0 (mod 5)是否有三个解；
(ⅱ) x 6 + 2x 5 - 4x 2 + 3 ≡ 0 (mod 5)是否有六个解？
3.设(a, m) = 1，k与m是正整数，又设x0k≡a (mod m)，证明同余方程
x k≡a(mod m)
的一切解x都可以表示成x≡yx0 (mod m)，其中y满足同余方程y k≡ 1 (mod m)。
4.设n是正整数，p是素数，(n, p- 1) = k，证明同余方程x n≡ 1 (mod p)有k个解。
5.设p是素数，证明：
(ⅰ) 对于一切整数x，x p- 1- 1 ≡ (x- 1) (x- 2) (x-p+ 1) (mod p)；(ⅱ) (p- 1)! ≡- 1 (mod p)。
6.设p≥ 3是素数，证明：(x- 1)(x- 2) (x-p+ 1)的展开式中除首项及常数项外，所有的系数都是p的倍数。
第五节素数模的二次同余方程
设p是素数，我们来研究素数模p的二次同余方程
ax2+bx+c≡ 0 (mod p)。(1) 如果p = 2，则可以直接验证x≡ 0或1 (mod 2)是否方程(1)的解。
如果(a, p) = p，则方程(1)成为一元一次同余方程。因此，只需考察p > 2，(a, p) = 1的情形。此时，因为(4a, p) = 1，所以，方程(1)等价于方程
4a2x2+ 4abx+ 4ac≡ 0 (mod p)，
即
(2ax+b)2≡b2- 4ac (mod p)。
这样，研究方程(1)归结为对方程
x2≡n (mod p) (2) 的研究。
定义１给定整数p，对于任意的整数n，(n，p) = 1，若方程(2)有解，则称n是模p的二次剩余，记为n∈QR(p)；否则，称n是模p的二次非剩余，记为n∈QNR(p)。
显然，若n1≡n2 (mod p)，则它们同是模p的二次剩余（或二次非剩余），因此，在谈到模p的二次剩余（或二次非剩余）时，把n1和n2看作是
125
126 同一个。
以下，在本节中，总假定p 是奇素数。
定理１ 若(n , p ) = 1，则
(ⅰ) n 是模p 的二次剩余的充要条件是
2
1-p n ≡ 1 (mod p )； (3)
(ⅱ) 若n 是模p 的二次剩余，则方程(2)有两个解；
(ⅲ) n 是模p 的二次非剩余的充要条件是
21-p n ≡ -1 (mod p )。 (4)
证明 结论(ⅰ)与(ⅱ)由第四节定理５直接推出。
(ⅲ) 若(n , p ) = 1，由第二章第四节定理１，有
n p - 1 ≡ 1 (mod p )， )1)(1(2
121-+--p p n n ≡ 0 (mod p )。 (5)
因为p 是奇素数，所以式(3)式与式(4)必有且仅有一个成立，利用结论(ⅰ)，可得到结论(ⅲ)。证毕。
定理２ 模p 的简化系中，二次剩余与二次非剩余的个数都是2
1-p ，而且，模p 的每个二次剩余与且仅与数列
12，22， ，2)(2
1-p (6) 中的一个数同余。
证明 显然，数列(6)包含了模p 的全部二次剩余。为了证明定理，只需证明式(6)中的任何两个数对模p 不同余。
对任意的整数k ，s ，1 ≤ k < s ≤2
1-p ，若 k 2 ≡ s 2 (mod p )， (7)
则p ∣k + s 或p ∣k - s 。这都是不可能的，所以式(7)不能成立。证毕。 定义２ 给定奇素数p ，对于整数n ，定义Legendre 符号为
?????∈-∈≠=。当，；当，；当，)(1)(11),(0)(p QNR n p QR n p n p n
初等数论练习题一 一、填空题 1、τ(2420)=27；?(2420)=_880_ 2、设a ，n 是大于1的整数，若a n -1是质数，则a=_2. 3、模9的绝对最小完全剩余系是_{-4，-3，-2，-1，0，1，2，3，4}. 4、同余方程9x+12≡0(mod 37)的解是x ≡11(mod 37)。 5、不定方程18x-23y=100的通解是x=900+23t ，y=700+18t t ∈Z 。. 6、分母是正整数m 的既约真分数的个数为_?(m )_。 7 8、??? ??10365 =-1。 9、若p 是素数，则同余方程x p - 1 ≡1(mod p )的解数为二、计算题 1、解同余方程：3x 2+11x -20≡0 (mod 105)。 解：因105 = 3?5?7， 同余方程3x 2+11x -20≡0 (mod 3)的解为x ≡1 (mod 3)， 同余方程3x 2+11x -38 ≡0 (mod 5)的解为x ≡0，3 (mod 5)， 同余方程3x 2+11x -20≡0 (mod 7)的解为x ≡2，6 (mod 7)， 故原同余方程有4解。 作同余方程组：x ≡b 1 (mod 3)，x ≡b 2 (mod 5)，x ≡b 3 (mod 7)， 其中b 1 = 1，b 2 = 0，3，b 3 = 2，6， 由孙子定理得原同余方程的解为x ≡13，55，58，100 (mod 105)。 2、判断同余方程x 2≡42(mod 107)是否有解？ 11074217 271071107713231071107311072107 710731072107732107422110721721107213)(=∴-=-=-==-=-=-==??≡-?--?-）（）（）（）（），（）（）（）（），（）（））（）（（ ）（解： 故同余方程x 2≡42(mod 107)有解。 3、求（127156+34）28除以111的最小非负余数。
1 浙江省2018年4月高等教育自学考试 初等数论试题 课程代码：10021 一、单项选择题(本大题共5小题，每小题2分，共10分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．20被-30除的余数是（ ） A ．-20 B ．-10 C ．10 D ．20 2．176至545的正整数中，13的倍数的个数是（ ） A ．27 B ．28 C ．29 D ．30 3．200!中末尾相继的0的个数是（ ） A ．49 B ．50 C ．51 D ．52 4．从以下满足规定要求的整数中，能选取出模20的简化剩余系的是（ ） A ．2的倍数 B ．3的倍数 C ．4的倍数 D ．5的倍数 5．设n 是正整数，下列选项为既约分数的是（ ） A ． 3144 21++n n B ． 121 -+n n C ．2 512+-n n D ．1 31++n n 二、填空题(本大题共10小题，每小题3分，共30分) 请在每小题的空格中填上正确答案。错填、不填均无分。 1．d(120)=___________。 2．314162被163除的余数是___________。 3．欧拉定理是___________。 4．同余方程3x ≡5(mod13)的解是___________。 5．不定方程10x-8y=12的通解是___________。
2 6．ο ___________)1847 365 ( = 7．［-π］＝___________。 8．为使n-1与3n 的最大公因数达到最大的可能值，则整数n 应满足条件___________。 9．如果一个正整数具有21个正因数，问这个正整数最小是___________。 10．同余方程x 3+x 2-x-1≡0(mod 3)的解是___________。 三、计算题(本大题共4小题，每小题10分，共40分) 1．解同余方程组 ???? ?? ?≡≡≡≡) 9(mod 4)7(mod 32)4(mod 23) 25(mod 1x x x x 2．解不定方程15x+10y+6z=19。 3．试求出所有正整数n ，使得2n -1能被7整除。 4．判断同余方程 x 2≡-1457(mod 2389) 是否有解？ 四、证明题(本大题共2小题，每小题10分，共20分) 1．证明形如4n+3的素数有无穷多个。 2．证明不定方程 x 2+y 2+z 2=x 2y 2 没有正整数解。
第三章 同 余 §1 同余的概念及其基本性质 。，所有奇数；所有偶数，例如，。 不同余，记作：对模则称；若所得的余数不同，同余，记作：对模则称所得的余数相同，与去除两个整数，称之为模。若用设)2(mod 1)2(mod 0)7(mod 18)(mod ,)(mod ,≡≡≡≡/≡∈+a a m b a m b a m b a m b a b a m m Z 定义1。 故同余关系是等价关系；（传递性），则，、若；（对称性） ，则、若；（反身性） 、：关系，它具有下列性质同余是整数之间的一种)(mod )(mod )(mod 3)(mod )(mod 2)(mod 1m c a m c b m b a m a b m b a m a a ≡≡≡≡≡≡ 。 则，，，设。 ，，即同余的充分必要条件是对模整数)(|)()(mod ,0)(|,2121212211b a m q q m b a r r m b a m r r r mq b r mq a t mt b a b a m m b a -?-=-?=?≡<≤+=+=∈+=-证明定理1Z 。 ，则若； ，则，若)(mod )(mod )2()(mod )(mod )(mod )1(21212211m b c a m c b a m b b a a m b a m b a -≡≡++≡+≡≡性质1 。 ，则特别地，若； ，则，若)(mod )(mod )(mod )(mod )(mod 21212211m kb ka m b a m b b a a m b a m b a ≡≡≡≡≡性质2 。 ，则， ；特别地，若则 ，，，若)(mod ,,2,1,0)(mod )(mod ,,2,1)(mod )(mod 0110111111 111 111m b x b x b a x a x a n i m b a m y y B x x A k i m y x m B A n n n n n n n n i i k k i i k k k k k k k k +++≡+++=≡≡ =≡≡----∑∑ΛΛΛΛΛΛΛΛΛΛΛΛαααααααααααααααα定理2。，则，，，若)(mod )(mod 1),(1111m b a m b a m d d b b d a a ≡≡===性质3
2013年春西南大学《初等数论》作业及答案(共4次,已整理) 第一次作业 1、设n，m为整数，如果3整除n，3整除m，则9（）mn。 A：整除 B：不整除 C：等于 D：小于 正确答案：A 得分：10 2、整数6的正约数的个数是（）。 A：1 B：2 C：3 D：4 正确答案：D 得分：10 3、如果5|n ，7|n，则35（）n 。 A：不整除 B：等于 C：不一定 D：整除 正确答案：D 得分：10 4、如果a|b，b|a ，则（）。 A：a=b B：a=-b C：a=b或a=-b D：a，b的关系无法确定 正确答案：C 得分：10 5、360与200的最大公约数是（）。 A：10 B：20 C：30 D：40 正确答案：D 得分：10 6、如果a|b，b|c，则（）。 A：a=c B：a=-c C：a|c D：c|a
正确答案：C 得分：10 7、1到20之间的素数是（）。 A：1，2，3，5，7，11，13，17，19 B：2，3，5，7，11，13，17，19 C：1，2，4，5，10，20 D：2，3，5，7，12，13，15，17 正确答案：B 得分：10 8、若a，b均为偶数，则a + b为（）。 A：偶数 B：奇数 C：正整数 D：负整数 正确答案：A 得分：10 9、下面的（）是模12的一个简化剩余系。 A：0，1，5，11 B：25，27，13，-1 C：1，5，7，11 D：1，-1，2，-2 正确答案：C 得分：10 10、下面的（）是模4的一个完全剩余系。 A：9，17，-5，-1 B：25，27，13，-1 C：0，1，6，7 D：1，-1，2，-2 正确答案：C 得分：10 11、下面的（）是不定方程3x + 7y = 20的一个整数解。 A：x=0,y=3 B：x=2,y=1 C：x=4,y=2 D：x=2,y=2 正确答案：D 得分：10 12、设a,b,c,d是模5的一个简化剩余系，则a+b+c+d对模5同余于（）。 A：0 B：1 C：2 D：3 正确答案：A 得分：10 13、使3的n次方对模7同余于1的最小的正整数n等于（）。 A：6 B：2
初等数论试卷一 一、 单项选择题：（1分/题×20题=20分） １．设x 为实数，[]x 为x 的整数部分，则( ) Ａ．[][]1x x x ≤<+； Ｂ．[][]1x x x <≤+； Ｃ．[][]1x x x ≤≤+； Ｄ．[][]1x x x <<+． ２．下列命题中不正确的是( ) Ａ．整数12,,,n a a a 的公因数中最大的称为最大公因数； Ｂ．整数12,, ,n a a a 的公倍数中最小的称为最小公倍数 Ｃ．整数a 与它的绝对值有相同的倍数 Ｄ．整数a 与它的绝对值有相同的约数 ３．设二元一次不定方程ax by c +=（其中,,a b c 是整数，且,a b 不全为零）有一整数解 ()00,,,x y d a b =，则此方程的一切解可表为( ) Ａ．00,,0,1,2,;a b x x t y y t t d d =- =+ =±± Ｂ．00,,0,1,2, ;a b x x t y y t t d d =+= -=±± Ｃ．00,,0,1,2, ;b a x x t y y t t d d =+= -=±± Ｄ．00,,0,1,2, ;b a x x t y y t t d d =-= -=±± ４．下列各组数中不构成勾股数的是( ) Ａ．５，１２，１３； Ｂ．７，２４，２５； Ｃ．３，４，５； Ｄ．８，１６，１７ ５．下列推导中不正确的是( ) Ａ．()()()11221212mod ,mod mod ;a b m a b m a a b b m ≡≡?+≡+ Ｂ．()()()11221212mod ,mod mod ;a b m a b m a a bb m ≡≡?≡ Ｃ．()()111212mod mod ;a b m a a b a m ≡?≡ Ｄ．()()112 2 11mod mod .a b m a b m ≡?≡ ６．模１０的一个简化剩余系是( ) Ａ．0,1,2, ,9; Ｂ．1,2,3,,10;
第五章同余方程 本章主要介绍同余方程的基础知识，并介绍几类特殊的同余方程的解法。 第一节同余方程的基本概念 本节要介绍同余方程的基本概念及一次同余方程。 在本章中，总假定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)。记d = (a , m )，以及 t = dq r ，q Z ，r = 0, 1, 2, , d 1， 则 x = x 0 qm r d m x r d m +≡0(mod m )，0 r d 1。 容易验证，当r = 0, 1, 2, , d 1时，相应的解 d m d x d m x d m x x )1(20000-+++，，，，Λ 对于模m 是两两不同余的，所以同余方程(2)恰有d 个解。证毕。 在定理的证明中，同时给出了解方程(2)的方法，但是，对于具体的方程(2)，常常可采用不同的方法去解。 例1 设(a , m ) = 1，又设存在整数y ，使得a b ym ，则 x a ym b +(mod m ) 是方程(2)的解。 解 直接验算，有 ax b ym b (mod m )。
第一章 §1 1 证明：n a a a ,,21 都是m 的倍数。 ∴存在n 个整数n p p p ,,21使 n n n m p a m p a m p a ===,,,222111 又n q q q ,,,21 是任意n 个整数 m p q p q q p a q a q a q n n n n )(22112211+++=+++∴ 即n n a q a q a q +++ 2211是m 的整数 2 证： )12)(1()12)(1(-+++=++n n n n n n n )1()1()2)(1(+-+++=n n n n n n )1()1/(6),2)(1(/6+-++n n n n n n )1()1()2)(1(/6+-+++∴n n n n n n 从而可知 )12)(1(/6++n n n 3 证： b a , 不全为0 ∴在整数集合{}Z y x by ax S ∈+=,|中存在正整数，因而 有形如by ax +的最小整数00by ax + Z y x ∈?,，由带余除法有00000,)(by ax r r q by ax by ax +<≤++=+ 则 S b q y y a q x x r ∈-+-=)()(00，由00by ax +是S 中的最小整数知0=r by ax by ax ++∴/00 下证8P 第二题 by ax by ax ++/00 （y x ,为任意整数） b by ax a by ax /,/0000++∴ ).,/(00b a by ax +∴ 又有b b a a b a /),(,/),( 00/),(by ax b a +∴ 故),(00b a by ax =+ 4 证：作序列 ,2 3, ,2 , 0,2 ,,2 3,b b b b b b - -- 则a 必在此序列的某两项之间
《初等数论》期末练习二 一、单项选择题 1、=),0(b （ ）. A b B b - C b D 0 2、如果1),(=b a ，则),(b a ab +=（ ）. A a B b C 1 D b a + 3、小于30的素数的个数（ ）. A 10 B 9 C 8 D 7 4、如果)(mod m b a ≡,c 是任意整数,则 A )(mod m bc ac ≡ B b a = C (mod )ac bc m ≡/ D b a ≠ 5、不定方程210231525=+y x （ ）. A 有解 B 无解 C 有正数解 D 有负数解 6、整数5874192能被( )整除. A 3 B 3与9 C 9 D 3或9 7、如果a b ，b a ，则( ). A b a = B b a -= C b a ≥ D b a ±= 8、公因数是最大公因数的（ ）. A 因数 B 倍数 C 相等 D 不确定 9、大于20且小于40的素数有（ ）. A 4个 B 5个 C 2个 D 3个 10、模7的最小非负完全剩余系是( ). A -3，-2,-1,0,1,2，3 B -6，-5,-4,-3,-2,-1 C 1,2,3,4,5，6 D 0,1,2,3,4，5，6 11、因为( ),所以不定方程71512=+y x 没有解. A [12，15]不整除7 B （12，15）不整除7 C 7不整除（12，15） D 7不整除[12，15] 12、同余式)593(mod 4382≡x （ ）. A 有解 B 无解 C 无法确定 D 有无限个解 二、填空题 1、有理数 b a ，0,(,)1a b a b <<=，能写成循环小数的条件是（ ）. 2、同余式)45(mod 01512≡+x 有解，而且解的个数为( ). 3、不大于545而为13的倍数的正整数的个数为( ). 4、设n 是一正整数，Euler 函数)(n ?表示所有( )n ，而且与n （ ）的正整数的个数. 5、设b a ,整数，则),(b a （ ）=ab . 6、一个整数能被3整除的充分必要条件是它的（ ）数码的和能被3整除. 7、+=][x x （ ）. 8、同余式)321(mod 75111≡x 有解,而且解的个数( ). 9、在176与545之间有( )是17的倍数.
初等数论考试试卷 一、 单项选择题：（1分/题×20题=20分） 1．设x 为实数，[]x 为x 的整数部分，则( A ) Ａ．[][]1x x x ≤<+； Ｂ．[][]1x x x <≤+； Ｃ．[][]1x x x ≤≤+； Ｄ．[][]1x x x <<+． 2．下列命题中不正确的是( B ) Ａ．整数12,, ,n a a a 的公因数中最大的称为最大公因数； < Ｂ．整数12,,,n a a a 的公倍数中最小的称为最小公倍数 【有最小的吗】 Ｃ．整数a 与它的绝对值有相同的倍数 Ｄ．整数a 与它的绝对值有相同的约数 3．设二元一次不定方程ax by c +=（其中,,a b c 是整数，且,a b 不全为零）有一整数解 ()00,,,x y d a b =，则此方程的一切解可表为( C ) Ａ．00,,0,1,2,;a b x x t y y t t d d =- =+=±± Ｂ．00,,0,1,2, ;a b x x t y y t t d d =+=-=±± Ｃ．00,,0,1,2, ;b a x x t y y t t d d =+=-=±± Ｄ．00,,0,1,2, ;b a x x t y y t t d d =-=-=±± （ 4．下列各组数中不构成勾股数的是( D ) Ａ．5，12，13； Ｂ．7，24，25； Ｃ．3，4，5； Ｄ．8，16，17 5．下列推导中不正确的是( D ) Ａ．()()()11221212mod ,mod mod ;a b m a b m a a b b m ≡≡?+≡+ Ｂ．()()()11221212mod ,mod mod ;a b m a b m a a bb m ≡≡?≡ Ｃ．()()111212mod mod ;a b m a a b a m ≡?≡
《初等数论》教学大纲 课程编码：110823 课程名称：初等数论 学时/学分：54/3 先修课程：《数学分析》、《高等代数》 适用专业：信息与计算科学 开设教研室：代数与几何教研室 一、课程性质与任务 1．课程性质：初等数论是信息与计算科学专业的一门专业必修课程。该课程是研究整数性质和方程（组）整数解的一门学科，也是一个古老的数学分支。初等数论是现代密码学的一门基础课程，也是高等学校信息安全专业的一门重要的基础课。初等数论在计算技术、通信技术等技术学科中也得到了广泛的应用。 2．课程任务：初等数论是信息与计算科学专业的一门重要的专业必修课，开设的目的在于使学生熟悉和掌握数论的基础知识，基本理论和基本的解题技能技巧，培养学生的逻辑思维能力，更深入地理解初等数论与其它邻近学科的关系，为进一步学习信息安全领域的其它学科打下坚实的基础。 二、课程教学基本要求 初等数论是研究整数性质的一门学科，历史上遗留下来没有解决的大多数数论难题其问题本身容易搞懂，容易引起人的兴趣，但是解决它们却非常困难。本课程的目的是简单介绍在初等数论研究中经常用到的若干基础知识、基本概念、方法和技巧。 通过本课程的学习，使学生加深对整数的性质的了解，更深入地理解初等数论与其它邻近学科的关系。 1. 有关定义、定理、性质等概念的内容按“知道、了解和理解”三个层次要求；有关计算、解法、公式和法则等方法的内容按“会、掌握、熟练掌握”三个层次要求。 2. 本课程开设在第5学期，总学时54，其中课堂讲授54学时，课堂实践0学时。教学环节以课堂讲授为主，研制电子教案和多媒体幻灯片以及CAI课件，在教学方法和手段上采用现代教育技术。 3. 成绩考核形式：期终成绩（闭卷考试）（70%）＋平时成绩（平时测验、作业、课堂提问、课堂讨论等）（30％）。成绩评定采用百分制，60分为及格。
1 证明：n a a a ,,21 都是m 的倍数。 ∴存在n 个整数n p p p ,,21使 n n n m p a m p a m p a ===,,,222111 又n q q q ,,,21 是任意n 个整数 m p q p q q p a q a q a q n n n n )(22112211+++=+++∴ 即n n a q a q a q +++ 2211是m 的整数 2 证： )12)(1()12)(1(-+++=++n n n n n n n )1()1()2)(1(+-+++=n n n n n n )1()1/(6),2)(1(/6+-++n n n n n n 1()1()2)(1(/6+-+++∴n n n n n n 从而可知 12)(1(/6++n n n 3 证： b a , 不全为0 ∴在整数集合{}Z y x by ax S ∈+=,|中存在正整数，因而 有形如by ax +的最小整数00by ax + Z y x ∈?,，由带余除法有00000,)(by ax r r q by ax by ax +<≤++=+ 则b q y y a q x x r ∈-+-=)()(00，由00by ax +是S 中的最小整数知0=r ax by ax + +∴/00 下证8P 第二题 by ax by ax ++/00 （y x ,为任意整数） b by ax a by ax /,/0000++∴ ,/(00b a by ax +∴ 又有b b a a b a /),(,/),( 0/),(by ax b a +∴ 故),(00b a by ax =+ 4 证：作序列 ,2 3, ,2 , 0,2 ,,2 3,b b b b b b - -- 则a 必在此序列的某两项之间
《数学史》教学大纲 课程编号：学分：总学时：54 适用专业：数学与应用数学开课学期： 先修专业：无后续课程：无 一、课程的性质、目的和要求 （一）课程的性质：选修课程。 （二）课程教学目的：能够以数学的、历史的眼光分析数学发展的内在原因，运用辩证唯物主义的哲学方法剖析数学发展史。 （三）课程基本要求：全面了解数学历史的发展过程，了解各个时期主要数学家的生平事迹和对数学发展的贡献，掌握重要的数学事件，理解主要的数学理论的形成过程以及历史文化背景。 二、本课程主要教学内容及时间安排 第一章：综述（８学时） 1、教学基本要求：分三阶段综合叙述数学历史发展过程，掌握各阶段的框架和脉络，理解中外各主要数学中心发展、转移、变化的过程。 2、教学重点：在教学上要求把握一个整体、三个阶段的特点（古典数学、近代数学和现代数学）。 3、教学难点： 4、本章知识点：⒈数学历史发展过程（5学时），作业量：1。 ⒉主要数学中心发展、转移、变化的过程（3学时），作业量：1。 第二章：东、西方初等数学的代表作（4学时） 1、教学基本要求：通过全面了解东、西方初等数学的代表作，即中国的《九章算术》和古希腊的《几何原本》的内容、背景和特点，把握两者的深刻的思想内涵和学术文化特征。 2、教学重点：把握《九章算术》和《几何原本》深刻的思想内涵和学术文化特征。 3、教学难点： 4、本章知识点：⒈数学历史发展过程（2学时），作业量：1。 ⒉主要数学中心发展、转移、变化的过程（2学时），作业量：1。 第三章：作图工具与计算工具（2学时） 1、教学基本要求：通过中、西方古代作图工具、计算工具的形成、发展过程的介绍，重点把握古希腊作图手段——尺规作图法，以及中国古代著名的计算工具——算筹的具体情况和历史背景。 2、教学重点：把握古希腊作图手段——尺规作图法，以及中国古代著名的计算工具——算筹的具体情况和历史背景。 3、教学难点：尺规作图法。 4、本章知识点：⒈尺规作图法及算筹的具体情况和历史背景。（2学时），作业量：1。 第四章：初等几何（2学时） 1、教学基本要求：沿着数的起源、发展的历史轨迹，重点了解记数的方法、数的运算以及数系扩充的历史发展过程，突出中国十进位制的历史地位和功绩，理解在数的扩充过程中，人类所表现出的困惑、好奇和对未知世界执着探索的精神状态。 2、教学重点：数系扩充的历史发展过程。 3、教学难点： 4、本章知识点：⒈数系扩充的历史发展过程。（2学时），作业量：1。 第五章：算术（2学时） 1、教学基本要求：了解自然数是基数与序数的统一，把握正负数的定义及分数的运算法则，
附录1 习题参考答案 第一章习题一 1. (ⅰ) 由a b知b = aq，于是b = (a)(q)，b = a(q)及b = (a)q，即a b，a b及a b。反之，由a b，a b及a b 也可得a b； (ⅱ) 由a b，b c知b = aq1，c = bq2，于是c = a(q1q2)，即a c； (ⅲ) 由b a i知a i= bq i，于是a1x1a2x2a k x k = b(q1x1 q2x2q k x k)，即b a1x1a2x2a k x k；(ⅳ) 由b a知a = bq，于是ac = bcq，即bc ac； (ⅴ) 由b a知a = bq，于是|a| = |b||q|，再由a 0得|q| 1，从而|a| |b|，后半结论由前半结论可得。 2. 由恒等式mq np= (mn pq) (m p)(n q)及条件m p mn pq可知m p mq np。 3. 在给定的连续39个自然数的前20个数中，存在两个自然数，它们的个位数字是0，其中必有一个的十位数字不是9，记这个数为a，它的数字和为s，则a, a 1, , a 9, a 19的数字和为s, s 1, , s 9, s 10，其中必有一个能被11整除。 4. 设不然，n1= n2n3，n2p，n3p，于是n = pn2n3p3，即p3n，矛盾。 5. 存在无穷多个正整数k，使得2k1是合数，对于这样的k，(k1)2
不能表示为a2p的形式，事实上，若(k 1)2= a2p，则(k 1 a)( k 1 a) = p，得k 1 a = 1，k 1 a = p，即p = 2k 1，此与p为素数矛盾。 第一章习题二 1. 验证当n =0,1，2，… ,11时，12|f(n)。 2.写a = 3q1r1，b = 3q2r2，r1, r2 = 0, 1或2，由3a2b2 = 3Q r12r22知r1 = r2 = 0，即3a且3b。 3.记n=10q+r, (r=0,1,…,9)，则n k+4-n k被10除的余数和r k+4-r k=r k(r4-1)被10 除的余数相同。对r=0,1,…,9进行验证即可。 4. 对于任何整数n，m，等式n2 (n 1)2 = m2 2的左边被4除的余数为1，而右边被4除的余数为2或3，故它不可能成立。 5 因a4 3a2 9 = (a2 3a 3)( a2 3a 3)，当a = 1，2时，a2 3a 3 = 1，a4 3a2 9 = a2 3a 3 = 7，13，a4 3a2 9是素数；当a 3时，a2 3a 3 > 1，a2 3a 3 > 1，a4 3a2 9是合数。 6. 设给定的n个整数为a1, a2, , a n，作 s1 = a1，s2 = a1a2，，s n = a1a2a n， 如果s i中有一个被n整除，则结论已真，否则存在s i，s j，i < j，使得s i与s j 被n除的余数相等，于是n s j s i = a i + 1a j。
初等数论第三次作业 计算题 1. 求75与105的最大公因数。 解：因为75 = 3错误！未找到引用源。52，105 = 3错误！未找到引用源。5错误！未找到引用源。7， 所以75与105的最大公因数是15。 2. 求66与121的最大公因数。 解：因为66=6×11,121=11×11， 所以66与121的最大公因数是11 3．求不定方程3x - 4y = 1的一切整数解。 答；因为（3,4）= 1，所以不定方程有整数解。 观察知x = 3，y = 2是其一个整数解。 由公式知其一切整数解为???+=+=t y t x 3243，t 为整数。 4．求不定方程7x + 2y = 1的一切整数解。 答；因为（7,2）=1,1|1，所以不定方程有解。观察知其一个整数解是 0013 x y =??=-?。 于是其一切整数解为1237x t y t =+??=--? ，t 取一切整数。 5．解同余式3x ≡ 1 (mod 7)。 答；因为（3,7）= 1，所以同余式有解且有一个解。 由3x - 7y = 1得???+=+=t y t x 3275， 所以同余式的解为)7(mod 5≡x 6．解同余式3x ≡ 8 (mod 10)。
答；因为（3,10）=1,1|8，所以同余式有解，并且只有一个解。由3108x y -=得 一个解00 61x y =??=?，所以同余式的解为6(mod10)x ≡。 7．解同余式28x ≡ 21 (mod 35)。 答：因为（28，35） = 7，而7|21，所以同余式28x ≡ 21(mod 35)有解，且有7个解。同余式28x ≡ 21(mod 35)等价于4x ≡ 3(mod 5)，解4x ≡ 3(mod 5)得x ≡ 2(mod 5)，故同余式28x ≡ 21(mod 35)的7个解为x ≡ 2，7，12，17，22，27，32(mod 35)。 8．解同余式组： ???≡≡) 5(mod 2)3(mod 1x x 。 答；由)3(mod 1≡x 得13+=k x ，将其代入)5(mod 2≡x 得)5(mod 213≡+k ， 解得)5(mod 2≡k ，即25+=t k ， 所以715+=t x ，所以解为)15(mod 7≡x 。 9. 求不定方程3x + 2y = 2的一切整数解。 解：因为(3,2) = 1，所以不定方程有整数解。 显然1,0==y x 是其一个特解， 所以不定方程的一切整数解为错误！未找到引用源。，其中t 取一切整数。 10.解同余式)5(mod 14≡x 答；因为（4,5）= 1，所以同余式有解且有一个解。 由4x - 5y = 1得???+=+=t y t x 3275， 所以同余式的解为)7(mod 5≡x
初等数论试卷和答案
初等数论考试试卷1 一、单项选择题(每题3分，共18分) 1、如果a b ，b a ，则( ). A b a = B b a -= C b a ≤ D b a ±= 2、如果n 3，n 5，则15（ ）n . A 整除 B 不整除 C 等于 D 不一定 3、在整数中正素数的个数（ ）. A 有1个 B 有限多 C 无限多 D 不一定 4、如果)(mod m b a ≡,c 是任意整数,则 A )(mod m bc ac ≡ B b a = C ac T )(mod m bc D b a ≠ 5、如果( ),则不定方程c by ax =+有解. A c b a ),( B ),(b a c C c a D a b a ),( 6、整数5874192能被( )整除. A 3 B 3与9 C 9 D 3或9 二、填空题(每题3分，共18分) 1、素数写成两个平方数和的方法是（ ）. 2、同余式)(mod 0m b ax ≡+有解的充分必要条件是( ). 3、如果b a ,是两个正整数,则不大于a 而为b 的倍数的正整数的个数为 ( ). 4、如果p 是素数,a 是任意一个整数,则a 被p 整除或者( ). 5、b a ,的公倍数是它们最小公倍数的( ).
试卷1答案 一、单项选择题(每题3分，共18分) 1、D. 2、A 3、C 4、A 5、A 6、B 二、填空题(每题3分，共18分) 1、素数写成两个平方数和的方法是（唯一的）. 2、同余式)(mod 0m b ax ≡+有解的充分必要条件是(b m a ),(). 3、如果b a ,是两个正整数,则不大于a 而为b 的倍数的正整数的个数为( ][b a ). 4、如果p 是素数,a 是任意一个整数,则a 被p 整除或者( 与p 互素 ). 5、b a ,的公倍数是它们最小公倍数的( 倍数 ). 6、如果b a ,是两个正整数,则存在( 唯一 )整数r q ,,使r bq a +=,b r ≤0. 三、计算题(每题8分，共32分) 1、 求[136,221,391]=?（8分） 解 [136,221,391] =[[136,221],391] =[391,17221136?] =[1768,391] ------------(4分) = 17391 1768?
作业次数：学号姓名作业成绩 第0章序言及预备知识 第一节序言（1） 1、数论人物、资料查询：（每人物写600字左右的简介） （1）华罗庚 2、理论计算与证明： （1 是无理数。 （2）Show that there are infinitely many Ulam numbers 3、用Mathematica 数学软件实现 A Ulam number is a member of an which was devised by and published in in 1964. The standard Ulam sequence (the (1, 2-Ulam sequence starts with U 1=1 and U 2=2 being the first two Ulam numbers. Then for n > 2, U n is defined to be the smallest that is the sum of two distinct earlier terms in exactly one way 。 By the definition, 3=1+2 is an Ulam number; and 4=1+3 is an Ulam number (The sum 4=2+2 doesn't count because the previous terms must be distinct. The integer 5 is not an Ulam number because 5=1+4=2+3. The first few terms are 1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26, 28, 36, 38, 47, 48, 53, 57, 62, 69, 72, 77,
《初等数论》本科 一 填空题（每空2分） 1.写出30以内的所有素数 2,3,5,7,11,13,17,19,23,29 . 2.,( ,)(,)(,) a b a b a b a b =设是任意两个不为零的整数,则 1 . 3.若,a b 是非零整数,则a 与b 互素的充要条件是存在整数,x y ,适1ax by += 4.写出180的标准分解式是 22235?? ,其正约数个数有 (2+1)(2+1)(1+1)=18个. 5.,1,2,,a b a b L 设与是正整数则在中能被整除的整数恰有 []a b 个. 6.设,a b 是非零整数,c 是整数,方程ax by c +=有整数解(,x y )的充要条件是 (,)|a b c 7. 若整数集合A 是模m 的完全剩余系,则A 中含有 m 个整数. 8.?(3)= 2 ;?(4)= 2 . 9.当p 素数时,(1)()p ?= 1p - ;(2)()k p ?= 1k k p p -- . 10.(),(,)1,1m m a m a ?=-≡设是正整数则 0 (mod ).m 11.,,p p a a a -≡设是素数则对于任意的整数有 0 (mod ).p 12.已知235(mod7)x +≡,则x ≡ 1 (mod7). 13.同余方程22(mod 7)x ≡的解是 4(mod7) . 14.同余方程2310120(mod 9)x x ++≡的解是 .X=6. . 15.(,)1n p =若,n p 是模的二次剩余的充要条件是 -121(mod ).p n p ≡ . 16.(,)1n p =若,n p 是模的二次非剩余的充要条件是 -12 1(mod ).p n p ≡- . 17.3()=5 -1 ; 4 ()=5 1 . 18.,p 设是奇素数则2 ()p = 218(1).p -- . 19.,p 设是奇素数则1()p = 1 ;-1 ()p = -1 2(-1).p . 20. 5()=9 1 ; 2 ()=45 -1 . 二 判断题(判断下列结论是否成立，每题2分). 1. ||,|a b a c x y Z a bx cy ?∈+且对任意的有.成立 2. (,)(,),[,][,]a b a c a b a c ==若则.不成立
初等数论考试试卷1 一、单项选择题(每题3分，共18分) 1、如果a b ，b a ，则( ). A b a = B b a -= C b a ≤ D b a ±= 2、如果n 3，n 5，则15（ ）n . A 整除 B 不整除 C 等于 D 不一定 3、在整数中正素数的个数（ ）. A 有1个 B 有限多 C 无限多 D 不一定 4、如果)(mod m b a ≡,c 是任意整数,则 A )(mod m bc ac ≡ B b a = C ac T )(mod m bc D b a ≠ 5、如果( ),则不定方程c by ax =+有解. A c b a ),( B ),(b a c C c a D a b a ),( 6、整数5874192能被( )整除. A 3 B 3与9 C 9 D 3或9 二、填空题(每题3分，共18分) 1、素数写成两个平方数和的方法是（ ）. 2、同余式)(mod 0m b ax ≡+有解的充分必要条件是( ). 3、如果b a ,是两个正整数,则不大于a 而为b 的倍数的正整数的个数为( ). 4、如果p 是素数,a 是任意一个整数,则a 被p 整除或者( ). 5、b a ,的公倍数是它们最小公倍数的( ). 6、如果b a ,是两个正整数,则存在( )整数r q ,,使r bq a +=,b r π≤0. 三、计算题(每题8分，共32分) 1、求[136,221,391]=? 2、求解不定方程144219=+y x . 3、解同余式)45(mod 01512≡+x . 4、求? ?? ??563429,其中563是素数. （8分） 四、证明题(第1小题10分，第2小题11分，第3小题11分，共32分)
第三章同余例题分析 例1：求3406的末二位数。 解：∵（3，100）=1，∴3)100(φ≡1（mod 100） φ(100)=φ(22·52)=40,∴340≡1(mol 100) ∴3406=(340)10·36≡(32)2·32≡-19×9≡-171≡29(mod 100) ∴末二位数为29。 例2：证明（a+b ）p ≡a p +b p (mod p ) 证：由费尔马小定理知对一切整数有：a p ≡a （p ），b p ≡b (P )， 由同余性质知有：a p +b p ≡a+b (p ) 又由费尔马小定理有（a+b ）p ≡a+b (p ) （a+b ）p ≡a p +b p (p ) 例3：设素数p >2，则2P -1的质因数一定是2pk +1形。 证：设q 是2p -1的质因数，由于2p -1为奇数，∴q ≠2， ∴（2·q ）=1,由条件q|2p -1,即2p ≡1（mod q ），又∵（q ,2）=1，2p ≡1（mod q ）设i 是使得2x ≡1（mod p ）成立最小正整数 若1
∴13|42n +1+3n +2 例5：证明5y +3=x 2无解 证明：若5y +3=x 2有解，则两边关于模5同余 有5y +3≡x 2(mod 5) 即3≡x 2(mod 5) 而任一个平方数x 2≡0,1,4(mod 5) ∴30,1,4(mod 5) ∴即得矛盾，即5y +3=x 2无解 例6：求 50111......被7除的余数。 解：∵111111被7整除，∴ 50111......≡11（mod 7）≡4（mod 7），即余数为 4。 例7：把..0.04263化为分数。 解：设b =...360420，从而1000b=...3642, 100000b=...364263，99000b=4263-42b=990004221 ==11000469 。 当然也可用直化分数的方法做。 例8：设一个数为62XY427是9，11的倍数，求X ，Y 解：因为9|62XY427 所以9|6+2+X+Y+4+2+7，即9|21+X+Y 又因为11|62XY427，有11|（7+4+X+6-2-Y-2） 即11|（X-Y+13） 因为0≤X，Y ≤9，所以有21≤21+X+Y ≤39， 4≤X-Y+13≤22，由此可知 21+X+Y=27，X-Y+13=11