第一章整数的可除性 整除是数论中的基本概念，本章从这个概念出发，引进带余数 除法及辗转相除法，然后利用这两个工具，建立最大公因数与最小 公倍数的理论，进一步证明极具重要性的算术基本定理这一切都 是整个课程中最基本的部分，以后时常要用到同时，它们也是整 个数学的基础知识，大部分都是读者在小学甚至在幼儿园时就开 始学习的由于当时考虑到儿童的理解力，着重点是具体数字的计 算和运用因此对绝大多数读者来说，可能计算技能是熟练的，对 计算方法和概念未必能从一般的角度来掌握，从而对它们的本质 未必理解因此在大学甚至高中阶段，重新学习和体会是大有裨益 的此外，本章还要介绍[x],{x}这两个极有用的记号，并利用 [x]来说明如何把n!表示成质数幂的乘积」 §1整除的概念·带余数除法 我们知道两个整数的和、差、积仍然是整数，但是用一不等于 零的整数去除另一个整数所得的商却不一定是整数，因此我们引 进整除的概念 定义设4，b是任意两个整数，其中b≠0，如果存在一个整 数g使得等式 a=bg (1) 成立，我们就说b整除a或a被b整除，记作b1a,此时我们把b 叫作a的因数，把a叫作b的倍数 如果(I)里的整数q不存在，我们就说b不能整除a或a不 被b整除，记作8a. ·1·
第一章 整数的可除性 整除是数论中的基本概念,本章从这个概念出发, 引进带余数 除法及辗转相除法,然后利用这两个工具, 建立最大公因数与最小 公倍数的理论,进一步证明极具重要性的算术基本定理 .这一切都 是整个课程中最基本的部分, 以后时常要用到 .同时, 它们也是整 个数学的基础知识,大部分都是读者在小学甚至在幼儿园时就开 始学习的 .由于当时考虑到儿童的理解力, 着重点是具体数字的计 算和运用 .因此对绝大多数读者来说, 可能计算技能是熟练的, 对 计算方法和概念未必能从一般的角度来掌握, 从而对它们的本质 未必理解 .因此在大学甚至高中阶段, 重新学习和体会是大有裨益 的 .此外, 本章还要介绍 [ x ] , { x} 这两个极有用的 记号, 并利用 [ x ] 来说明如何把 n ! 表示成质数幂的乘积 . §1 整除的概念·带余数除法 我们知道两个整数的和、差、积仍然是整数, 但是用一不等于 零的整数去除另一个整数所得的商却不一定是整数, 因此我们引 进整除的概念: 定义 设 a, b 是任意两个整数, 其中 b≠0, 如果存在一个整 数 q 使得等式 a = bq ( 1) 成立,我们就说 b 整除 a 或 a 被 b 整除, 记作 b | a, 此时我们把 b 叫作 a 的因数,把 a 叫作 b 的倍数 . 如果(1 ) 里的整数 q 不存在, 我们就说 b 不能整除 a 或 a 不 被 b 整除,记作 b8 a . · 1 ·
整除这个概念虽然简单，但却是数论中的基本概念，我们很容 易从定义出发，证明下面那些关于可除性的基本定理 定理1（传递性）若a是b的倍数，b是c的倍数，则a是c 的倍数，也就是① bla,cb cla 证b1a,cb就是说存在两个整数a,使得 a=ab,b=b c 成立，因此 a=(ab)c, 但ab是一个整数，故cla. 证完 定理2若a,b都是m的倍数，则a士b也是m的倍数 证a,b是m的倍数的意义就是存在两个整数a,b,使得 a=a m,b=b m. 因此 a±b=(a±b)m 但a±b是整数，故a±b是m的倍数. 证完 用同样的方法，可以证明 定理3若a,2,.,a都是m的倍数，g,.,gn是任 意n个整数，则ga++.+g.a是m的倍数（证明留给读 者) 上面我们仅就能够整除的情形初步地讨论了一下，至于在一 般（即未必能整除的）情形下，我们有下面基本而重要的定理· 定理4（带余数除法）若a,b是两个整数，其中b>0,则存 在着两个整数9及r,使得 a=bg+r,0≤r<b (2) 成立，而且g及r是惟一的 ①我们用AB表示由命题A可以推出命题B ·2·
整除这个概念虽然简单,但却是数论中的基本概念, 我们很容 易从定义出发,证明下面那些关于可除性的基本定理 . 定理 1(传递性 ) 若 a 是 b 的倍数, b 是 c 的倍数, 则 a 是 c 的倍数,也就是① b | a, c| b c| a . 证 b| a, c| b 就是说存在两个整数 a1 , b1 使得 a = a1 b, b = b1 c 成立,因此 a = ( a1 b1 ) c, 但 a1 b1 是一个整数, 故 c| a . 证完 定理 2 若 a, b 都是 m 的倍数, 则 a± b 也是 m 的倍数 . 证 a, b 是 m 的倍数的意义就是存在两个整数 a1 , b1 ,使得 a = a1 m , b = b1 m . 因此 a± b = ( a1± b1 ) m , 但 a1± b1 是整数, 故 a± b 是 m 的倍数 . 证完 用同样的方法,可以证明 定理 3 若 a1 , a2 , ., an 都是 m 的倍数, q1 , q2 , ., qn 是任 意 n 个整数, 则 q1 a1 + q2 a2 + . + qn an 是 m 的倍数 .( 证明留给读 者 .) 上面我们仅就能够整除的情形初步地讨论了一下, 至于在一 般(即未必能整除的) 情形下,我们有下面基本而重要的定理 . 定理 4(带余数除法 ) 若 a, b 是两个整数, 其中 b > 0, 则存 在着两个整数 q 及 r,使得 a = bq + r,0≤ r < b ( 2) 成立,而且 q 及 r 是惟一的 . · 2 · ① 我 们用 A B 表示 由命题 A 可 以推出 命题 B
证作整数序列 .,-3b,-2b,-b,0,b,2b,3b,. 则α必在上述序列的某两项之间，即存在一个整数q使得 qb≤a<(q+1)b 成立令a-qb=r,则a=bg+r,而0≤r<b 下面我们证明q,r的惟一性：设，n是满足(2)的两个整 数，则 a=bg+n,0≤n<b, 因而 bg +n=bq+r, 于是 b(q-q)=n-r, 故 blq-gl=In-rl. 由于r及都是小于b的正数，所以上式右边是小于b的如果 q≠q:则上式左边≥b这是不可能的.因此q=q而r=n.证完 整数的很多基本性质，都可以从定理4引导出来我们可以说 这一章最主要的部分是建立在定理4的基础上的. 定义(2)中的q叫做a被b除所得的不完全商，r叫作a被 b除所得到的余数. 为了更好地了解这个定义，我们举例说明如下 例设b=15,则当a=255时 a=17b+0,r=0<15,而q=17; 当a=417时， a=27b+12,0<r=12<15,而q=27; 当a=-81时， a=-6b+9,0<r=9<15,而q=-6 习题 1.证明定理3 ·3·
证 作整数序列 ., - 3 b, - 2 b, - b, 0, b, 2 b, 3 b, . 则 a 必在上述序列的某两项之间, 即存在一个整数 q 使得 qb≤ a < ( q + 1) b 成立 .令 a - qb = r, 则 a = bq + r,而 0≤ r < b . 下面我们证明 q, r 的惟一性: 设 q1 , r1 是满足 ( 2 ) 的两个整 数,则 a = bq1 + r1 , 0≤ r1 < b, 因而 bq1 + r1 = bq + r, 于是 b( q - q1 ) = r1 - r, 故 b | q - q1 | = | r1 - r| . 由于 r 及 r1 都是小于 b 的正数, 所以上式右边是小于 b 的 .如果 q≠ q1 则上式左边≥ b .这是不可能的 .因此 q = q1 而 r = r1 .证完 整数的很多基本性质,都可以从定理 4 引导出来 .我们可以说 这一章最主要的部分是建立在定理 4 的基础上的 . 定义 (2 )中的 q 叫做 a 被 b 除所得的不完全商, r 叫作 a 被 b 除所得到的余数 . 为了更好地了解这个定义,我们举例说明如下: 例 设 b = 15,则当 a = 255 时 a = 17 b + 0, r = 0 < 15, 而 q = 17; 当 a = 417 时, a = 27 b + 12, 0 < r = 12 < 15, 而 q = 27; 当 a = - 81 时, a = - 6 b + 9, 0 < r = 9 < 15 ,而 q = - 6 . 习 题 1. 证明定理 3 . · 3 ·
2.证明3引n(n+1)(2n+1),其中n是任何整数 3.若a。+b是形如ax+bx,y)是任意整数，a,b是两个不全为零 的整数)的数中的最小正数，则 (a0+b)川(ax+by), 其中x,y是任何整数 4.若a,b是任意二整数，且b≠0，证明：存在两个整数s,1使得 a=临+1,1≤9 成立，并且当b是奇数时，s,1是惟一存在的当b是偶数时结果如何？ §2最大公因数与辗转相除法 有了带余数除法，我们就可以着手研究整数的最大公因数的 存在问题及其实际求法，在研究过程中，我们要用到基本而重要的 辗转相除法 定义设a,2,.,an是n(n≥2)个整数若整数d是它们 之中每一个的因数，那么d就叫作a,a,.,a,的一个公因数. 整数a,a2,.,a的公因数中最大的一个叫作最大公因数， 记作(a,c,.,a),若(a,.,a)=1,我们说a,.,a 互质或互素，若a,6,.,a。中每两个整数互质，我们就说它们两 两互质 显然，若整数a,&,.,a两两互质，则(a,a,.,a)=1, 反过来却不一定成立（很容易举出反例），且若a,.,a。不全 为零，则(a,a,.,a)是存在的. 为了讨论时免去区别正负整数的麻烦，我们先证明 定理1若a,a,.,an是任意n个不全为零的整数，则 ()a,a,.,a与|al,|al,.,a的公因数相同； (ii)(a,.,an)=(al,|a2l,.,lanl). 证设d是a,&,.,a.的任一公因数由定义da,i=1, ·4·
2. 证明 3 | n( n + 1) ( 2 n + 1) ,其中 n 是任何整数 . 3. 若 ax0 + by0 是形如 ax + by( x , y ) 是任意整数 , a, b 是两个不全为零 的整数) 的数中的最小正数 , 则 ( ax0 + by0 ) | ( ax + by ) , 其中 x , y 是任何整数 . 4. 若 a, b 是任意二整数 ,且 b≠0, 证明 :存在两个整数 s, t 使得 a = bs + t , | t |≤ | b | 2 成立 ,并且当 b 是奇数时 , s, t 是惟一存在的 .当 b 是偶数时结果如何 ? §2 最大公因数与辗转相除法 有了带余数除法,我们就可以着手研究整数的最大公因数的 存在问题及其实际求法,在研究过程中, 我们要用到基本而重要的 辗转相除法 . 定义 设 a1 , a2 ,., an 是 n ( n≥2 )个整数 .若整数 d 是它们 之中每一个的因数,那么 d 就叫作 a1 , a2 ,., an 的一个公因数 . 整数 a1 , a2 ,., an 的公因数中最大的一个叫作最大公因数, 记作( a1 , a2 , ., an ) , 若 ( a1 , a2 , ., an ) = 1, 我们说 a1 , a2 , ., an 互质或互素,若 a1 , a2 , ., an 中每两个整数互质,我们就说它们两 两互质 . 显然,若整数 a1 , a2 , ., an 两两互质, 则 ( a1 , a2 , ., an ) = 1, 反过来却不一定成立 (很容易举出反例) , 且若 a1 , a2 , ., an 不全 为零,则( a1 , a2 ,., an )是存在的 . 为了讨论时免去区别正负整数的麻烦,我们先证明 定理 1 若 a1 , a2 ,., an 是任意 n 个不全为零的整数, 则 (i) a1 , a2 ,., an 与 | a1 | , | a2 | ,., | an | 的公因数相同; (ii) ( a1 , a2 , ., an ) = ( | a1 | , | a2 | , ., | an | ) . 证 设 d 是 a1 , a2 , ., an 的任一公因数 .由定义 d | ai , i = 1, · 4 ·
2,.,n,因而d|a,i=1,2,.,n,故d是|al,|a|,.,|al 的一个公因数，同法可证，1al,1a1,.,1a1的任一个公因数都 是a,.,an的一个公因数故a,a,.,a,与|al,|al,., 1a有相同的公因数，即()获证由（①）立得() 证完 定理1的()告诉我们，要讨论最大公因数不妨仅就非负整数 去讨论，下面我们首先看两个非负整数的情形 定理2若b是任一正整数，则()0与b的公因数就是b的 因数，反之，b的因数也就是0与b的公因数(i)(0,b)=b. 证显然0与b的公因数是b的因数.由于任何非零整数都 是0的因数，故b的因数也就是0，b的公因数，于是()获证，其 次，我们立刻知道b的最大因数是b:而0，b的最大公因数是b的 最大因数，故(0，b)=b 证完 由定理1,2立刻得到0 推论2.1若b是任一非零整数，则(0，b)=1b川 定理3设a,b,c是任意三个不全为0的整数，且 a=bg+c, 其中g是非零整数，则a,b与b,c有相同的公因数，因而(a,b) =(b,c) 证设d是a,b的任一公因数，由定义，da,d川b.由§1定 理3，d是c=a+(-q)b的因数，因而d是b,c的一个公因数 同法可证，b,c的任一公因数是a,b的一个公因数于是定理的前 一部分获证第二部分显然随之成立 证完 现在我们介绍一下辗转相除法它有很多应用：可用以求出两 个正整数的最大公因数：借此推出最大公因数的重要性质；还是解 一次不定方程的基本工具 设a,b是任意两个正整数，由带余数除法，我们有下面的系 ①我们用推论2.1表示定理2的推论1 ·5·
2, ., n, 因而 d | | ai | , i = 1, 2 , ., n, 故 d 是 | a1 | , | a2 | , ., | an | 的一个公因数,同法可证, | a1 | , | a2 | , ., | an | 的任一个公因数都 是 a1 , a2 ,., an 的一个公因数 .故 a1 , a2 ,., an 与 | a1 | , | a2 | , ., | an | 有相同的公因数,即(i)获证 .由 (i)立得 (ii) . 证完 定理 1 的(ii) 告诉我们,要讨论最大公因数不妨仅就非负整数 去讨论,下面我们首先看两个非负整数的情形 . 定理 2 若 b 是任一正整数, 则 (i)0 与 b 的公因数就是 b 的 因数,反之, b 的因数也就是 0 与 b 的公因数 .(ii) ( 0, b) = b . 证 显然 0 与 b 的公因数是 b 的因数 .由于任何非零整数都 是 0 的因数, 故 b 的因数也就是 0, b 的公因数, 于是 ( i) 获证 .其 次,我们立刻知道 b 的最大因数是 b; 而 0, b 的最大公因数是 b 的 最大因数,故( 0, b) = b . 证完 由定理 1, 2 立刻得到① 推论 2.1 若 b 是任一非零整数,则 (0, b) = | b | . 定理 3 设 a, b, c 是任意三个不全为 0 的整数,且 a = bq + c, 其中 q 是非零整数, 则 a, b 与 b, c 有相同的公因数, 因而 ( a, b) = ( b, c) . 证 设 d 是 a, b 的任一公因数,由定义, d | a, d | b .由§1 定 理 3, d 是 c = a + ( - q) b 的因数, 因而 d 是 b, c 的一个公因数 . 同法可证, b, c 的任一公因数是 a, b 的一个公因数 .于是定理的前 一部分获证 .第二部分显然随之成立 . 证完 现在我们介绍一下辗转相除法 .它有很多应用: 可用以求出两 个正整数的最大公因数;借此推出最大公因数的重要性质; 还是解 一次不定方程的基本工具 . 设 a, b 是任意两个正整数, 由带余数除法, 我们有下面的系 · 5 · ① 我 们用推 论 2.1 表示 定理 2 的推论 1