如何构造两个互素的整数？

先规定：如果两个整数 a ， b 互素 ，则写 \text{gcd}\left( a,b \right)=1 .

下面给出一些方法来弄出 互素对 。

【 Ⅰ 】

使用定理：在 \mathbb{Z} 中，若 \text{gcd}\left( a,b \right)=1 ，则有 \text{gcd}\left( a,a+b \right)=1 .

这时，我们选定两个数 a_{0} ， b_{0} ，且 \text{gcd}\left( a_{0},b_{0} \right)=1 ，那么让 a_{n}=a_{0} ， b_{n}=a_{0}+b_{n-1} \left( \forall n \right) ，那么依定理就会有： \text{gcd}\left( a_{n},b_{n} \right)=1 \left( \forall n \right) .

【 Ⅱ 】

我们知，任意两个相邻的 Fibonacci 数是 互素 的，因此我们只需要给出 Fibonacci 数生成的公式即可： \forall n\in \mathbb{N} ，有

F_{n}=\frac{1}{\sqrt{5}}\left( \left( \frac{\sqrt{5}+1}{2} \right)^{n}-\left( \frac{1-\sqrt{5}}{2} \right)^{n} \right)

那么则知， \forall n\in \mathbb{N} ， \text{gcd}\left( F_{n+1},F_{n} \right)=1 .

【 Ⅲ 】

在自然数序列中，任意两个相邻数是互素的。

即 \forall n\in \mathbb{N} ， \text{gcd}\left( n,n+1 \right)=1 .

【 Ⅳ 】

我们有定理：

\Large \text{gcd}\left( a,b \right)=1\\\Large \Leftrightarrow\left( \exists s\in \mathbb{Z}\right)\left( \exists t\in \mathbb{Z} \right)\left( sa+tb=1 \right)

因此，我们可以先找出一对 互素对 a 和 b ，这时自然可以依此定理推出 sa+tb=1 .

这时，易知： \Large \left( sa+tb \right)^{2}\\\Large =\left( sa \right)^{2}+\left( tb \right)^{2}+2satb\\\Large =s^{2}a^{2}+t^{2}b^{2}+2satb\\\Large =\left( s^{2}a+2stb \right)a+\left( t^{2}b \right)b\\\Large =1

因此可知， a 和 b 是使得此式成立的整数，从而依定理说：

\left( s^{2}a+2stb \right) 和 \left( t^{2}b \right) 是 互素 的。

而且由于 \Large sa+tb=1\\\Large \Rightarrow\left( sa+tb \right)^{2}=1\\\Large \Rightarrow\left( s^{2}a+2stb \right)a+\left( t^{2}b \right)b=1 可以看出它总是保持 Aa+Bb=1 的形式，所以总可以依此继续生成更多的 互素对 ，且可以一直生成下去。

【 Ⅴ 】

由于 p 作为 素数 时，只会 整除 形如 np 的整数，因此，只要让数字处于 np+a （其中 a 可以取 1,2,...,p-1 ）的状态，这样自然就会有 \text{gcd}\left( p,np+a \right)=1 .

【 Ⅵ 】

对于任意两个数字，两者在进行素因数分解时，会看到里面全是素数，我们会对素数进行匹对查看，若两者之间一个相同的素因数都没有，那么这两个数字必然 互素 。

因此，采用这个方法，拿出有足够数字的素数表，将它一分为二，称为集 A 与集 B ；

然后，用集 A 中的素数随意拼凑，使用乘法弄出 m_{1} ；

再用集 B 中的素数随意拼凑，使用乘法弄出 m_{2} ；

则可知必有 \text{gcd}\left( m_{1},m_{2} \right)=1 .

用此方法也是可以弄出大量的互素对。

【 Ⅶ 】

使用定理：

正整数 2^{a}-1 与 2^{b}-1 互素 \Leftrightarrow a 与 b 互素 .

这样，先找出一对互素对 a 和 b ，那么依定理自然知 \text{gcd}\left( 2^{a}-1,2^{b}-1 \right)=1 .

这种方法也一样可以简单地弄出大量的互素对。

【 Ⅷ 】

使用一个定理：

同余方程 ax\equiv1\left( \text{mod}m \right) 有解 \Leftrightarrow \text{gcd}\left( a,m \right)=1 .

因此，只要满足 m|ax-1 ，则自然有 \text{gcd}\left( a,m \right)=1 .

一个简单的利用它的方法就是：由于我们知 3×7=21 ，所以只要 a 使用 3 作个位， x 使用 7 作个位，那么再选 m=10 即可。

当然还有基于 1×1=1 和 9×9=81 这些可用。

【 Ⅸ 】

我们有定理：

若 p 为 素数 ，则 \left( p-1 \right)!\equiv-1\left( \text{mod}p \right) .

那么我们将它自乘一次，则得：

\left( p-1 \right)!·\left( p-1 \right)!\equiv\left( -1 \right)·\left( -1 \right)\left( \text{mod}p \right)

也即得： \left( p-1 \right)!·\left( p-1 \right)!\equiv1\left( \text{mod}p \right) .

利用【 Ⅷ 】的定理，显然可知 \left( p-1 \right)!x\equiv1\left( \text{mod}p \right) 是有解的。

因此知 \text{gcd}\left( \left( p-1 \right)!,p \right)=1 .

从而可生成大量的 互素对 。

【 Ⅹ 】

在环 \mathbb{Z}_{m} 中， \bar{a} 是可逆元 \Leftrightarrow a 与 m 互素。

所以可以查看在 \mathbb{Z}_{m} 中是否存在元素 \bar{b} 能使 \bar{a} 处于 \bar{a}*\bar{b}=\bar{1} ，若存在，则说明 \text{gcd}\left( a,m \right)=1 。从而找到 互素对 。

而且由于 \mathbb{Z}_{m} 中每一个元素要么是可逆元，要么是零因子，二者必居其一且只居其一。

因此也可证 \bar{a} 不是零因子，那么也就可知 \bar{a} 是可逆元，从而说 \text{gcd}\left( a,m \right)=1 .

【 ⅩⅠ 】

使用欧拉定理：

设 m 是一个正整数， a 是一个整数且 \text{gcd}\left( a,m \right)=1 ，那么 a^{\phi\left( m \right)}\equiv1\left( \text{mod}m \right) .

其中 \phi\left( m \right) 是欧拉函数，它记录的是 \mathbb{Z}_{m} 中的可逆元的个数，且 \phi\left( m \right)=m·\prod_{i=1}^{n}\left( 1-\frac{1}{p_{i}} \right) ，

（ p_{1},p_{2},...,p_{n} 是 m 的所有素因数，且每个素因数只取一个来计算）.

这时，我们只要把 a^{\phi\left( m \right)} 拆成 a^{t}·a^{s} ，那么自然说明 a^{t}·x\equiv1\left( \text{mod}m \right) 是有解的，从而依【 Ⅷ 】的定理则知 \text{gcd}\left( a^{t},m \right)=1 ，这也是大量的 互素对 。

【 ⅩⅡ 】

同样是使用这个定理：

\Large \text{gcd}\left( a,b \right)=1\\\Large \Leftrightarrow\left( \exists s\in \mathbb{Z}\right)\left( \exists t\in \mathbb{Z} \right)\left( sa+tb=1 \right)

实际上，这里的 a ， b ， s ， t 是没有太大区别的，导致我们可以这样做：

先随便选取 t 和 b 相乘，然后把 tb 移到等式的右边，则变成： sa=1-tb ，这就说明，只需要把 1-tb 进行分解（分解成 s 和 a 的 乘积 ，不需要素因数分解）就行了，【分解出来的这些序对： \left( s,t \right) ， \left( s,b \right) ， \left( a,t \right) ， \left( a,b \right) 就都是 互素对 了】。

为了简单，可以先让 t 为负数， b 为正数，那么移到右边后，右边得数则为正数，从而 s 和 a 也就都选正数即可。

例如，先选 t=-18 ， b=98 ，那么两者相乘再移到右边则是：

1-tb=1+18×98=1765 ，

然后自然也知 sa=1-tb=1765 ，随便分解一下就知道 5×353=1765 ，所以可以选 s=5\wedge a=353 ，依上面所述，则知 \left( 5,-18 \right) ， \left( 5,353 \right) ， \left( 353,-18 \right) ， \left( 353,98 \right) 就均是 互素对 了，而且也完全可以 把负号全去掉 ，从而 \left( 5,18 \right) ， \left( 353,18 \right) 也成为 互素对 。