相對質數

相對質數（Relatively Prime/Coprime）係數論一個基本概念。

定義

假設有兩個整數$a,b\in \mathbb {Z}$。如果$$gcd(a,b)=1$$咁佢哋兩個就係相對質數。

性質

• 比舒公式：如果$gcd(a,b)=1$，咁就會有兩個整數$x,y\in \mathbb {Z}$令到$ax+by=1$。
• $a$同$b$之間係無共同因子（factor）。
• 喺線式商餘方程入面，$ax\equiv c{\bmod {b}}$有一個答案。
• $a$同$b$嘅最小公倍數係$lcm(a,b)=a\times b$。

推理

如果$a|c$同$b|c$，亦都知道$gcd(a,b)=1$都啱嘅話，咁$ab|c$。

證明：

假設$a$同$b$係相對質數，同埋$a|c$同$b|c$。

由$a|c$得出$am=c$，由$b|c$得出$bn=c$。$m$同$n$係某啲整數。

由$gcd(a,b)=1$，利用比舒公式得出$ax+by=1$，$x$同$y$係某啲整數。$${\begin{aligned}ax+by&=1\\acx+bcy&=c\\ax(bn)+by(am)&=c\\ab(xn+my)&=c\end{aligned}}$$所以得出$ab|c$。

歐幾理得推論

喺歐幾理得幾何原本入面證明以下兩條定理。呢兩條定理喺數論入面非常有用。同時，佢都有一個質數版本。

如果$a|bc$，同時$gcd(a,b)=1$，會得出$a|c$。

證明：

由$a|bc$得出$am=bc$。$m$係某啲整數。利用比舒公式得出$ax+by=1$，$x$同$y$係某啲整數。$${\begin{aligned}ax+by&=1\\acx+bcy&=c\\axc+y(am)&=c\\a(xc+my)&=c\end{aligned}}$$所以得出$a|c$。

睇埋

• 最小公倍數
• 最大公因數
• 質數