上一页

ⓘ 互質




                                     

ⓘ 互質

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

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

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

                                     

1. 互質的例子

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

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

                                     

2. 整集互質與兩兩互質

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

  • 這些整數的最大公因數是 1 ,我們直接稱這些整數互質,也稱為 整集互質 (英語: setwise coprime )。以 { 6, 8, 9 } {\displaystyle \{6.8.9\}} 為例:
gcd 6, 8, 9 = gcd 6, 8, 9) = gcd 2, 9 = 1 {\displaystyle \gcd6.8.9=\gcd\gcd6.8.9)=\gcd2.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 7, 8, 9) = gcd 7, gcd 8, 9) = gcd 7, 9, 8) = 1 {\displaystyle \gcd7.8=\gcd7.9=\gcd8.9=1\Rightarrow \gcd7.8.9=\gcd\gcd7.8.9)=\gcd7,\gcd8.9)=\gcd\gcd7.9.8)=1}

兩兩互質是較為嚴格的互質,如果一個整數集合是兩兩互質的,它也必定是整集互質,但是整集互質不必然是兩兩互質,甚至可能兩兩皆不互質,例如 gcd 6, 15, 10 = 1 {\displaystyle \gcd6.15.10=1} ,是整集互質,但 gcd 6, 15 = 3 {\displaystyle \gcd6.15=3} 、 gcd 15, 10 = 5 {\displaystyle \gcd15.10=5} 、 gcd 10, 6 = 2 {\displaystyle \gcd10.6=2} ,任兩者皆不互質。

                                     

3. 性質

性质之一:整数a和b互质当且仅当存在整数x,y使得xa+yb=1。 或者,一般的,有存在整数x,y使得xa+yb=d,其中d是a和b的最大公因数。(贝祖等式)

                                     

4. 判别方法

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

5. 外部參考

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