01整除理论(编辑修改稿)

01整除理论(编辑修改稿)内容摘要：

设 d 是 a与 bc的一个公约数，则 da， dbc， 由 式 （ 2）得到 ， d|c, 即 d是 a与 c 的 公约数。 另一方面， 若 d 是 a 与 c 的 公约数， 则 它 也 是 a与 bc的 公约数。 因此， a与 c的 公约数 的 集合， 就是a与 bc的 公约数 的 集合 ， 所以 (a, bc) = (a, c)。 证毕。 推论 3 若 (a, bi) = 1， 1  i  n，则 (a, b1b2 bn) = 1。 证明 留作习题。 定理 5 对于任意的 n个整数 a1, a2,  , an，记 (a1, a2) = d2， (d2, a3) = d3，  ， (dn  2, an  1) = dn  1， (dn  1, an) = dn， 则 dn = (a1, a2,  , an)。 证明 由定理 2的推论，我们有 dn = (dn  1, an)  dnan， dndn  1， dn  1 = (dn  2, an  1)  dn  1an  1， dn  1dn  2，  dnan， dnan  1， dndn  2， dn  2 = (dn  3, an  2)  dn  2an  2， dn  2dn  3  dnan， dnan  1， dnan  2， dndn  3，   d2 = (a1, a2)  dnan， dnan  1，  ， dna2， dna1， 即 dn是 a1, a2,  , an的一个公约数。 另一方面，对于 a1, a2,  , an的任何公约数 d，由定理 2的推论及 13 d2,  , dn的定义，依次得出 da1， da2  dd2， dd2， da3  dd3，   ddn  1， dan  ddn， 因此 dn是 a1, a2,  , an的公约数中的最大者，即 dn = (a1, a2,  , an)。 证毕。 例 1 证明：若 n是正整数，则 314 421nn 是既约分数。 解 由定 理 1得到 (21n  4, 14n  3) = (7n  1, 14n  3) = (7n  1, 1) = 1。 注 ：一般地，若 (x, y) = 1，那么，对于任意的整数 a， b，有 (x, y) = (x ay, y) = (x ay, y  b(x ay)) = (x ay, (ab  1)y  bx)， 因此，bxyab ayx )1(是既约分数。 例 2 证明： 121| n2  2n  12， nZ。 解 由 于 121 = 112， n2  2n  12 = (n  1)2  11，所以，若 112(n  1)2  11， (3) 则 11(n  1)2，因此，由定理 4的推论 1得到 11n  1， 112(n  1)2。 再由式 (3)得到 11211， 这是不可能的。 所以式 (3)不能成立。 注 ：这个例题的一般形式是： 设 p是素数， a， b是整数，则 pk | (an  b)k  pk  1c， 其中 c是不被 p整 除的任意整数 ， k是任意的大于 1的整数。 例 3 设 a， b是整数，且 9a2  ab  b2， (4) 则 3(a, b)。 解 由式 (4)得到 9(a  b)2  3ab  3(a  b)2  3ab 14  3(a  b)2  3a  b (5)  9(a  b)2。 再由式 (4)得到 93ab  3ab。 因此，由定理 4的推论 1，得到 3a或 3b。 若 3a，由式 (5)得到 3b；若 3b，由 (5)式也得到 3a。 因此，总有 3a且 3b。 由定理 2的推论推出 3(a, b)。 例 4 设 a和 b是正整数， b 2，则 2b  1| 2a  1。 解 (ⅰ ) 若 a b，且 2b  12a  1。 (6) 成立，则 2b  1  2a  1  2b  2a  2  2a(2b  a  1)  2， 于是 a = 1， b  a = 1，即 b = 2，这是不可能的，所以式 (6)不成立。 (ⅱ ) 若 a = b，且式 (6)成立，则由式 (6)得到 2a  1(2a  1)  2  2a  12  2a  1  2  2a  3， 于是 b = a = 1，这是不可能的，所以式 (6)不成立。 (ⅲ ) 若 a b，记 a = kb  r， 0  r b，此时 2kb  1 = (2b  1)(2(k  1)b  2(k  2)b    1) = (2b  1)Q， 其中 Q是整数。 所以 2a  1 = 2kb + r  1 = 2r(2kb  1  1)  1 = 2r((2b  1)Q  1)  1 = (2b  1)Q   (2r  1)， 其中 Q是整数。 因此 2b  12a  1  2b  12r  1， 在 (ⅰ )中已经证明这是不可能的 ， 所以式 (6)不能成立。 综上证得 2b  1| 2a  1。 习 题 三 1. 证明定理 1中的结论 (ⅰ )— (ⅳ )。 2. 证明定理 2的推论 1, 推论 2和 推论 3。 15 3. 证明定理 4的推论 1和推论 3。 4. 设 x， yZ， 172x  3y，证明： 179x  5y。 5. 设 a， b， cN， c无平方因子， a2b2c，证明： ab。 6. 设 n是正整数，求 1223212 C,C,C nnnn  的最大公约数。 第四节 最小公倍数 定义 1 整数 a1, a2,  , ak的公共倍数称为 a1, a2,  , ak的公倍数。 a1, a2,  , ak的正公倍数中的最小的一个叫做 a1, a2,  , ak的最小公倍数，记为 [a1, a2,  , ak]。 定理 1 下面的等式成立： (ⅰ ) [a, 1] = |a|， [a, a] = |a|； (ⅱ ) [a, b] = [b, a]； (ⅲ ) [a1, a2,  , ak] = [|a1|, |a2|  , |ak|]； (ⅳ ) 若 ab，则 [a, b] = |b|。 证明 留作习题。 由定理 1中的结论 (ⅲ )可知，在讨论 a1, a2,  , ak的最小公倍数时，不妨假定它们都是正整数。 在本节中总是维持这一假定。 最小公倍数和最大公约数之间有一个很重要的关系，即下面的定理。 定理 2 对任意的正整数 a， b，有 [a, b] =),( baab。 证明 设 m是 a和 b 的一个公倍数，那么存在整数 k1， k2，使得m = ak1， m = bk2，因此 ak1 = bk2。 (1) 于是 21 ),(),( kbabkbaa 。 由于 )(),(,),( babbaa= 1，所以由第三节定理 4得到 16 tbabkkbab ),(),( 11| 即， ， 其中 t是某个整数。 将上式代入式 (1)得到 m =),( baabt。 (2) 另一方面，对于任意的整数 t，由式 (2)所确定的 m 显然是 a 与 b的公倍数，因此 a 与 b的公倍数必是式 (2)中的形式，其中 t是整数。 当 t = 1时，得到最小公倍数 [a, b] =),( baab。 证毕。 推论 1 两个整数的任何公倍数可以被它们的最小公倍数整除。 证明 由式 (2)可得证。 证毕。 这个推论说明：两个整数的最小公倍数不但是最小的正倍数，而且是另外的公倍数的约数。 推论 2 设 m， a， b是正整数，则 [ma, mb] = m[a, b]。 证明 由定理 2及第三节 定理 2的推论得到 [ma, mb] =),(),(),( 22 bam abbam abmmbma abm = m[a, b]。 证毕。 定理 3 对于任意的 n个整数 a1, a2,  , an，记 [a1, a2] = m2， [m2, a3] = m3，  ， [mn2, an1] = mn1， [mn1, an] = mn， 则 [a1, a2,  , an] = mn。 证明 我们有 mn = [mn1, an]  mn1mn， anmn， mn1 = [mn2, an1]  mn2mn1mn， anmn， an1mn1mn， mn2 = [mn3, an2]  mn3mn2mn， anmn， an1mn， an2mn，   m2 = [a1, a2]  anmn，  ， a2mn， a1mn， 即 mn是 a1, a2,  , an的一个公倍数。 另一方面，对于 a1, a2,  , an的任何公倍数 m，由定理 2的推论及 17 m2,  , mn的定义，得 m2m， m3m，  ， mnm。 即 mn是 a1, a2,  , an最小的正的公倍数。 证毕。 推论 若 m是整 数 a1, a2,  , an的公倍数，则 [a1, a2,  , an]m。 证明 留作习题。 定理 4 整数 a1, a2,  , an两两互素，即 (ai, aj) = 1， 1  i, j  n， i  j 的充要条件是 [a1, a2,  , an] = a1a2 an。 (3) 证明 必要性 因为 (a1, a2) = 1，由定理 2得到 [a1, a2] =),( 21 21aa aa= a1a2。 由 (a1, a3) = (a2, a3) = 1及第三节定理 4推论 3得到 (a1a2, a3) = 1， 由此及定理 3得到 [a1, a2, a3] = [[a1, a2], a3] = [a1a2, a3] = a1a2a3。 如此继续下去，就得到式 (3)。 充分性 用归纳法证明。 当 n = 2时，式 (3)成为 [a1, a2] = a1a2。 由定理 2 a1a2 = [a1, a2] =),( 21 21aa aa (a1, a2) = 1， 即当 n = 2时，充分性成立。 假设充分性当 n = k时成立，即 [a1, a2,  , ak] = a1a2 ak  (ai, aj) = 1， 1  i, j  k， i  j。 对于整数 a1, a2,  , ak, ak + 1，使用定理 3中的记号，由定理 3可知 [a1, a2,  , ak, ak + 1] = [mk, ak + 1]。 (4) 其中 mk = [a1, a2,  , ak]。 因此，如果 [a1, a2,  , ak, ak + 1] = a1a2 akak + 1， 那么，由此及式 (4)得到 [a1, a2,  , ak, ak + 1] = [mk, ak + 1] =),( 11kk kk am am= a1a2 akak + 1， 18 即 ),( 1kk kamm= a1a2 ak ， 显然 mk  a1a2 ak， (mk, ak + 1)  1。 所以若使上式成立，必是 (mk, ak + 1) = 1， (5) 并且 mk = a1a2 ak。 (6) 由式 (6)与式 (5)推出 (ai, ak + 1) = 1， 1  i  k； (7) 由式 (6)及归纳假设推出 (ai, aj) = 1， 1  i, j  k， i  j。 (8) 综合式 (7)与式 (8)，可知当 n = k  1时，充分性成立。 由归纳法证明了充分性。 证毕。 定理 4有许多应用。 例如，如果 m1, m2,  , mk是两两互素的整数，那么，要证明 m = m1m2 mk整除某个整数 Q，只。