本页使用了标题或全文手工转换

互質

维基百科,自由的百科全书
跳转至: 导航搜索

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

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

兩個整數 ab 互質,記為 ab

互質的例子[编辑]

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

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

整集互質與兩兩互質[编辑]

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

  • 這些整數的最大公因數是 1,我們直接稱這些整數互質[5],也稱為整集互質英语setwise coprime[6]。以 \{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

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

性質[编辑]

性质之一:整数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。故这两数互质。

外部參考[编辑]

參考來源[编辑]

  1. ^ Number Theory in Science and Communication, p.28
  2. ^ Wiktionary - coprime 以正整數為數域來定義互質。
  3. ^ ProofWiki > Definition:Coprime/Integers
  4. ^ ProofWiki > Integers Coprime to Zero
  5. ^ StackExchange > a problem with coprime numbers
  6. ^ Algebra II: Chapters 4-7, p.14