Rearuh

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

• 如果數域是正整數 N+{displaystyle mathbb {N^{+}} }，那麼 1 與所有正整數互質^[3]。


• 如果數域是整數 Z{displaystyle mathbb {Z} }，那麼 1 和 -1 與所有整數互質^[4]，而且它們是唯一與 0 互質的整數^[5]。

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

互質的例子

例如 8 與 10 的最大公因數是 2，不是 1，因此它們並不互质。

又例如 7, 10, 13 的最大公因數是 1，因此它們互质。

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

整集互質與兩兩互質

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

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

gcd(6,8,9)=gcd(gcd(6,8),9)=gcd(2,9)=1{displaystyle gcd(6,8,9)=gcd(gcd(6,8),9)=gcd(2,9)=1}

• 这些整數是两两互质的（英语：pairwise coprime）。以 {7,8,9}{displaystyle {7,8,9}} 為例:

gcd(7,8)=gcd(7,9)=gcd(8,9)=1⇒gcd(7,8,9)=gcd(gcd(7,8),9)=gcd(7,gcd(8,9))=gcd(gcd(7,9),8)=1{displaystyle gcd(7,8)=gcd(7,9)=gcd(8,9)=1Rightarrow gcd(7,8,9)=gcd(gcd(7,8),9)=gcd(7,gcd(8,9))=gcd(gcd(7,9),8)=1}

兩兩互質是較為嚴格的互質，如果一個整數集合是兩兩互質的，它也必定是整集互質，但是整集互質不必然是兩兩互質。

性質

性质之一：整数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. 
   2的冪和任何一个奇数都互质。如32和75、256与315。


5. 相邻两个自然数互质。如15与16。


6. 相邻两个奇数互质。如49与51。


7. 一個數的質因數都小於某數，另一個數質因數都大於同一個數，則两个数互质。如180与2431、5040与4301。


8. 两个偶数一定不互质，有公因數2。如84与50、816与612。


9. 末位數是5或0的兩數一定不互质，有公因數5。如2975与360。


10. 较大数是质数，則两个数互质。如97与88。


11. 兩數和是质数，則两个数互质。如52与45。


12. 兩數差是质数，兩个數都不是兩數差的倍數，則两个数互质。如140与171。


13. 兩數積是無平方數因數的數，則两个数互质。如154与195。


14. 较大数除以較小數的餘數是1或-1，則两个数互质。如440与63。


15. 两数都是合数（二数差较大），较小数所有的质因数，都不是较大数的因数，这两个数互质。如357与715，357=3×7×17，而3、7和17都不是715的因数，故这两数互质。


16. 两数都是合数（二数差较小），这两数之差的所有质因数都不是较小数的因数，这两个数互质。如85和78。85－78=7，7不是78的因数，故这两数互质。


17. 两数都是合数，较大数除以较小数的余数（大于“1”）的所有质因数，都不是较小数的因数，則两数互质。如 462与 221，462÷221=2...20，20=2×2×5。2、5都不是221的因数，故这两数互质。


18. 輾轉相除法。如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