STEP数学练习:辗转相除为什么能找到最大公因数?

知道辗转相除的操作,并不等于解释了它为什么正确。STEP相关证明训练可以把一个熟悉算法拆成计算、等价关系和验证三部分。下面是原创练习,重点是论证结构,不是官方题目或当年考试安排。

想结合自己的基础讨论下一步?到文末扫码联系翰林,发送“STEP公因数1103”,说明年级、学习目标和目前最困惑的问题。

把除法链完整写出来

计算414和162的最大公因数:414=2×162+90;162=90+72;90=72+18;72=4×18。最后一个非零余数是18,因此得到最大公因数18。

这里不能在第一次得到90后就停止。90虽然是余数,却不整除162。算法应继续到下一步余数为0,并回到上一项非零余数。

为什么可以用余数替换

设a=qb+r。若整数d同时整除a和b,就也整除a−qb=r。因此a、b的每个公因数都是b、r的公因数。

反过来,如果d同时整除b和r,就整除qb+r=a。因此两对数拥有完全相同的公因数集合,最大公因数自然相同。把两个方向都写出,才建立了等价关系,而不是只有一个包含关系。

回代得到独立核对

由18=90−72、72=162−90,得到18=2×90−162。再用90=414−2×162代入,得到18=2×414−5×162。

直接计算右边828−810=18,验证了恒等式。同时414=23×18、162=9×18,说明18确实整除两个原数。回代过程也展示了最大公因数能够写成原数的整数线性组合。

从算法答案走向证明答案

一份清楚的解答应包括余数链、共同因子为何保留,以及最后结果为何符合定义。若讨论正整数的一般算法,还可说明非负余数严格减小,所以过程会终止。

做推广时先说明数的范围与最大公因数取正数的约定,再处理符号或零的特殊情况。咨询可带上自己的证明段落,标出究竟是“这一步为何成立”还是“怎样把计算写成证明”,比只发送18这个答案更有效。

延伸阅读:STEP证明训练:数学归纳法的递推步,究竟假设了什么。

带着具体问题,扫码联系翰林

正在了解项目、选择学习方向,或已经开始准备?用微信扫描下方二维码,发送“STEP公因数1103”。请补充年级、所在地区、当前基础和最想解决的问题,方便沟通时直接聚焦。

微信扫码联系翰林,发送STEP公因数1103咨询学习与准备问题

微信咨询学习与准备方向

电脑阅读可用微信扫码;手机阅读可点击入口,或保存二维码后在微信内识别。

官方信息与延伸资料:资料1

在线客服
微信咨询