互質

互質（英文：Coprime，符號：⊥，又稱互素、relatively prime、mutually prime、co-prime）。在數論中，如果兩個或兩個以上的整數的最大公因數是1，則稱它們為互質。依此定義：

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

兩個整數a與b互質，記為a ⊥ b。

互質的例子

例如 8 與 10 的最大公因數是 2，不是 1，因此它們並不互質。
又例如 7, 10, 13 的最大公因數是 1，因此它們互質。

最大公因數可以通過輾轉相除法得到。

整集互質與兩兩互質

三個或三個以上的整數互質有兩種不同的情況：

• 這些整數的最大公因數是 1，我們直接稱這些整數互質，也稱為整集互質（英語：setwise coprime）。以 $\{6,8,9\}$ 為例：

$\gcd(6,8,9)=\gcd(\gcd(6,8),9)=\gcd(2,9)=1$

• 這些整數是兩兩互質的（英語：pairwise coprime）。以 $\{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$，任兩者皆不互質。

性質

性質之一：整數a和b互質當且僅當存在整數x,y使得xa+yb=1。 或者，一般的，有存在整數x,y使得xa+yb=d，其中d是a和b的最大公因數。（貝祖等式）

判別方法

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 Theory（頁面存檔備份，存於網際網路檔案館）
• 史丹福大學離散結構講義（頁面存檔備份，存於網際網路檔案館）
• Abstract Algebra: An Inquiry Based Approach, p.45（頁面存檔備份，存於網際網路檔案館）