輾轉相除法

首先假設有兩個整數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}$ 。

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