Java 中的卡迈克尔数

在本节中，我们将学习卡迈克尔数是什么，并创建Java 程序来检查给定数字是否为卡迈克尔数。卡迈克尔数程序经常出现在 Java 编码面试和学术中。

卡迈克尔数

一个复合数 n，对于所有与 n 互质的整数 'a'（即 a^n-1≡ 1(mod n)），它都表现为伪素数，称为绝对伪素数或卡迈克尔数。

该数字必须满足卡迈克尔数的充要条件。如果 n 满足以下条件，则 n 是绝对伪素数或卡迈克尔数：

• n 是复合数（可以由两个更小的正整数相乘得到正整数），并且是无平方因子数（n 不能被任何素数的平方整除）。
• 对于所有与 n 互质的整数 a，a^n-1≡1(mod n)

它们非常罕见。请注意，每个卡迈克尔数都是至少三个不同素数的乘积。

换句话说，我们可以说，一个复合数 n 是卡迈克尔数，当且仅当对于所有与 'n' 互质的数，我们有：

让我们看看如何计算卡迈克尔数。

卡迈克尔数的例子

让我们检查561是否是卡迈克尔数。

如果该数字满足上述两个条件，则意味着 561 是卡迈克尔数。

1. 考虑 561=3*11*17，因此 561 是一个复合数，满足第一个条件。
2. 根据第二个条件，对于所有与 (a, n) = 1 的整数 'a'，都有 a⁵⁶⁰ ≡1(mod 561)。

令 GCD (a, 561) = 1

断言：a⁵⁶⁰ ≡ 1 mod 561

假设 'a' 与561互质。所以，a 不是 3、11 或 17 的倍数。现在，尽管 561 不是素数，但它仍然满足我们即将展示的正式定理的结论，即'a' 的 560 次幂模 561 等于 1。

现在，3、11和17是素数，因此根据费马小定理，'a' 的平方模 3 等于1，'a' 的第 10 次幂模 11 等于1，'a' 的第 16 次幂模 17 等于1。

现在我们来处理第一个同余式，'a' 的平方模 3 等于1，我们将两边都提高到相应的幂，以得出'a' 的第 80 次幂模 3 等于1。我们可以对下一个同余式做同样的事情。我们可以取'a' 的第 10 次幂模 11 等于1，并将两边都提高到 8 次幂，以计算'a' 的第 80 次幂模 11 等于1。最后，我们可以取最后一个同余式 'a' 的第 16 次幂模 17 等于1，并将两边都提高到 5 次幂，以计算'a' 的第 80 次幂模 17 等于1。

现在，我们将使用中国剩余定理(CRT) 将所有内容结合起来。

我们知道 'a' 的 80 次幂模 3、11 和 17 都等于 1。因此，我们可以得出结论，'a' 的第 80 次幂模 561 等于1。因此，根据 CRT：

我们将在这里再执行一步，即取 'a' 的第 80 次幂同余于1 模 561。将两边都提高到 7 次幂，我们发现 'a' 的 560 次幂同余于1 模 561。因此：

所以，尽管561不是素数，但它仍然满足费马小定理的结论（对于任何与 n 互质的数 'a'，a 的 n-1 次幂模 n 等于 1）。

前几个卡迈克尔数是561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841。

算法

1. 读取一个整数 n。
2. 从 2 迭代到 n，并在每次迭代中检查gcd(b, n) = 1和b^{n - 1} mod n = 1。如果所有迭代都满足给定条件，则打印“n 是卡迈克尔数”，否则打印“n 不是卡迈克尔数”。
3. 停止

卡迈克尔数 Java 程序

CheckCarmichaelNumber.java

输出 1

Enter the Number: 10585
10585 is a Carmichael number.

输出 2

Enter the Number: 564
564 is not a Carmichael number.