最近我在國中的課堂上，正在進行基礎整數論的教學：「如何求出兩正整數的最大公因數？」

一般來說，有三種方法：短除法、標準分解式找共同質因數中次方較低者、輾轉相除法。

前兩種方法還好解釋，第三種方法就不是三言兩語可以說清楚的。

優秀的學生不會滿足於技術操作，而是會想知道原理。

那麼我們就來談談輾轉相除法是怎麼來的。

首先，要從除法原理談起：任給兩個正整數 $a$、$b$，則存在唯一一組整數 $q$、$r$ 滿足 $$a=bq+r$$ 其中 $$0\leq r<b$$

那麼 $a$ 與 $b$ 的最大公因數等於 $b$ 與 $r$ 的最大公因數： $$(a,b)=(b,r)$$ 這就是操作輾轉相除法的核心概念。

可是為什麼這是對的呢？

如果 $r=0$，則 $a$ 是 $b$ 的倍數，即 $$(a,b)=b=(b,r)$$ 顯然成立。

因此，我們要聚焦在 $r>0$ 的情況下，為何這個等式是對的呢？

首先，可以設 $(a,b)=d_1$、$(b,r)=d_2$

因為 $d_1$ 是 $a$、$b$ 的最大公因數，所以 $d_1$ 必定是 $a-bq$ 的因式(稍微想一下，不難)。

為了方便說明起見，以符號表示： $$d_1|a, d_1|b \Longrightarrow d_1|a-bq = r$$

因為 $$d_1|b, d_1|r$$ 所以 $$d_1|(b,r)=d_2$$ 故 $$d_1\leq d_2\tag{1}$$

另一方面，由 $(b,r)=d_2$ 可知 $$d_2|b, d_2|r$$ 則 $$d_2|bq+r = a$$
因為 $d_2|a, d_2|b$，所以 $$d_2|(a,b)=d_1$$ 故 $$d_2|d_1\tag{2}$$

由 (1)、(2) 可知 $d_1=d_2$ 得證。

輾轉相除法就是反覆進行這樣的過程：

設 $b_1$、$b_2$ 為正整數，且$b_1>b_2$，則存在整數 $q,b_3$ 使得 $$b_1=qb_2+b_3, \ 0\leq b_3<b_2$$
若 $b_3=0$，則 $(b_1,b_2)=b_2$

若 $b_3>0$，則存在整數 $q_1, b_4$ 使得 $$b_2=q_1b_3+b_4, 0\leq b_4<b_3$$ 即 $$(b_2, b_3)=(b_3,b_4)$$

一直持續這樣的過程，可以找到一個遞減數列 $b_1>b_2>b_3>b_4>\cdots$ 滿足 $$(b_1,b_2)=(b_2,b_3)=\cdots=(b_i,b_{i+1}), i\in N$$

在有限步驟下，必定存在一個正整數 $n$ 使得 $b_{n+1}=0$，此時 $$(b_1,b_2) = (b_n,b_{n+1}) = (b_n, 0) = b_n$$

此為歐幾里德算術(Euclid Algorithm)，也是我們在課堂上帶同學操作的過程：

關於最大公因數的另一個觀點

透過上述的歐幾里德算術，我們可以知道，對於任意的整數 $a$、$b$，必定存在整數 $s$、$t$ 滿足 $$sa+tb=gcd(a,b) \tag{*}$$ 為什麼呢？

可以對於歐幾里德算術的步驟 $n$ 進行數學歸納法

假設 $a>b$，$n=1$，也就是說一個步驟就結束了。

此時，存在一個整數 $q$ 使得 $a=bq$，那麼 $$gcd(a,b)=b=1\cdot a+(b-a)=1\cdot a+(1-q)b$$ 其中 $s=1, t=1-q$

接下來，假設 $n<k$ 時，(*) 成立，則當 $n=k$，$k>1$ 時會如何呢？

由除法原理可知，存在兩整數 $q$、$r$ 滿足 $$a=bq+r, 0<r<b$$ 由歸納法假設可知，存在整數 $c$、$d$ 使得 $$cb+dr=gcd(b,r)$$ 故 $$gcd(a,b)=gcd(b,r)=cb+dr=cb+d(a-bq)=da+(c-dq)b$$ 令 $s=d$，$t=c-dq$ 得證。

我們來做一個簡單的練習：如何找出整數 $x$、$y$ 滿足 $$754x+221y=gcd(754,221)$$

同樣地，從歐幾里德算術開始：
$$\begin{aligned} 步驟1：754 &= 3\times 221+91 \\ 步驟2：221 &= 2\times 91+39 \\ 步驟3： \ 91 &= 2\times 39+13 \\ 步驟4： \ 39 &= 3\times 13 +0 \end{aligned}$$ 因此可得 $gcd(754,221)=13$

接著將以上操作反過來寫：
$$\begin{aligned} 13 &= 91-2\times 39 \\ &= 91-2\times (221-2\times 91) \\ &= 5\times 91 -2\times 221 \\ &= 5\times (754-3\times 221)-2\times 221\\ &=5\times 754 – 17\times 221 \end{aligned}$$ 找到了，$x=5$、$y=-17$

可是，如果考慮一般的整係數方程式 $ax+by=c$，要如何確定有整數解呢？

如果整係數方程式 $ax+by=c$ 有整數解，則 $(a,b) | ax+by$，因此可得 $(a,b) | c$，

也就是說，$(a,b)| c$ 是整係數方程式 $ax+by=c$ 有整數解的必要條件。

另一方面，若 $(a,b) | c$，則存在一個整數 $q$ 使得 $$c=(a,b)\times q$$

由以上討論可知，存在整數 $s, t$ 使得 $$sa+tb=(a,b)$$ 即 $$(sq)a+(tq)b=(a,b)\cdot q=c$$ 此時 $$x=sq,\ y=tq$$

但是還有個問題，這個整係數方程式 $ax+by=c$ 應該不只一組解吧，那其他解要如何找呢？

很簡單，其實就是找出直線 $ax+by=c$ 上的格子點($x$、$y$ 坐標皆為整數的點)。

假設，經由歐幾里德算術，我們可以找到一組解 $(x_0, y_0)$，而且令 $x, y$ 是另一組整數解，

則 $$\frac{y-y_0}{x-x_0}=-\frac{a}{b}=\frac{a/d}{-b/d}$$ 其中 $d=(a,b)$，因此
$$\begin{cases} x&= x_0-\frac{b}{d}k \\ y&= y_0+\frac{a}{d}k \end{cases}$$

看完以上介紹，請同學不妨試著做做看以下這道題：

自己先想過再看解法喔。

根據除法原理：
$$\begin{align} 629 &= 357\cdot 1 + 272 \\ 357 &= 272\cdot 1 + 85 \\ 272 &= 85\cdot 3 +17 \\ 85 &= 17\cdot 5 +0 \end{align}$$

將以上計算由後往前推：
$$\begin{aligned} 17 &= 272 -3\cdot 85 \\ &= 272-3\cdot (357-272\cdot 1) \\ &= 4\cdot 272 – 3\cdot 357 \\ &= 4\cdot (629-357) – 3\cdot 357 \\ &= -7\cdot 357 + 4\cdot 629 \end{aligned}$$

以上的計算過程，可以呈現如下：

如果看得不是很清楚，不妨用符號來表示：令 $a=357$、$b=629$ 則
$$\begin{aligned} b &= a\cdot 1 + (b-a) \\ a &= (b-a) \cdot 1 + (2a-b) \\ (b-a) &= (2a-b)\cdot 3 + (-7a+4b) \\ (2a-b) &= (-7a+4b)\cdot 5 + 0 \end{aligned}$$ 因此， $$-7a+4b=17$$ 圖示如下：

第(2)題的部份： $$[357, 629] = \frac{357\times 629}{(357, 629)}=\frac{357\times 629}{17} = 13209$$

這篇文章就先寫到這邊，提供給學生們當作課外補充參考。

最後也放一部Youtube優質影片給大家參考

歡迎訂閱 高中數學數位學習電子報

高中數學數位學習電子報訪客

Δ

Updates

怎麼稱呼

填寫 Email (訂閱成功後會收到回信，若未收到可能e-mail寫錯了喔！)

立即訂閱取得學習資料

Gim’s 數學數位學習教室

高一數學line@