本頁使用了標題或全文手工轉換

互質

維基百科,自由的百科全書
跳至導覽 跳至搜尋

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

  • 如果數域正整數 ,那麼 1 與所有正整數互質[3]
  • 如果數域整數 ,那麼 1-1 與所有整數互質[4],而且它們是唯一與 0 互質的整數[5]

兩個整數 ab 互質,記為 ab

互質的例子[編輯]

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

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

整集互質與兩兩互質[編輯]

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

  • 這些整數的最大公因數是 1,我們直接稱這些整數互質[6],也稱為整集互質英語:setwise coprime[7]。以 為例:
  • 這些整數是兩兩互質的(英語:pairwise coprime)。以 為例:

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

性質[編輯]

性質之一:整數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。故這兩數互質。

參考來源[編輯]

外部參考[編輯]