輾轉相除法

輾轉相除法zin2 zyun2 soeng1 ceoi4 faat3，或者叫歐幾里得演算法（英文：Euclidean algorithm），係求最大公因數嘅算法。輾轉相除法首次記載喺約前300年古希臘嘅歐幾里得嘅《幾何原本》入面，而中國最早記載喺東漢嘅《九章算術》。

輾轉相除法例子：${\begin{aligned}12&=5\times 2+2\\5&=2\times 2+1\\2&=2\times 1\end{aligned}}$

詳細算法

首先假設有兩個整數a，b，其中一個並唔等於零。

利用餘數定理，得出$a=bq_{1}+r_{1}$。

再利用餘數定理，將$b$除$r_{1}$，得出$b=r_{1}q_{2}+r_{2}$。

重複以上步驟，直到可以餘盡為止，如果係n次搞掂嘅話，即係$r_{n}=0$，得出$r_{n-2}=q_{n}r_{n-1}+r_{n}=q_{n}r_{n-1}$。

咁佢哋嘅公因數就係 $\gcd(a,b)=r_{n-1}$

證明

假設有兩個整數$a,b\in \mathbb {Z}$。利用餘數定理，得知有一個$r_{0},q_{0}\in \mathbb {Z}$同埋$0<r_{0}<b$，得到

$$a=bq_{0}+r_{0}$$

之後，利用最大公因數既性質，得知$\gcd(a,b)=\gcd(b,r_{0})$。根據輾轉相除法，

$$b=r_{0}q_{1}+r_{1}$$

同一個原理，$\gcd(b,r_{0})=\gcd(r_{0},r_{1})$。直到$r_{n}=0$，得到

$$r_{n-2}=r_{n-1}q_{n}+r_{n}$$

，得知$\gcd(r_{n-2},r_{n-1})=\gcd(r_{n-1},r_{n})$。

因為$r_{n}=0$，所以$\gcd(r_{n-2},r_{n-1})=\gcd(r_{n-1},0)=r_{n-1}$。

再推返上去，$\gcd(a,b)=r_{n-1}$。

其他應用

第一個應用係用嚟證明「如果$k>0$，咁就$\gcd(ka,kb)=k\gcd(a,b)$。」

證明：

利用輾轉相除法求$\gcd(ka,kb)$。

$${\begin{aligned}a&=bq_{0}+r_{0}\quad ,0<r_{0}<b\\ak&=(bk)q_{0}+r_{0}k\quad ,0<r_{0}k<bk\\.\\.\\.\\r_{n-2}&=q_{n}(r_{n-1})+r_{n}\quad ,r_{n}=0\\r_{n-2}k&=q_{n}(r_{n-1}k)+r_{n}\quad ,r_{n}=0\end{aligned}}$$

所以，$\gcd(a,b)=r_{n-1}$，$\gcd(ka,kb)=r_{n-1}k$。

由上面可以推斷到「任何整數$k\neq 0$，$\gcd(ka,kb)=|k|\gcd(a,b)$。」

證明：

如果$k>0$，咁$\gcd(ka,kb)=k\gcd(a,b)$，即係$\gcd(ka,kb)=|k|\gcd(a,b)$。即係要假設$k<0$，咁樣$-k=|k|>0$。

$${\begin{aligned}\gcd(-ka,-kb)&=\gcd(|k|a,|k|b)\\&=|k|\gcd(a,b)\end{aligned}}$$

例子

搵13579同246810既GCD。

${\begin{aligned}246810&=13579\times 18+2388\\13579&=2388\times 5+1639\\2388&=1639\times 1+749\\1639&=749\times 2+141\\749&=141\times 5+44\\141&=44\times 3+9\\44&=9\times 4+8\\9&=8\times 1+1\end{aligned}}$

所以$\gcd(246810,13579)=1$。

睇埋

• 比舒公式
• 線性商餘方程
• 孫子定理