如果两个整数的最大公约数为1,就称它们互素,也称互质。等价地,不存在大于1的整数能同时整除它们。互素描述的是数与数之间的关系,而非某个数本身的性质:例如,8和15互素,尽管它们都不是素数。这一概念在数论中十分基础,尤其是在整除、分数和同余的研究中。
定义与基本示例
整数 a 和 b 互素,当且仅当
gcd(a,b)=1.
有时也使用记号 a⊥b,不过直接写出最大公约数为1的条件可以避免歧义。
例如:
- 8 和 15,它们的正因数中只有1是共有的。
- 14 和 25,尽管二者都是合数。
- 任意两个不同的素数。
- 任意两个相邻整数,因为 n 和 n+1 的公约数必定整除它们的差,即1。
相比之下,14和21不互素,因为它们的最大公约数是7。
正负号不影响互素关系:
gcd(a,b)=gcd(∣a∣,∣b∣).
因此,−8 和15互素。整数1和 −1 都与任意整数互素。由于 gcd(a,0)=∣a∣,零只与1和 −1 互素。按照通常的约定 gcd(0,0)=0,零与自身不互素。
算术基本定理给出了另一种刻画:两个非零整数互素,当且仅当它们的绝对值没有共同的素因数。
裴蜀等式
裴蜀等式给出了互素关系的一种核心刻画:
gcd(a,b)=1⟺ax+by=1for some integers x,y.
也就是说,两个整数互素,当且仅当1可以表示为它们的整数线性组合。
例如,
2⋅8−1⋅15=1,
这就证明了8和15互素。
其中一个方向显而易见:如果 ax+by=1,那么 a 和 b 的每个公约数都整除等式左边,因而也整除1。反方向可以由扩展欧几里得算法得出,该算法能构造出符合条件的系数 x 和 y。
更一般地,若 d=gcd(a,b),则存在整数 x,y,使得
因此,当 a,b 不全为零时,一次丢番图方程
有整数解,当且仅当 gcd(a,b) 整除 c。当 a 和 b 互素时,右边的 c 可以取任意整数。
互素性的判定
欧几里得算法无需进行素因数分解,就能判定两个整数是否互素。它反复使用
gcd(a,b)=gcd(b,a−qb)
直到余数为零。最后一个非零余数就是最大公约数。
例如,
351211=2⋅12+11,=1⋅11+1,=11⋅1.
所以 gcd(35,12)=1。逆向回代可得
1=12−11=12−(35−2⋅12)=3⋅12−35.
带余除法的步数至多按两个正整数输入中较小者的对数增长。因此,即使对于很大的整数,计算最大公约数也是切实可行的。
一个基本的不变性是:对于任意整数 k,都有
gcd(a,b)=1⟺gcd(a,b+ka)=1
将一个数的整数倍加到另一个数上,不会改变它们的公约数。
多个整数:整体互素与两两互素
对于有限个整数 a1,…,ak,必须区分两种不同的条件。
整体互素是指
gcd(a1,…,ak)=1.
即不存在大于1的整数能整除其中的每一个数。
两两互素是指
gcd(ai,aj)=1whenever i=j.
即任意两个数都必须互素。
两两互素必然意味着整体互素,但对于三个或更多整数,反之不成立。例如,
gcd(6,10,15)=1,
但它们两两的最大公约数分别为2、3和5。相比之下,8、9和25两两互素。
在涉及多个整数时,英文术语“mutually coprime”和“relatively prime”的用法并不总是一致。明确写出最大公约数条件,或使用“两两”一词,可以消除歧义。
关于整除的推论
在整除问题的论证中,互素关系使我们能够将因子分开处理。一个重要结果是欧几里得引理的互素形式:
gcd(a,b)=1,a∣bc⟹a∣c.
要证明这一点,只需将裴蜀等式 ax+by=1 两边乘以 c:
acx+bcy=c.
左边的两项都能被 a 整除,因此 c 也能被 a 整除。
其他有用的推论包括:
如果 a∣c、b∣c,且 a,b 互素,那么 ab∣c。
如果 a 分别与 b 和 c 互素,那么它也与 bc 互素。
对于正整数 r,s,有
gcd(a,b)=1⟺gcd(ar,bs)=1.
对于正整数 a,b,有
gcd(a,b)lcm(a,b)=ab.
因此,它们互素等价于它们的最小公倍数为 ab。
分数与模算术
最简分数
当 b=0 时,分数 a/b 为最简分数的条件是
gcd(a,b)=1.
将分子和分母同时除以它们的最大公约数,就能得到这样的表示。
每个有理数都能唯一地表示为 a/b,其中 b>0,且 a,b 互素。要保证唯一性,必须约定分母为正。
模逆元
在模算术中,当 n≥2 时,整数 a 存在模 n 的乘法逆元,当且仅当
gcd(a,n)=1.
事实上,逆元就是满足
ax≡1(modn),
的整数 x,这等价于存在某个整数 y,使得方程 ax+ny=1 成立。
例如,
3⋅12−35=1
表明3是12模35的逆元。
模 n 的可逆剩余类在乘法下构成一个群。这些剩余类的个数由欧拉函数 φ(n) 给出。欧拉定理指出,只要 gcd(a,n)=1,就有
aφ(n)≡1(modn)
同余方程组
中国剩余定理指出,如果各个正模数两两互素,那么相应的同余方程组有解,且解在模这些模数的乘积的意义下唯一。
对于两个模数,若 gcd(m,n)=1,则无论余数 r,s 为何,同余方程组
x≡r(modm),x≡s(modn)
在模 mn 的意义下都恰有一个解类。如果模数不互素,就需要额外的相容条件。
正整数中互素的频率
在两个分量都不超过 N 的正整数有序对中,互素数对所占的比例趋于
N→∞limN2#{(a,b):1≤a,b≤N, gcd(a,b)=1}=π26≈0.607927.
这一极限密度常被描述为随机选取的两个正整数互素的概率。严格来说,全体正整数上不存在均匀概率分布;这里指的是从 {1,…,N} 中独立、均匀地选取两个数,然后取 N 趋于无穷时的极限。
这一结果可以用黎曼ζ函数表示:
ζ(2)1=p prime∏(1−p21).
对于每个素数 p,相应的因子排除了两个分量都能被 p 整除的数对。从有限多个素数过渡到无穷乘积,需要严格的论证。
更一般地,对于 k≥2,最大公约数为1的有序 k 元组所占比例的极限为 1/ζ(k)。当 k>2 时,这并不是两两互素的 k 元组的密度。
历史与代数背景
互素数已见于欧几里得的《几何原本》,其中将它们刻画为只能以单位作为公度量的数。欧几里得算法则为判定这种关系提供了经典的计算方法。
在抽象代数中,裴蜀等式所给出的刻画将整数的互素关系与理想联系起来。在整数环中,
gcd(a,b)=1⟺(a)+(b)=Z.
因此,由 a 和 b 生成的理想就是整个环。
这一表述可以推广为其他环中互素理想的概念。不过,在整数中,“没有共同的非单位因子”与“生成整个环”是等价的,而这种等价关系并非在每个环中都成立,因此推广互素概念时需要谨慎。