第四讲数论的方法技巧之二高等教育科普读物高等教育专业基础教材.pdf
第四讲 数论的方法技巧之二 第四讲 数论的方法技巧之二 四、反证法 反证法即首先对命题的结论作出相反的假设，并从此 假设出发，经过正确的推理，导出矛盾的结果，这就否定 了作为推理出发点的假设，从而肯定了原结论是正确的。反证法的过程可简述为以下三个步骤：1 反设：假设所要证明的结论不成立，而其反面成立；2.归谬：由“反设”出发，通过正确的推理，导出矛 盾一一与已知条件、公理、定义、定理、反设及明显的事 实矛盾或自相矛盾；3.结论：因为推理正确，产生矛盾的原因在于“反设”的谬误，既然结论的反面不成立，从而肯定了结论成立。运用反证法的关键在于导致矛盾。在数论中，不少问 题是通过奇偶分析或同余等方法引出矛盾的。例 1 是否存在三位数 abc,使得凯 be 二 ab+bc+ac?解：如果存在这样的三位数，那么就有 100a+10b+c=(10a+b)+(10b+c)+(10a+c)。上式 可化简为 80a=b+c，而这显然是不可能的，因为 a 1,b w 9,c 9。这表明所找的数是不存在的。说明：在证明不存在性的问题时，常用反证法：先假 设存在，即至少有一个元素，它符合命题中所述的一切要 求，然后从这个存在的元素出发，进行推理，直到产生矛 盾。例 2 将某个 17 位数的数字的排列顺序颠倒，再将得到 的数与原来的数相加。试说明，得到的和中至少有一个数 字是偶数。解：假设得到的和中没有一个数字是偶数，即全是奇 数。在如下式所示的加法算式中，末一列数字的和 d+a 为 奇数，从而第一列也是如此，因此第二列数字的和 b+cw 9 999。另一方面，可以通过构造三元数组来证明 30 是最少的 个数。(2,61,2X 61),(3,60,3X 60),(4,59,4 X 59),，(30,33,30X 33),(31,32,31 X32)。上面写出的这些数都是互不相同的，并且这些数中的 最大数为 31 X 32=992。如果划去的数少于 30 个，那么上 述三元数组至少剩下一个，这样就不满足题设条件。所以，30 是最少的个数。六、配对法 配对的形式是多样的，有数字的凑整配对，也有集合 间元素与元素的配对(可用于计数)。传说高斯 8 岁时求 和(1+2+100)首创了配对。像高斯那样，善于使用配 对技巧，常常能使一些表面上看来很麻烦，甚至很棘手的 问题迎刃而解。此假设出发经过正确的推理导出矛盾的结果这就否定了作为推理出发点的假设从而肯定了原结论是正确的反证法的过程可简述为以下三个步骤反设假设所要证明的结论不成立而其反面成立归谬由反设出发通过正确的推理导出矛盾一既然结论的反面不成立从而肯定了结论成立运用反证法的关键在于导致矛盾在数论中不少问题是通过奇偶分析或同余等方法引出矛盾的例是否存在三位数使得凯二解如果存在这样的三位数么就有上式可化简为而这显然是不可能的因中所述的一切要求然后从这个存在的元素出发进行推理直到产生矛盾例将某个位数的数字的排列顺序颠倒再将得到的数与原来的数相加试说明得到的和中至少有一个数字是偶数解假设得到的和中没有一个数字是偶数即全是奇数在如 例 7 求 1,2,3，9999998,9999999 这 9999999 个数中所有数码的和。解：在这些数前面添一个数 0,并不影响所有数码的和。将这 1000 万个数两两配对，因为 0 与 9999999，1 与 9999 998,，4999999 与 5000000 各对的数码和都是 9X 7=63。这里共有 5000000 对，故所有数码的和是 63 X 5000000=31 5000000。例 8 某商场向顾客发放 9999 张购物券，每张购物券上 印有一个四位数的号码，从 0001 到 9999 号。若号码的前 两位数字之和等于后两位数字之和，则称这张购物券为“幸 运券”。例如号码 0734，因 0+7=3+4，所以这个号码的购 物券是幸运券。试说明，这个商场所发的购物券中，所有 幸运券的号码之和能被 101 整除。解：显然，号码为 9999 的是幸运券，除这张幸运券外，如果某个号码 n 是幸运券，那么号码为 m=9999-n 的购物券 也是幸运券。由于 9999 是奇数，所以 n。由于 m+n=9999 相加时不出现进位，所以除去号码是 9999 这张幸运券之外，其余所有幸运券可全部两两配对，而每一对两个号码之和均为 9999，即所有幸运券号码之和 是 9999的倍数。此假设出发经过正确的推理导出矛盾的结果这就否定了作为推理出发点的假设从而肯定了原结论是正确的反证法的过程可简述为以下三个步骤反设假设所要证明的结论不成立而其反面成立归谬由反设出发通过正确的推理导出矛盾一既然结论的反面不成立从而肯定了结论成立运用反证法的关键在于导致矛盾在数论中不少问题是通过奇偶分析或同余等方法引出矛盾的例是否存在三位数使得凯二解如果存在这样的三位数么就有上式可化简为而这显然是不可能的因中所述的一切要求然后从这个存在的元素出发进行推理直到产生矛盾例将某个位数的数字的排列顺序颠倒再将得到的数与原来的数相加试说明得到的和中至少有一个数字是偶数解假设得到的和中没有一个数字是偶数即全是奇数在如因为 9999=99X 101,所以所有幸运券号码之和能被 10 1整除。例9 己知最简分数巴可以養示成 n m,1 1 1 n 2 3 88 试说明分子 m 是质数 89 的倍数。解法一：仿照高斯求和(1+2+3+n)的办法，将和 的各项顺序倒过来再写一遍，即 存#存寻 两式相加，得 兰冥旦+旦+生込 88 2X37 3X36 88 n 从而 2mX 88!=89X k(k 是正整数)。因为 89 为奇质数，所以 89 不能整除 88!，从而 阳 m。解法二：作配对处理此假设出发经过正确的推理导出矛盾的结果这就否定了作为推理出发点的假设从而肯定了原结论是正确的反证法的过程可简述为以下三个步骤反设假设所要证明的结论不成立而其反面成立归谬由反设出发通过正确的推理导出矛盾一既然结论的反面不成立从而肯定了结论成立运用反证法的关键在于导致矛盾在数论中不少问题是通过奇偶分析或同余等方法引出矛盾的例是否存在三位数使得凯二解如果存在这样的三位数么就有上式可化简为而这显然是不可能的因中所述的一切要求然后从这个存在的元素出发进行推理直到产生矛盾例将某个位数的数字的排列顺序颠倒再将得到的数与原来的数相加试说明得到的和中至少有一个数字是偶数解假设得到的和中没有一个数字是偶数即全是奇数在如 喊+G+滸*+恰+)1 1 十+44 X 45 将括号内的分数进行通分，其公分母为 1X 88X 2X 87X 3X 86X X 44X 45=88!,故 巴=89X 碁 a 是正整数)，也 881 从而 mX 88!=89 X k(k=nX q)。因为 89 为奇质数，所以 89 不能整除 88！，从而 89|m 七、估计法 估计法是用不等式放大或缩小的方法来确定某个数或 整个算式的取值范围，以获取有关量的本质特征，达到解 题的目的。在数论问题中，一个有限范围内的整数至多有有限个，过渡到整数，就能够对可能的情况逐一检验，以确定问题 的解。;-1-UX88 2X87 此假设出发经过正确的推理导出矛盾的结果这就否定了作为推理出发点的假设从而肯定了原结论是正确的反证法的过程可简述为以下三个步骤反设假设所要证明的结论不成立而其反面成立归谬由反设出发通过正确的推理导出矛盾一既然结论的反面不成立从而肯定了结论成立运用反证法的关键在于导致矛盾在数论中不少问题是通过奇偶分析或同余等方法引出矛盾的例是否存在三位数使得凯二解如果存在这样的三位数么就有上式可化简为而这显然是不可能的因中所述的一切要求然后从这个存在的元素出发进行推理直到产生矛盾例将某个位数的数字的排列顺序颠倒再将得到的数与原来的数相加试说明得到的和中至少有一个数字是偶数解假设得到的和中没有一个数字是偶数即全是奇数在如 例 10 己知一个整数等于 4 个不同的形如亠尬是整数）的真分数之和，亠 r-求 这个数，并求出满足题意的 5 组不同的真分数。解：因每一真分数满足 而所求的数整 S 是四个不同的真分数之和，因此 2v S V4,推知 S=3。于是可得如下 5 组不同的真分数：f 1 3 5 111 佇 4T Sr 12j 例 11 已知在乘积 1X 2X 3X-X n 的尾部恰好有 106 个连续的零，求自然数 n 的最大值。分析：若已知 n 的具体数值，求 1 x2x-x n 的尾部 零的个数，则比较容易解决，现在反过来知道尾部零的个 数，求 n 的值，不大好处理，我们可以先估计 n 大约是多 少，然后再仔细确定 n 的值。1 2 6 41，J 1 2 3 7 42 2 7 23 一 7 J 一，-2 3 8 24 f 1 2 9 2f 3J W 14 19 20 2 XIL+1 此假设出发经过正确的推理导出矛盾的结果这就否定了作为推理出发点的假设从而肯定了原结论是正确的反证法的过程可简述为以下三个步骤反设假设所要证明的结论不成立而其反面成立归谬由反设出发通过正确的推理导出矛盾一既然结论的反面不成立从而肯定了结论成立运用反证法的关键在于导致矛盾在数论中不少问题是通过奇偶分析或同余等方法引出矛盾的例是否存在三位数使得凯二解如果存在这样的三位数么就有上式可化简为而这显然是不可能的因中所述的一切要求然后从这个存在的元素出发进行推理直到产生矛盾例将某个位数的数字的排列顺序颠倒再将得到的数与原来的数相加试说明得到的和中至少有一个数字是偶数解假设得到的和中没有一个数字是偶数即全是奇数在如解当口=40。时，数 2（承，4Q0 中共有 因此，乘积 1X 2X 3xX 400 中含质因数 5 的个数为 80+16+3=99（个）。又乘积中质因数 2 的个数多于 5 的个 数，故 n=400 时，1X 2 XX n 的尾部有 99 个零，还需 7 个零，注意到 425 中含有 2 个质因数 5，所以 当 n=430 时，1X 2 xx n 的尾部有 106 个零；当 n=435 时，1X 2 XX n 的尾部有 107 个零。因此，n 的最大值为 434。16 个数是宁的倍数.有 400 二？个数是宁的倍数 数.其中有 5 此假设出发经过正确的推理导出矛盾的结果这就否定了作为推理出发点的假设从而肯定了原结论是正确的反证法的过程可简述为以下三个步骤反设假设所要证明的结论不成立而其反面成立归谬由反设出发通过正确的推理导出矛盾一既然结论的反面不成立从而肯定了结论成立运用反证法的关键在于导致矛盾在数论中不少问题是通过奇偶分析或同余等方法引出矛盾的例是否存在三位数使得凯二解如果存在这样的三位数么就有上式可化简为而这显然是不可能的因中所述的一切要求然后从这个存在的元素出发进行推理直到产生矛盾例将某个位数的数字的排列顺序颠倒再将得到的数与原来的数相加试说明得到的和中至少有一个数字是偶数解假设得到的和中没有一个数字是偶数即全是奇数在如
