IBM Ponder This #279 · 2021 年 7 月

费马小定理指出，若 $n$ 是质数，则 $a^{n-1}\equiv 1(\text{mod }n)$。随机选择 $a\in {\mathbb{Z}}_n^{\ast }$ 并计算 $a^{n-1}$，若不等于 1，便能判定 $n$ 为合数。

但卡迈克尔数虽为合数，却对每个 $a\in {\mathbb{Z}}_n^{\ast }$ 都满足 $a^{n-1}\equiv 1(\text{mod }n)$。Miller–Rabin 检验在计算 $a^{n-1}$ 时，额外检查单位平方根：若 $b^2\equiv 1(\text{mod }n)$，则 $b$ 是模 $n$ 的单位平方根。对每个 $n$，都有平凡根 $1,n-1$；只有 $n$ 为合数时才可能有其他根。

最小卡迈克尔数为 $561=3\cdot 11\cdot 17$，模 561 的最大非平凡单位平方根为 494。

任务：找出一个至少一百位的卡迈克尔数 $n$，并求模 $n$ 的最大非平凡单位平方根。按以下格式提供数、全部质因数和根：

n
p1, p2, ..., pn
b

附加问题：还要求是 primary Carmichael number，定义为 $n$ 对每个质因数 $p$ 满足：把 $n$ 写成 $p$ 进制时，$n$ 的各位数字之和恰好为 $p$。这个性质能推出 $n$ 是卡迈克尔数。

例如 $1729=7\cdot 13\cdot 19$ 在七进制为 5020，数字和 7；十三进制为 A30，数字和 10+3+0=13；十九进制为 4F0，数字和 4+15+0=19。

解答

认真尝试后再打开

待补充。