离散数学教程-王元元-第4章 初等数论.pptVIP

离散数学 第4章 初等数论 第10章 特殊图 4.1.1 整除 定义4.1 设a,b是整数，a ? 0，如果存在整数c，使得b=a*c 成立（这里 *为数乘运算，下同。我们也会像初等数学学习时那样，很多时候 省略乘运算符号），则称a整除b，或b可被a整除，使用记号a?b表 示之。这时又称b是a的倍数，a是b的因子（约数、因数或除数）。 如果不存在整数c使得b=ac成立，则称a不整除b， b不可被a整除， 记为?a?b。 例4.1 8 | 48，?13 | 200，23 | 0 9 | ?54，?(5 | 4)，?(?3 | ?14) 例4.2 6的因子有?1，?2，?3和?6，13的因子只有?1和?13。 4.1.1 整除 定义4.2 若整数a ? 0，a ??1，并且除平凡因子 ?1和 ?a外没有其他 因子，则称a是素数（或质数）；否则称a为合数。 素数在数论中有着极其重要的地位。以后若无特别说明，素数 总是指正素数。2是第一个素数，其后还有3，5，7，11，?等等， 对它们我们还要做更深入的讨论。 4.1.1 整除 定理4.1 a，b，c是整数，则有： （1）a?b 当且仅当 ?a??b； （2）若a?b，b?c ，则 a?c； （3）若b?ai，i = 1,2,???,k,则 b?a1x1?a2x2?????akxk，此处xi(i = 1,2,???,k) 是任意的整数； （4）若b?a ，则 bc?ac，此处c是任意的非零整数； （5）若b?a，a ?0则 |b| ? |a|； （6）若b?a且|a| |b|，则 a = 0。 4.1.1 整除 证 (3) 因为b?ai，故存在整数ci使得ai=bci , i=1,2,???,k，则， a1x1?a2x2?????akxk=bc1x1?bc2x2?????bckxk=b(c1x1?c2x2?????ckxk) 其中c1x1?c2x2?????ckxk是整数。因此，b?a1x1?a2x2?????akxk。 (5) 因为b?a，a ?0，故有整数c ?0 ，使得a=bc；从而 |a|=|b||c|，又由|c|≥1，故|b|?|a|。 (6) 若b?a且|a||b|，故有整数c?0 ，使得a=bc，从而|a|=|b||c|。 由于|a||b|，可知|c|=0，故c=0，从而a=0。 4.1.1 整除 整除的定义和性质很简单，但却是数论的基础，有广泛的应用， 且其应用往往具有很强的趣味性和技巧性。 例4.3 求证：若n是奇数，则8?(n2 ? 1)。 解 设n = 2k ? 1，k是整数，则 n2 ? 1= (2k ? 1)2 ? 1 = 4k(k ? 1)。 由于在k和k ? 1中必有一个是偶数，所以8?n2 ? 1。 4.1.1 整除 例4.4 证明：下列方程无整数解：x12?x22?x32 = 1999 解 若x1 , x2 , x3都是奇数，据例4.3，存在整数A1, A2, A3, 使得 x12 = 8A1 ? 1， x22 = 8A2 ? 1， x32 = 8A3 ? 1， x12 ? x22 ? x32 = 8(A1 ? A2 ? A3) ? 3， 它被8除的余数是3，而1999被8除的余数是7。 故x1，x2，x3不可能都是奇数。 4.1.1 整除 例4.4 证明：下列方程无整数解：x12?x22?x32 = 1999 解(续)另，由式x12?x22?x32 =1999，知x1,x2,x3中只能有且仅有一个 奇数。设x1为奇数，x2，x3为偶数，则存在整数A1，A2，A3，使 得 x12=8A1?1，x22=8A2?r，x32=8A3?s，其中r和s是整数，而且 只能取值0或4（因为x22，x32是4的倍数）。 于是 x12?x22?x32 = 8(A1?A2?A3)?1?r?s， 这样x12?x22?x32 被8除的余数只可能是1或5，但1999被8除的余 数是7，因此这样的x1，x2，x3也不