互质

两个数仅有公因数1

数论中,互质(英语:coprime符号:⊥,又称互质)是指如果两个或两个以上的整数最大公因数是1[1]。依此定义:

  • 如果数域正整数,那么1与所有正整数互质。
  • 如果数域整数 ,那么1和-1与所有整数互质[2],而且它们是仅有与0互质的整数[3]

两个整数ab互质,记为,也可以依其定义写成

互质的例子

例如8与10的最大公因数是2,不互质。

又如7、10、13的最大公因数是1,因此互质。

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

整集互质与两两互质

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

  • 这些整数的最大公因数是1,我们直接称这些整数互质[4],也称为整集互质(英语:setwise coprime[5]。以  为例: 
  • 这些整数是两两互质的(英语:pairwise coprime)。以 为例: 

两两互质是较为严格的互质,如果一个整数集合是两两互质的,它也必定是整集互质,但是整集互质不必然是两两互质,甚至可能两两皆不互质,例如 ,是整集互质,但   ,任两者皆不互质。

性质

性质之一:整数ab互质,当且仅当存在整数x,y,使得 

一般地,存在整数x,y使得 ,其中dab的最大公因数(贝祖等式)。

判别方法

  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. [2014-10-19]. (原始内容存档于2014-10-19). 
  2. ^ ProofWiki > Definition:Coprime/Integers. [2014-10-19]. (原始内容存档于2020-03-27). 
  3. ^ ProofWiki > Integers Coprime to Zero. [2014-10-19]. (原始内容存档于2020-03-27). 
  4. ^ StackExchange > a problem with coprime numbers. [2014-10-19]. (原始内容存档于2020-09-21). 
  5. ^ Algebra II: Chapters 4-7, p.14

外部参考