扩展欧几里德算法
的<年代trong>欧几里得算法
欧几里得算法
欧氏算法基本上是整数除法算法的连续重复。关键是要反复用除数除以余数,直到余数为0。GCD是该算法中最后一个非零余数。下面的例子演示了寻找102和38的GCD的算法:
GCD为2,因为它是算法终止前出现的最后一个非零余数。 我们有
最后一个非零余数为17,因此GCD为17。<年代pan class="katex">
这个算法可以用下面的递归漂亮地实现:
用欧几里得算法求出42823和6409的GCD。
欧几里得算法的递归实现
1 2 3 4 5 6 |
|
扩展欧几里德算法
扩展欧几里得算法是一种计算整数的算法<年代pan class="katex">
而且<年代pan class="katex">
这样
鉴于<年代pan class="katex">
而且<年代pan class="katex">
. 这样的整数的存在由<一个t一个rget="_blank" rel="nofollow" href="//www.parkandroid.com/wiki/bezouts-identity/">Bezout引理 扩展欧氏算法可以看作是模幂的倒数。 通过反转欧氏算法中的步骤,就有可能找到这些整数<年代pan class="katex">
而且<年代pan class="katex">
.整个思路是从GCD开始,然后递归地往回走。这可以通过将数字作为变量来实现,直到我们得到一个表达式,它是初始数字的线性组合。我们将用上面的例子来做这件事。 我们从GCD开始。我们用前两项来重写
我们更换了<年代pan class="katex">