相對質數

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

定義編輯

假設有兩個整數 $a,b\in \mathbb {Z}$ 。如果

gcd(a,b)=1

咁佢哋兩個就係相對質數。

如果 $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

。