擴展歐幾里得演算法

現在要來介紹輾轉相除法的擴充算法。

定理1

\(a, b \in \mathbb{Z}\) 若 \(d = \gcd(a, b)\)，則存在 \(s, t \in \mathbb{Z}\) 使得 \(as + bt = d\)

證明

使用輾轉相除法時，令第 \(i\) 次遞迴之後，\(a\) 變成了 \(a_i\)，\(b\) 變成了 \(b_i\)。可以發現，最後一步時 \(a\) 曾變成 \(0\)，\(b\) 曾變成 \(d\)。此時\(0 \times a + 1 \times b = d\)
。

令 \(a_{i+1}x' + b_{i+1}y' = d\)。根據輾轉相除法的內容：\(a_{i+1} = b_i \mod a_i\)，\(b_{i+1} = a_i\)。因此代入後得知

\[
(b_i\mod a_i)x' + a_iy' = d
\]

注意到 \(b_i \mod a_i = b_i - a_i \times \left\lfloor \frac{b_i}{a_i} \right\rfloor\)，代入並且整理後可以發現：

\[
a_i \left( y' - \left\lfloor \frac{b_i}{a_i} \right\rfloor x' \right) + b_ix' = d
\]

與 \(a_ix + b_iy = d\) 比較後可得：

\[
\begin{cases}
x = -\left\lfloor \frac{b_i}{a_i} \right\rfloor x' + y' \\
y = x'
\end{cases}
\]

也就是說，我們有了 \(i+1\) 屆的答案就能夠構造第 \(i\) 屆的答案。而我們又知道最後一屆的答案是 \(x = 0\)，\(y = 1\)。因此我們就以構造證明了定理1。不僅如此，知道如何構造之後，也能夠輕易地將其寫成程式碼。

pair<int, int> ExtGCD(int a, int b) {
    if (a == 0)
        return pair<int, int>(0, 1);
    auto [x, y] = ExtGCD(b % a, a);
    return pair<int, int>(-(b / a) * x + y, x);
}

定理2

(歐幾里得引理). 已知 \(gcd(a, b) = 1\)，那麼若 \(a \mid bc\)，則 \(a \mid c\)

證明

存在 \(s, t\) 使得 \(as + bt = 1\)，兩邊同乘以 \(c\) 得到 \(acs + bct = c \Rightarrow a \mid c\)