互素(Coprime integers，亦译为互质)指整数不存在共同的素数因子。正如我们在 3.3 节 中看到的，互素对于我们非常重要。因为在模运算中，涉及互素的计算与非互素的计算非常不同(参见 3.3.2 节)
判断两个整数是否互质的简单方法是将这两个数依次与小于其的素数相除，判断它们是否共享素因子。另一种判断互素的方法是计算两个整数的最大公约数，当最大公约数为 1 时，则互素。显然，计算最大公约数的方法更加高效。
示例 5
再次考虑 示例 4。正如我们所看到的，12 和 5 的最大公约数为 1 。这说明 12 和 5 是互素的，因为除了 1 没有其他共同的素数因子。