初等数论第一章2

1、初等数论,Number Theory,第一章 整除理论,整除性理论是初等数论的基础。本章要介绍带余数除法，辗转相除法，最大公约数，最小公倍数，算术基本定理以及它们的一些应用。,第二节 带余数除法,在本节中，我们要介绍带余数除法及其简单应用。,定理1(带余数除法) 设a与b是两个整数，b 0，则存在唯一的两个整数q和r，使得 a = bq r，0 r |b|。 (1),第二节 带余数除法,证明 存在性 若ba，a = bq，qZ，可取r = 0。若b a，考虑集合 A = a kb；kZ , 其中Z表示所有整数的集合，以后，仍使用此记号，并以N表示所有正整数的集合。,在集合A中有无限多个正整数，

2、设最小的正整数是r = a k0b，则必有 0 |b|，a k0b |b| 0，这样，在集合A中，又有正整数a k0b |b| r，这与r的最小性矛盾。所以式(2)必定成立。取q = k0知式(1)成立。存在性得证。,第二节 带余数除法,唯一性 假设有两对整数q ，r 与q ，r 都使得式(1)成立，即 a = q b r = q b r ，0 r , r |b|， 则 (q q )b = r r ，|r r | |b|， (3) 因此r r = 0，r = r ，再由式(3)得出 q = q ，唯一性得证。证毕。,第二节 带余数除法,定义1 称式(1)中的q是a被b除的商，r是a被b除的余数

3、。,由定理1可知，对于给定的整数b，可以按照被b除的余数将所有的整数分成b类。在同一类中的数被b除的余数相同。这就使得许多关于全体整数的问题可以归化为对有限个整数类的研究。,第二节 带余数除法,以后除特别声明外，在谈到带余数除法时总是假定b是正整数。,例1 设a，b，x，y是整数, k和m是正整数, 并且 a = a1m r1，0 r1 m， b = b1m r2，0 r2 m， 则ax by和ab被m除的余数分别与r1x r2y和r1r2被m除的余数相同。特别地，ak 与r1k 被m除的余数相同。,第二节 带余数除法,解 由 ax by = (a1m r1)x (b1m r2)y = (a1

4、x b1y)m r1x r2y 可知，若r1x r2y被m除的余数是r，即 r1x r2y = qm r，0 r m， 则 ax by = (a1x b1y q)m r，0 r m， 即ax by被m除的余数也是r。,第二节 带余数除法,同样方法可以证明其余结论。,例2 设a1, a2, , an为不全为零的整数,以y0表示集合 A = y；y = a1x1 anxn，xiZ，1 i n 中的最小正数，则对于任何yA，y0y；特别地，y0ai，1 i n。,第二节 带余数除法,解 设y0 = a1x1 anxn，对任意的y = a1x1 anxnA，由定理1，存在q, r0Z，使得 y = q

5、y0 r0，0 r0 y0 。 因此 r0=yqy0 = a1(x1 qx1) an(xn qxn)A。 如果r0 0，那么，因为0 r0 y0，所以r0是A中比y0还小的正数，这与y0的定义矛盾。所以r0 = 0，即y0y。,第二节 带余数除法,显然aiA（1 i n），所以y0整除每个ai（1 i n）。,例3 任意给出的五个整数中，必有三个数之和被3整除。,解 设这五个数是ai，i = 1, 2, 3, 4, 5，记 ai = 3qi ri，0 ri 3，i = 1, 2, 3, 4, 5。 分别考虑以下两种情形：,第二节 带余数除法,() 若在r1, r2, , r5中数0，1，2都出

6、现，不妨设r1 = 0，r2 = 1，r3 = 2，此时 a1 a2 a3 = 3(q1 q2 q3) 3 可以被3整除；,() 若在r1, r2, , r5中数0，1，2至少有一个不出现，这样至少有三个ri要取相同的值，不妨设r1 = r2 = r3 = r（r = 0，1或2），此时 a1 a2 a3 = 3(q1 q2 q3) 3r 可以被3整除。,第二节 带余数除法,例4 设a0, a1, , anZ，f(x) = anxn a1x a0 ，已知f(0)与f(1)都不是3的倍数，证明：若方程f(x) = 0有整数解，则 3f(1) = a0 a1 a2 (1)nan 。,解 对任何整数

7、x，都有 x = 3q r，r = 0，1或2，qZ。,第二节 带余数除法,() 若r = 0，即x = 3q，qZ，则 f(x) = f(3q) = an(3q)n a1(3q) a0 = 3Q1 a0 = 3Q1 f(0)， 其中Q1Z,由于f(0)不是3的倍数, 所以f(x) 0；,() 若r = 1，即x = 3q 1，qZ，则 f(x)=f(3q 1) = an(3q 1)n a1(3q 1) a0 = 3Q2 an a1 a0 = 3Q2 f(1)， 其中Q2Z。由于f(1)不是3的倍数， 所以f(x) 0。,第二节 带余数除法,因此若f(x) = 0有整数解x，则必是x = 3q

8、 2 = 3q 1，q Z，于是 0 = f(x) = f(3q 1) = an(3q 1)n a1(3q 1) a0 = 3Q3 a0 a1 a2 ( 1)nan = 3Q3 f(1)， 其中Q3Z。所以3f(1) = a0 a1 a2 (1)nan 。,第二节 带余数除法,例5 证明：对于任意的整数n， f(n) = 3n5 5n3 7n被15整除。,解 对于任意的正整数n，记 n = 15q r，0 r 15。 由例1， n2 = 15Q1 r1，n4 = 15Q2 r2， 其中r1与r2分别是r2与r4被15除的余数。,第二节 带余数除法,以R表示3n4 5n2 7被15除的余数，则R

9、就是3r2 5r1 7被15除的余数，而且f(n)被15除的余数就是rR被15除的余数，记为R 。 当r = 0时，显然R = 0，即153n5 5n3 7n。 对于r = 1, 2, 3, , 14的情形，通过计算列出下表：,第二节 带余数除法,r = 1, 14 2, 13 3, 12 4, 11 5, 10 6, 9 7, 8 r1 = 1 4 9 1 10 6 4 r2 = 1 1 6 1 10 6 1 R = 0 0 10 0 12 10 0 R= 0 0 0 0 0 0 0 这证明了结论。,第二节 带余数除法,例6 设n是奇数，则16n4 4n2 11。,解 我们有 n4 4n2

10、11 = (n2 1)(n2 5) 16。 由第一节例题9，有8n2 1，由此及2n2 5 得到16(n2 1)(n2 5)。,第二节 带余数除法,例7 证明：若a被9除的余数是3，4，5或6，则方程x3 y3 = a没有整数解。,解 对任意的整数x，y，记 x = 3q1 r1，y = 3q2 r2，0 r1, r2 3。 则存在Q1, R1, Q2, R2Z，使得 x3 = 9Q1 R1，y3 = 9Q2 R2 ，,第二节 带余数除法,其中R1和R2被9除的余数分别与r13和r23被9除的余数相同，即 R1 = 0，1或8，R2 = 0，1或8。 (4) 因此 x3 y3 = 9(Q1 Q2) R1 R2 。 又由式(4)可知，R1 R2被9除的余数只可能是0，1，2，7或8，所以，x3 y3不可能等于a 。,习 题 二,1. 证明：12n4 2n3 11n2 10n，nZ。 2.