歡迎光臨亞夜漫聊。
這是亞夜的一個不定期專欄，主要是分享亞夜學習到的新知識或個人見解，主題可能包括財經、健身、科學或數學等。如果您能在這邊學到一點東西，那是亞夜的榮幸；而如果有什麼錯誤或建議，或者有什麼主題想要亞夜聊一聊的，也都歡迎在底下留言，您的留言亞夜一定都會看過。
今天來聊聊「輾轉相減法」。相信應該大多數人都對「輾轉相『除』法」有印象，因為這是台灣國民教育的教材。在亞夜那個時代是國小的教材，現在聽說移到國中了？不重要，總之，除法其實在四則運算裡面是最麻煩的，所以今天來介紹另一個方法讓大家參考看看。
【輾轉相除法】
在這之前，我們先簡單帶一下國小（中？）學的「輾轉相除法」。輾轉相除法的操作過程為：
拿大數除以小數，求餘數。因為是餘數，所以小數（除數）會比較大。
如果餘數不是零，那麼就把原本的小數當成被除數，餘數當成除數，並繼續求餘數。
如果餘數是零，那麼此時的除數就是最大公因數。
〔範例〕
求 1767 跟 2511 的最大公因數：
2511 ÷ 1767 = 1 ... 744 ——不為零
1767 ÷ 744 = 2 ... 279 ——不為零
744 ÷ 279 = 2 ... 186 ——不為零
279 ÷ 186 = 1 ... 93 ——不為零
186 ÷ 93 = 2 ... 0 ——為零，因此 93 為所求。
事實上，2511 = 93 × 27；1767 = 93 × 19，所以最大公因數是 93 無誤。
〔證明〕
一般課堂上只會教方法，但不會證明。然而，其實「輾轉相除法」本身並不是巧合，而是真正可以證明的數學定理。
求 x、y 兩數的最大公因數，x > y 。那我們假設這個公因數是 α。然後我們就：
令 x = aα、y = bα，a > b，且 a、b 互質或 b = 1；a、b ∈ N。
令 a = nb+m；n、m ∈ N，且 m < b。
x ÷ y = aα ÷ bα = ( nbα + mα ) ÷ bα = n ... mα
令 bα = x'；mα = y'
x' = a'α、y' = b'α，a' > b'，且 a'、b' 互質或 b' = 1；a'、b' ∈ N（自然數）。
令 a' = n'b'+m'；n'、m' ∈ N，且 m' < b'。
x' ÷ y' = a'α ÷ b'α = ( nb'α + m'α ) ÷ b'α = n' ... m'α
∵ y < x ∴ x' < x →a' < a 、 b' < b 、 m' < m
根據數學歸納法，m、m'、m''... ∈ N，且逐次遞減，因此 k 次後 m(k') 必然收斂到 1（最小自然數）。
令 m(k')=1
→ a(k') = nb(k') + 1
→ x(k') ÷ y(k') = (nb(k')+1) α ÷ b(k')α = n ... α
最後一步：
b(k')α ÷ α = b(k') ... 0 ——輾轉相除法的結論：α 即為所求。
其實，數學上我們常這樣說：
．減法是加法的逆運算
．除法是乘法的逆運算
．乘法是加法的速算法
．因此，除法是減法的速算法
看似奇妙，其實有幾分道理。因為在除法的過程中，你要一直求餘數。而餘數怎麼求？餘數等於被除數減去除數與商數的乘積，因此過程中確實是在做減法。
因為，x、y 存在最大公因數 α（α 當然可以是 1），所以我們理所當然可以把 x、y 都用 α 的倍數表示。而 α 的倍數減去 α 的倍數，剩下來的必然還是 α 的倍數，這個很好證明：
乘法分配律：
aα - bα = (a-b)α 得證
而求餘數的過程就是一直在做這件事而已，數字越減越小，最後減到剩 1，不就得到 α 了嗎？而 α 無法再細拆，因為整個過程永遠都是 α 的倍數，所以 α 的 1 被再減下去就得 0，因此可以確定 α 為所求。
【輾轉相減法】
以上過程其實不太好理解，如果題目很機車，除法也不好做，所以如果你覺得燒腦，可以先接受這個結論，但先別管為什麼。
而今天的重點是《輾轉相減法》。這個方法台灣不教，但中國有教。但為什麼台灣不教？因為說穿了，這個方法只是《輾轉相除法》的變體而已，本質是同一個方法。
輾轉相減法怎麼操作？是這樣的：
拿大數減小數，求出差。
拿出小數（減數）跟差做比較，這兩個數，大數減小數，求出一個新差。
如此反覆，一旦差值與減數相同，即為所求。
〔範例〕
求 1767 跟 2511 的最大公因數：
2511 - 1767 = 744 ——不相同
1767 - 744 = 1023 ——不相同
1023 - 744 = 279 ——不相同
744 - 279 = 465 ——不相同
465 - 279 = 186 ——不相同
279 - 186 = 93 ——不相同
186 - 93 = 93 ——相同，因此 93 為所求。
仔細比較輾轉相除法與輾轉相減法的過程：
2511 ÷ 1767 = 1 ... 744 1767 ÷ 744 = 2 ... 279 744 ÷ 279 = 2 ... 186 279 ÷ 186 = 1 ... 93 186 ÷ 93 = 2 ... 0 ——為零，因此 93 為所求。 |
2511 - 1767 = 744 1767 - 744 = 1023 1023 - 744 = 279 744 - 279 = 465 465 - 279 = 186 279 - 186 = 93 186 - 93 = 93 ——相同，因此 93 為所求。 |
注意畫底線的部分，你會發現出現跟輾轉相除法重覆的數字。
其實，輾轉相減法只是把輾轉相除法的「求餘過程」用另一種方式呈現，因此兩個算法在邏輯上是嚴格等價的。
雖然輾轉相除法的算是比較少，但你需要先進行「估商」的動作。如果估商估錯，算了半天乘法結果餘數還筆除數大，又要重算一次。而「連減」雖然要一值重覆運算，但不存在估商的問題，也不用做乘法，也許計算量較大，但出錯率可能較低。
【後記】
工具沒有對錯，只有好不好用。輾轉相除法還是輾轉相減法，其實都是在做同一件事，跟解方程組的加減消去法與高斯消去法之間的關係一樣，本質是同一件事，只是看你覺得哪一個過程方便而已。
要亞夜來分高下的話，對於「數感強」的人而言，輾轉相除法顯然快得多；但對於數感弱，乘除法計算有困難的同學而言，輾轉相減法的確是個簡單高效的替代選項，湊合著用也沒有不行。
喔對了，對於討厭數學的人，也許會問：「所以求最大公因數可以幹嘛？」
當你在職場上，在海量數據中要找出「最小單位」時，你就需要用到最大公因數了。例如貼磁磚就會用到。你覺得沒用只是你還沒遇到問題而已。
封面圖片：AI 生成
達人
