算术基本定理
扩展欧几里得算法
重要程度：6 分
<div>
<h2>扩展欧几里得算法</h2>
<p><strong>定义：</strong>扩展欧几里得算法是用于计算两个整数的最大公约数，并同时找到满足贝祖等式 ax + by = gcd(a, b) 的整数 x 和 y 的算法。</p>
<p><strong>步骤：</strong></p>
<ol>
<li>如果 b == 0，则 gcd(a, b) = a，x = 1，y = 0。</li>
<li>否则，递归调用扩展欧几里得算法来计算 gcd(b, a % b)，得到 gcd(b, a % b)、x1 和 y1。</li>
<li>通过以下公式计算 x 和 y：x = y1，y = x1 - (a / b) * y1。</li>
</ol>
<p><strong>例题：</strong>使用扩展欧几里得算法求解 30x + 18y = gcd(30, 18)。</p>
<pre>
gcd(30, 18):
1. r = 30 % 18 = 12
x1 = 1, y1 = 0
x = 0, y = 1 - (30 / 18) * 0 = 1
2. r = 18 % 12 = 6
x1 = 0, y1 = 1
x = 1, y = 0 - (18 / 12) * 1 = -1
3. r = 12 % 6 = 0
x1 = 1, y1 = -1
x = -1, y = 1 - (12 / 6) * (-1) = 2
</pre>
<p>因此，gcd(30, 18) = 6，且 30 * (-1) + 18 * 2 = 6。</p>
</div>