合数数列(说几个数论中的经典问题)

作者|刘瑞祥来源|说短论长编辑|遇见数学本文原创性很低,但是我希望大家读了以后能“真的”读懂,切实理解其中道理,而不是囫囵吞枣。本文涉及初等数论的三个非常重要的定理(算法),均出自《几何原本》。如果两

  作者 | 刘瑞祥

  来源 | 说短论长

  编辑 | 遇见数学

  本文原创性很低,但是我希望大家读了以后能“真的”读懂,切实理解其中道理,而不是囫囵吞枣。本文涉及初等数论的三个非常重要的定理(算法),均出自《几何原本》。

  说几个数论中的经典问题如果两个数都能被第三个数整除,则这两个数的和、差一定能被第三个数整除;如果两个数有且只有一个能被第三数整除,则这两个数的和、差一定不能被第三个数整除。

  设有两个数 、,欲求其最大公约数,可以用大数除以小数,取其余数(肯定小于一开始的较小数,我们不妨称这一步得到的余数是第一余数),再以开始所给的较小数除以第一余数,再取余数(即第二余数),以后以第一余数除以第二余数达到第三余数,第二余数除以第三余数得到第四余数…直至余数为 时,上一次的余数即为初始两个数的最大公约数。

  说几个数论中的经典问题例:设初始的两个数为 和 ,以 除以 得到第一余数为 ,再以 除以 得到第二余数为 ,以 除以 得到第三余数为 3,因为 12 能被 3 整除,所以 3 是最大公约数。

  → 和 的最大公约数是 。

  道理很简单: 取余数,其实可以看做从 里连续减去 直到减不开为止。而公约数 (姑且不管是不是最大)是 和 共同的约数,即 、 都是 的倍数,所以从 中连续减去 ,两个同为 倍数的数做减法,得到的余数(这里是第一余数)当然还是 的倍数,此即前面提到的预备知识。以后辗转进行下去,每一次得到的余数当然也还是 的倍数。直到得到这个 ,也就是整除了。

  那为什么是最大公约数呢?因为如果不是最大的,换句话说就是还有更大的,比如是 。那么这个 就在前面的过程中被“跳过去”了。那么显然就违背了预备知识。因为本来任何一步里两个数的全部约数都满足预备知识,结果这么一来肯定有的不满足了。

  以上就是著名的欧几里得算法,只不过当年欧几里得用词远比这严谨。这个算法有什么用呢?它比起小学学的短除法,最大的好处是不用一个个的尝试某个数是不是公约数。短除法对于大数很麻烦,比如求 和 的最大公约数需要一个个尝试,如果给的两个数更大,特别是两个数的公共质因数很大,就更麻烦(最近一位老师让学生计算 和 的最大公约数,许多学生就算不出来)。另外用辗转相除法还可以立刻得出一个结论:相差为 的两个正整数互质。

  这个关系很简单:两个数的最大公约数和最小公倍数,二者的乘积等于原来两个数的乘积。

  说几个数论中的经典问题首先我们看两个互质数的情况:互质数的最大公约数就是 ,最小公倍数就是这两个数的乘积,显然符合这个关系,但是任意两个正整数呢?

  要理解这个关系也不难,假设两个数 、 的最大公约数是 ,即 ,,则显然 ,而括号里的 恰好就是最小公倍数。如果还有人觉得不放心,可以回忆一下短除法的计算过程:对于两个数的情况,“侧面的”乘在一起就是最大公约数 ,侧面的和“底下的”乘在一起(无论计算最大公约数还是最小公倍数,侧面的只取一次)就是最小公倍数 。

  这个定理有很多证明方法,但最简单的是这个:假设质数是有限的,将全部各个质数乘起来再加 ,则这个新得到的数肯定和全部质数的乘积互质,即不能被已有的各个质数整除,所以是一个新的质数。这就和前面矛盾了。

  合数数列(说几个数论中的经典问题) -1大家要注意,这里并不是说若干质数乘起来再加 一定会得到新的质数,实际上也可能得到一个能被其它质数整除的合数。比如 、 都是质数,而 却不是,它是 的倍数,注意 不是

  用连续相乘的方法还可以求任意长度的连续合数数列。比如我要生成连续 个合数,就可以先计算出 ,然后用这个结果加 、加 、加 一直到加 ,因为 含有 的每个因子,所以加 就是 的倍数,加 就是 的倍数,如此等等。可以想见,用这样的方法得到连续的千百万个合数也是没有问题的。但是这样得到的数列肯定不会是最小的,即以此题为例,实际上在这之前我们就有 连续七个合数,而更前面还有 、、、、、、 等多个连续的五合数数列。另外不但从 乘到 加 直至加 是合数,而且 前面还有 也都是合数,也就是说 连续十三个数都是合数。

  一方面质数是无穷无尽的,另一方面连续的合数数列可以要多长有多长,多么神奇的数学。

  另外我要说一点:初等数论在小学数学中是非常特别的内容,它的计算和小学数学其它部分明显不同,主要是对逻辑的要求比较高,如果只让学生机械地记忆和应用这些内容,那就太可惜了。虽然谁出的卷子都不要求学生写算理,但是算理最重要。至于有的老师总觉得学生不一定能理解其中的道理,那我只能说:如果你不去发展学生的思考能力,那学生就永远也无法发展思考能力,思考能力的发展是长期而艰巨的,但不可缺少。为什么五年级学生理解不了被 整除数的特性?因为他四年级的时候没有发展相应能力,四年级时为什么没有发展起来?因为他三年级时…老师总是告诉学生最后的结论,如同厨子总是把菜做好了再端上来,顾客是不会学会做菜的。

  说几个数论中的经典问题

本文来自投稿,不代表仟亿经验网立场,如若转载,请注明出处:https://www.qyjsjt.cn/24501.html

本站所有文章资讯、展示的图片素材等内容均为注册用户上传(部分报媒/平媒内容转载自网络合作媒体),仅供学习参考。如有侵犯您的版权,请联系我们dra9on333@qq.com反馈!本站将在三个工作日内改正

(0)
上一篇 2022年8月6日 14:25:38
下一篇 2022年8月6日 15:28:38

相关推荐