互质(英文:coprime,符号:⊥,又称互素、relatively prime、mutually prime、co-prime)。在数论中,如果两个或两个以上的整数的最大公约数是 1,则称它们为互质。依此定义:

两个整数 ab 互素,记为 ab

互素的例子

例如 810 的最大公约数是 2,不是 1,因此它们并不互质。
又例如 7, 10, 13 的最大公约数是 1,因此它们互质。

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

整集互素与两两互素

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

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}
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)=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. ^ Eaton, James S. Treatise on Arithmetic. 1872. May be downloaded from: http://archive.org/details/atreatiseonarit05eatogoog
  2. ^ Number Theory in Science and Communication, p.28
  3. ^ Wiktionary - coprime 以正整数为数域来定义互素。
  4. ^ ProofWiki > Definition:Coprime/Integers
  5. ^ ProofWiki > Integers Coprime to Zero
  6. ^ StackExchange > a problem with coprime numbers
  7. ^ Algebra II: Chapters 4-7, p.14

外部参考

www.zuoweixin.com
问题反馈联系QQ:暂无联系方式,也可发qq邮箱。