互質

在數論中，互質（Template:Lang-en，符號：⊥，又稱-{zh-cn:互质;zh-tw:互素}-）是指如果兩個或兩個以上的整數的最大公因數是1。依此定義：

• 如果數域是正整數${\mathbb{N}}^{\mathbb{+}}$，那麼1與所有正整數互質。
• 如果數域是整數 $\mathbb{Z}$，那麼1和-1與所有整數互質，而且它們是僅有與0互質的整數。

兩個整數Template:Mvar與Template:Mvar互質，記為$a\perp b$，也可以依其定义写成$\gcd (a,b)=1$或$(a,b)=1$。

互質的例子

例如8與10的最大公因數是2，不互質。

又如7、10、13的最大公因數是1，因此互質。

最大公因数可以通过辗转相除法得到。

整集互質與兩兩互質

三个或三个以上的整數互質有两种不同的情况：

• 這些整數的最大公因數是1，我們直接稱這些整數互質，也稱為整集互質（Template:Lang-en）。以 $\{6,8,9\}$為例：$$\gcd (6,8,9)=\gcd (\gcd (6,8),9)=\gcd (2,9)=1$$
• 这些整數是两两互質的（Template:Lang-en）。以$\{7,8,9\}$為例：$$\gcd (7,8)=\gcd (7,9)=\gcd (8,9)=1\Rightarrow \gcd (7,8,9)=\gcd (\gcd (7,8),9)=\gcd (7,\gcd (8,9))=\gcd (\gcd (7,9),8)=1$$

兩兩互質是較為嚴格的互質，如果一個整數集合是兩兩互質的，它也必定是整集互質，但是整集互質不必然是兩兩互質，甚至可能兩兩皆不互質，例如$\gcd (6,15,10)=1$，是整集互質，但$\gcd (6,15)=3$、$\gcd (15,10)=5$、$\gcd (10,6)=2$，任兩者皆不互質。

性質

性质之一：整数Template:Mvar和Template:Mvar互質，当且仅当存在整数Template:Mvar,Template:Mvar，使得$xa+yb=1$。

一般地，存在整数Template:Mvar,Template:Mvar使得$xa+yb=d$，其中Template:Mvar是Template:Mvar和Template:Mvar的最大公因数（贝祖等式）。

判别方法

1. 两个不同的质数一定互質。例如，2与7、13与19。
2. 一个质数，另一个不为它的倍数，这两个数互質。例如，3与10、5与 26。
3. 1和任何一个自然数都互質。如1和9908。
4. 相邻两个自然数互質。如15与16。
5. 相邻两个奇数互質。如49与51。
6. 较大数是质数，則两个数互質。如97与88。
7. 两数都是合数（二数差较大），较小数所有的质因数，都不是较大数的因数，这两个数互質。如357与715，357=3×7×17，而3、7和17都不是715的因数，故这两数互質。
8. 两数都是合数（二数差较小），这两数之差的所有质因数都不是较小数的因数，这两个数互質。如85和78。85－78=7，7不是78的因数，故这两数互質。
9. 两数都是合数，较大数除以较小数的余数（大于“1”）的所有质因数，都不是较小数的因数，則两数互質。如 462与 221，462÷221=2...20，20=2×2×5。2、5都不是221的因数，故这两数互質。
10. 輾轉相除法。如255与182。255－182=73，182－（73×2）=36，73－（36×2）=1，則（255，182）=1。故这两数互質。

外部參考

• Final Answers > Number TheoryTemplate:Wayback
• 史丹福大學離散結構講義Template:Wayback
• Abstract Algebra: An Inquiry Based Approach, p.45Template:Wayback