互素（Coprime，或称互质）是数论中一个基础且重要的概念，它在纯数学领域至关重要，并且在各种应用领域中也有广泛而深远的影响，从密码学到音乐理论中的和声，互素数的应用广泛而深远。
互素数的定义互素数的定义很简单：两个整数如果只有 1 作为它们的公因数，即它们的最大公因数（Greatest Common Divisor, GCD）为 1，那么这对整数就是互素的。
用符号表示为：若 gcd(a,b) = 1，则称整数 a 和 b 互素。例如，39 和 22 是互素的，因为 gcd(39,22) = 1。
»» 可进一步阅读之前发布《揭秘寻找最大公约数的古老算法——辗转相除法》 一文
了解互素数的定义是理解接下来讨论的更多概念和应用的基础。
互素数与分数的化简在化简分数 a/b 至最简形式时，互素数概念的实用性就显现出来。
如果 gcd(a,b) = d，则 a 和 b 可以写成 a = a₀ × d 与 b = b₀ × d 的形式，而 a/b 就可以化简为 a₀/b₀。其中，a₀ 和 b₀ 互素，确保了分数为最简形式。
除法规则互素数具有一个有用的性质：若乘积 ab 能被整数 c 整除，并且 b 与 c 互素，则 a 必定能被 c 整除。
证明概述：
设 ab = ck，其中 k 为某整数。
- 互素条件：a 和 b 互素意味着 gcd(a,b) = 1，它们没有共同的素因数。
- 乘积可被整除：既然 c 能整除 ab，且 a 和 b 无共同素因数，c 的素因数必须全部来源于 a。
- 素因数分布：因此，a 包含 c 的所有素因数及其指数，以保证 c 能整除 ab。
- 结论：c 必然能整除 a。
一个有趣的性质是：如果两个互素整数的乘积是平方数 c²，那么这两个整数也都是平方数。
▌示例：
以整数 16 和 9 为例：
a = 16 = 4² b = 9 = 3² a ⋅ b = 16 ⋅ 9 = 144 = 12²
这里，a 和 b 互素且它们的乘积 144 是平方数 c²，其中 c = 12。
▌证明思路
平方数的定义是，其素因数分解中所有指数均为偶数。如果 a ⋅ b = c² 且 a 和 b 互素，则 c² 的每个素因数的指数必须是偶数，且必须来源于 a 或 b。因此，a 和 b 各自的素因数指数也都是偶数，所以它们也是平方数。
判断两个数是否互素的方法这里有一些判别两个数是否互质的简易方法：
- 两个不同的素数一定互质。 由于素数只有 1 和它本身作为因数，因此两个不同的素数没有共同的因数（除了 1）。
- 一个素数和另一个不为它倍数的数互质。 如果一个数是素数，另一个数不是它的倍数，这意味着后者不能被前者整除。例如，3 是素数，而 10 不是 3 的倍数（10 不能被 3 整除），所以它们互质： gcd(3, 10) = 1
- 1 和任何一个自然数都互质。 因为 1 只有一个因数，即它自己，使得它与任何自然数互质。
- 相邻两个自然数互质。 相邻的两个自然数的差是 1，因为任何数都不能除 1 以外的数整除，所以它们必定互质。
- 相邻两个奇数互质。 如前所述，相邻的奇数之差为 2，而任何大于 1 的因数都不能整除 2，因此这两个奇数互质。例如，49 和 51 互质： gcd(49, 51) = 1
- 两数都是合数（二数差较大），较小数的所有素因数，都不是较大数的因数，则这两个数互质。 其实就是说，如果两个数没有共同的素因数，那么互质。例如，357 和 715 都是合数。357 的素因数是 3、7 和 17，而这些都不是 715 的因数（715 = 5 × 11 × 13），因此： gcd(357, 715) = 1
- 两数都是合数（二数差较小），这两数之差的所有素因数都不是较小数的因数，这两个数互质。 利用了两数之差的素因数性质来判断互素。如果两个合数的差的素因数不是较小数的任何因数，那么这两个数互质。例如，85 和 78 的差是 7，它是素数，而 7 不是 78 的因数，所以它们互质： gcd(85, 78) = 1
- 两数都是合数，较大数除以较小数的余数（大于"1"）的所有素因数，都不是较小数的因数，则两数互质。 实为辗转相除法的一个直接应用。例如，考虑 462 和 221，当你用 462 除以 221，余数是 20，它的素因数是 2 和 5。因为 2 和 5 都不是 221 的
