互素

在数论中，互素（英语：coprime，符号：⊥，又称互质）是指如果两个或两个以上的整数的最大公约数是1。依此定义：

• 如果数域是正整数$\mathbb {N^{+}}$，那么1与所有正整数互素。
• 如果数域是整数 $\mathbb {Z}$，那么1和-1与所有整数互素，而且它们是仅有与0互素的整数。

两个整数a与b互素，记为$a\perp b$，也可以依其定义写成$\gcd(a,b)=1$或$(a,b)=1$。

互素的例子

例如8与10的最大公约数是2，不互素。

又如7、10、13的最大公约数是1，因此互素。

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

整集互素与两两互素

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

• 这些整数的最大公约数是1，我们直接称这些整数互素，也称为整集互素（英语：setwise coprime）。以 $\{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$$

两两互素是较为严格的互素，如果一个整数集合是两两互素的，它也必定是整集互素，但是整集互素不必然是两两互素，甚至可能两两皆不互素，例如$\gcd(6,15,10)=1$，是整集互素，但$\gcd(6,15)=3$、$\gcd(15,10)=5$、$\gcd(10,6)=2$，任两者皆不互素。

性质

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

外部参考

• Final Answers > Number Theory（页面存档备份，存于互联网档案馆）
• 斯坦福大学离散结构讲义（页面存档备份，存于互联网档案馆）
• Abstract Algebra: An Inquiry Based Approach, p.45（页面存档备份，存于互联网档案馆）