04.拓展欧几里得算法

title: 04. 拓展欧几里得算法 tags: zk basic euclidean WTF zk教程第4讲：拓展欧几里得算法 在本讲中，我们将深入研究欧几里得算法的一种扩展，这一算法不仅可以计算最大公约数，还能找到满足贝祖等式（Bézout equation）的整数解。 贝祖等式 在介绍拓展欧几里得算法之前，让我们先来了解一下贝祖等式。对于两个整数 $a$ 和 $b$，存在整数 $x$ 和 $y$ 使得它们满足如下等式： $$ ax + by = \gcd(a, b) $$ 这个等式称为贝祖等式，其中 $\gcd(a, b)$ 是 $a$ 和 $b$ 的最大公约数。拓展欧几里得算法的目标就是找到这样的整数 $x$ 和 $y$。 拓展欧几里得算法 2.1 基本思想 拓展欧几里得算法在使用欧几里得算法计算最大公约数的同时，通过逆向推导，找到满足贝祖等式的整数解。在欧几里得算法中，我们只关心每次迭代的余数 $ri$，而不关心商 $qi$；而拓展算法中利用 $qi$ 逆向求出贝祖等式，可谓是废物利用了。 让我们回忆一下欧几里得算法： $$ a = bq0 + r0 $$ $$ b = r...