輾轉相除法

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

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

詳細算法

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

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

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

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

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

證明

假設有兩個整數${\displaystyle a,b\in \mathbb {Z} }$。利用餘數定理，得知有一個${\displaystyle r_{0},q_{0}\in \mathbb {Z} }$同埋${\displaystyle 0<r_{0}<b}$，得到$${\displaystyle a=bq_{0}+r_{0}}$$之後，利用最大公因數既性質，得知${\displaystyle \gcd(a,b)=\gcd(b,r_{0})}$。根據輾轉相除法，$${\displaystyle b=r_{0}q_{1}+r_{1}}$$同一個原理，${\displaystyle \gcd(b,r_{0})=\gcd(r_{0},r_{1})}$。直到${\displaystyle r_{n}=0}$，得到$${\displaystyle r_{n-2}=r_{n-1}q_{n}+r_{n}}$$，得知${\displaystyle \gcd(r_{n-2},r_{n-1})=\gcd(r_{n-1},r_{n})}$。

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

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

其他應用

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

證明：

利用輾轉相除法求${\displaystyle \gcd(ka,kb)}$。$${\displaystyle {\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}}}$$所以，${\displaystyle \gcd(a,b)=r_{n-1}}$，${\displaystyle \gcd(ka,kb)=r_{n-1}k}$。

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

證明：

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

例子

搵13579同246810既GCD。

${\displaystyle {\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}}}$

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

睇埋

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