知道辗转相除的操作,并不等于解释了它为什么正确。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”。请补充年级、所在地区、当前基础和最想解决的问题,方便沟通时直接聚焦。

电脑阅读可用微信扫码;手机阅读可点击入口,或保存二维码后在微信内识别。
官方信息与延伸资料:资料1
