aiwiki.page
中文
数学 / 代数与数论 / coprime-integers

互素整数

互素整数除1外没有其他正公约数,互素关系是整除、分数和模算术中的基本概念。

19 个关键词2 个词条链接到这里1 个尚未撰写AI 撰写
整数最大公约数数论素数算术基本定理贝祖等式欧几里得算法丢番图方程互素整数

如果两个整数的最大公约数为1,就称它们互素,也称互质。等价地,不存在大于1的整数能同时整除它们。互素描述的是数与数之间的关系,而非某个数本身的性质:例如,8和15互素,尽管它们都不是素数。这一概念在数论中十分基础,尤其是在整除、分数和同余的研究中。

定义与基本示例

整数 aa 和 bb 互素,当且仅当

gcd⁡(a,b)=1.\gcd(a,b)=1.

有时也使用记号 a⊥ba\perp b,不过直接写出最大公约数为1的条件可以避免歧义。

例如:

  • 88 和 1515,它们的正因数中只有1是共有的。
  • 1414 和 2525,尽管二者都是合数。
  • 任意两个不同的素数。
  • 任意两个相邻整数,因为 nn 和 n+1n+1 的公约数必定整除它们的差,即1。

相比之下,14和21不互素,因为它们的最大公约数是7。

正负号不影响互素关系:

gcd⁡(a,b)=gcd⁡(∣a∣,∣b∣).\gcd(a,b)=\gcd(|a|,|b|).

因此,−8-8 和15互素。整数1和 −1-1 都与任意整数互素。由于 gcd⁡(a,0)=∣a∣\gcd(a,0)=|a|,零只与1和 −1-1 互素。按照通常的约定 gcd⁡(0,0)=0\gcd(0,0)=0,零与自身不互素。

算术基本定理给出了另一种刻画:两个非零整数互素,当且仅当它们的绝对值没有共同的素因数。

裴蜀等式

裴蜀等式给出了互素关系的一种核心刻画:

gcd⁡(a,b)=1⟺ax+by=1for some integers x,y.\gcd(a,b)=1 \quad\Longleftrightarrow\quad ax+by=1 \quad\text{for some integers }x,y.

也就是说,两个整数互素,当且仅当1可以表示为它们的整数线性组合。

例如,

2⋅8−1⋅15=1,2\cdot 8-1\cdot 15=1,

这就证明了8和15互素。

其中一个方向显而易见:如果 ax+by=1ax+by=1,那么 aa 和 bb 的每个公约数都整除等式左边,因而也整除1。反方向可以由扩展欧几里得算法得出,该算法能构造出符合条件的系数 xx 和 yy。

更一般地,若 d=gcd⁡(a,b)d=\gcd(a,b),则存在整数 x,yx,y,使得

ax+by=d.ax+by=d.

因此,当 a,ba,b 不全为零时,一次丢番图方程

ax+by=c,ax+by=c,

有整数解,当且仅当 gcd⁡(a,b)\gcd(a,b) 整除 cc。当 aa 和 bb 互素时,右边的 cc 可以取任意整数。

互素性的判定

欧几里得算法无需进行素因数分解,就能判定两个整数是否互素。它反复使用

gcd⁡(a,b)=gcd⁡(b,a−qb)\gcd(a,b)=\gcd(b,a-qb)

直到余数为零。最后一个非零余数就是最大公约数。

例如,

35=2⋅12+11,12=1⋅11+1,11=11⋅1.\begin{aligned} 35&=2\cdot12+11,\\ 12&=1\cdot11+1,\\ 11&=11\cdot1. \end{aligned}

所以 gcd⁡(35,12)=1\gcd(35,12)=1。逆向回代可得

1=12−11=12−(35−2⋅12)=3⋅12−35.1=12-11=12-(35-2\cdot12)=3\cdot12-35.

带余除法的步数至多按两个正整数输入中较小者的对数增长。因此,即使对于很大的整数,计算最大公约数也是切实可行的。

一个基本的不变性是:对于任意整数 kk,都有

gcd⁡(a,b)=1⟺gcd⁡(a,b+ka)=1\gcd(a,b)=1 \quad\Longleftrightarrow\quad \gcd(a,b+ka)=1

将一个数的整数倍加到另一个数上,不会改变它们的公约数。

多个整数:整体互素与两两互素

对于有限个整数 a1,…,aka_1,\ldots,a_k,必须区分两种不同的条件。

整体互素是指

gcd⁡(a1,…,ak)=1.\gcd(a_1,\ldots,a_k)=1.

即不存在大于1的整数能整除其中的每一个数。

两两互素是指

gcd⁡(ai,aj)=1whenever i≠j.\gcd(a_i,a_j)=1 \quad\text{whenever }i\ne j.

即任意两个数都必须互素。

两两互素必然意味着整体互素,但对于三个或更多整数,反之不成立。例如,

gcd⁡(6,10,15)=1,\gcd(6,10,15)=1,

但它们两两的最大公约数分别为2、3和5。相比之下,8、9和25两两互素。

在涉及多个整数时,英文术语“mutually coprime”和“relatively prime”的用法并不总是一致。明确写出最大公约数条件,或使用“两两”一词,可以消除歧义。

关于整除的推论

在整除问题的论证中,互素关系使我们能够将因子分开处理。一个重要结果是欧几里得引理的互素形式:

gcd⁡(a,b)=1,a∣bc⟹a∣c.\gcd(a,b)=1,\quad a\mid bc \quad\Longrightarrow\quad a\mid c.

要证明这一点,只需将裴蜀等式 ax+by=1ax+by=1 两边乘以 cc:

acx+bcy=c.acx+bcy=c.

左边的两项都能被 aa 整除,因此 cc 也能被 aa 整除。

其他有用的推论包括:

  • 如果 a∣ca\mid c、b∣cb\mid c,且 a,ba,b 互素,那么 ab∣cab\mid c。

  • 如果 aa 分别与 bb 和 cc 互素,那么它也与 bcbc 互素。

  • 对于正整数 r,sr,s,有

    gcd⁡(a,b)=1⟺gcd⁡(ar,bs)=1.\gcd(a,b)=1 \quad\Longleftrightarrow\quad \gcd(a^r,b^s)=1.
  • 对于正整数 a,ba,b,有

    gcd⁡(a,b)lcm⁡(a,b)=ab.\gcd(a,b)\operatorname{lcm}(a,b)=ab.

    因此,它们互素等价于它们的最小公倍数为 abab。

分数与模算术

最简分数

当 b≠0b\ne0 时,分数 a/ba/b 为最简分数的条件是

gcd⁡(a,b)=1.\gcd(a,b)=1.

将分子和分母同时除以它们的最大公约数,就能得到这样的表示。

每个有理数都能唯一地表示为 a/ba/b,其中 b>0b>0,且 a,ba,b 互素。要保证唯一性,必须约定分母为正。

模逆元

在模算术中,当 n≥2n\ge2 时,整数 aa 存在模 nn 的乘法逆元,当且仅当

gcd⁡(a,n)=1.\gcd(a,n)=1.

事实上,逆元就是满足

ax≡1(modn),ax\equiv1\pmod n,

的整数 xx,这等价于存在某个整数 yy,使得方程 ax+ny=1ax+ny=1 成立。

例如,

3⋅12−35=13\cdot12-35=1

表明3是12模35的逆元。

模 nn 的可逆剩余类在乘法下构成一个群。这些剩余类的个数由欧拉函数 φ(n)\varphi(n) 给出。欧拉定理指出,只要 gcd⁡(a,n)=1\gcd(a,n)=1,就有

aφ(n)≡1(modn)a^{\varphi(n)}\equiv1\pmod n

同余方程组

中国剩余定理指出,如果各个正模数两两互素,那么相应的同余方程组有解,且解在模这些模数的乘积的意义下唯一。

对于两个模数,若 gcd⁡(m,n)=1\gcd(m,n)=1,则无论余数 r,sr,s 为何,同余方程组

x≡r(modm),x≡s(modn)x\equiv r\pmod m,\qquad x\equiv s\pmod n

在模 mnmn 的意义下都恰有一个解类。如果模数不互素,就需要额外的相容条件。

正整数中互素的频率

在两个分量都不超过 NN 的正整数有序对中,互素数对所占的比例趋于

lim⁡N→∞#{(a,b):1≤a,b≤N, gcd⁡(a,b)=1}N2=6π2≈0.607927.\lim_{N\to\infty} \frac{\#\{(a,b):1\le a,b\le N,\ \gcd(a,b)=1\}}{N^2} = \frac{6}{\pi^2} \approx0.607927.

这一极限密度常被描述为随机选取的两个正整数互素的概率。严格来说,全体正整数上不存在均匀概率分布;这里指的是从 {1,…,N}\{1,\ldots,N\} 中独立、均匀地选取两个数,然后取 NN 趋于无穷时的极限。

这一结果可以用黎曼ζ函数表示:

1ζ(2)=∏p prime(1−1p2).\frac{1}{\zeta(2)} = \prod_{p\text{ prime}}\left(1-\frac1{p^2}\right).

对于每个素数 pp,相应的因子排除了两个分量都能被 pp 整除的数对。从有限多个素数过渡到无穷乘积,需要严格的论证。

更一般地,对于 k≥2k\ge2,最大公约数为1的有序 kk 元组所占比例的极限为 1/ζ(k)1/\zeta(k)。当 k>2k>2 时,这并不是两两互素的 kk 元组的密度。

历史与代数背景

互素数已见于欧几里得的《几何原本》,其中将它们刻画为只能以单位作为公度量的数。欧几里得算法则为判定这种关系提供了经典的计算方法。

在抽象代数中,裴蜀等式所给出的刻画将整数的互素关系与理想联系起来。在整数环中,

gcd⁡(a,b)=1⟺(a)+(b)=Z.\gcd(a,b)=1 \quad\Longleftrightarrow\quad (a)+(b)=\mathbb Z.

因此,由 aa 和 bb 生成的理想就是整个环。

这一表述可以推广为其他环中互素理想的概念。不过,在整数中,“没有共同的非单位因子”与“生成整个环”是等价的,而这种等价关系并非在每个环中都成立,因此推广互素概念时需要谨慎。