北仑中文网

第七十四章 周一的微妙与算法的延伸（第2页）

“看，这就是我佩服的人”。

下午放学后，数学小组的第二次活动如期举行。

这次的主题是深入探讨“辗转相除法”（欧几里得算法）的延伸。

苏白首先带领大家快速回顾了算法的基本步骤和原理验证。

然后，他抛出了新的问题：

“我们己经知道如何高效求出两个数的最大公约数（GCD）。

那么，能不能找到两个整数x和y，使得ax+by=GCD（a，b）成立呢？

比如，对于1071和462，我们能不能找到这样的x和y？”

这个问题立刻引起了大家的兴趣。

“这有什么用呢？”张涛好奇地问。

“应用很广。”

苏白解释道：

“比如在数论中解不定方程，或者在密码学的一些基础算法里，这都是关键一步。”

他接着介绍了“扩展欧几里得算法”的基本思想——

在辗转相除法的每一步中，同时记录下余数可以表示为a和b的线性组合的形式，并逆向回溯代入。

演示过程略显复杂，但苏白讲解得极有耐心，一步步在黑板上推导。

李浩紧跟思路，不时提出关键点；林薇薇虽然有些步骤需要反复理解，但在苏白的引导下也逐渐跟上了节奏；张涛则负责记录每一步的关键结果，确保大家不迷路。

当最终得到x=-7，y=16满足1071（-7）+462（16）=21（即GCD）时，小组成员都露出了兴奋的表情。

“太神奇了！”

林薇薇惊叹道：

“就像拆解一个精巧的机械，每一步都严丝合缝，最后真的拼出了想要的结果！”

李浩推了推眼镜：

“这个逆向代入的过程，体现了很强的递归和逆向思维。”

张涛看着密密麻麻的演算过程，咂舌道：

“虽然烧脑，但搞明白后真有成就感！”

活动结束时，窗外天色己晚。

大家收拾好东西，一起走出教学楼。

“下次我们可以找些具体的应用题，比如解一个简单的不定方程，试试这个新工具。”