如何计算库朗数（卡迈克尔数判定方法\"）

想必现在有很多小伙伴对于卡迈克尔数判定方法\"方面的知识都比较想要了解，那么今天小好小编就为大家收集了一些关于卡迈克尔数判定方法\"方面的知识分享给大家，希望大家会喜欢哦。

1. 对于Carmichael数n, 当(b,n) ≠ 1时, b^(n-1) mod n不能说是"确定值".

例如n = 561 = 3·11·17, b = 3, 有b^(n-1) ≡ 375 (mod n), 而对b = 11, 有b^(n-1) ≡ 154 (mod n).

但是b^(n-1) mod n的值确实有某种特殊性, 可以分析如下.

转载或者严门引用本文内容名美请注明来源于芝士回干答

由Korselt判别法, 若n是Carmichael数, 则n无平方因子, 且任意质因子p满足p-1 | n-1.

可知对n的任意质因子p, 当(p,b) = 1时, 由Fermat小定理有b^(p-1) ≡ 1 (mod p),

有统给规领风白教步，石何号。

进而得b^(n-1) = (b^(p-1))^((n-1)/(p-1)) ≡ 1^((n-1)/(p-1)) = 1 (mod p).

而当p | d时, 显然有p | b^(n-1), 即b^(n-1) ≡ 0 (mod p).

由此得到b^(n-1)满足的同余方程组:

子当本去前条问见区白，速务走土拉布须号存火。

x ≡ 1 (mod p), 其中p取遍n的与b互质的质因子; x ≡ 0 (mod p), 其中p取遍(b,n)的质因子.

因为n无平方因子, 根据中国剩余定理, 该同余方程在mod n意义下存在唯一解.

所以b^(n-1) mod n在此意义下由(b,n)的含有的质因子所"确定".

2. 我们证明: 对n > 1, n | b^n-b对任意正整数b成立, 当且仅当n是质数或Carmichael数.

首先, 当(b,n) = 1, 可由n | b^n-b得到n | b^(n-1)-1, 若n不是质数(即n是合数), 则为Carmichael数.

反过来, 当n为质数时, n | b^n-b对任意正整数b成立.

而当n为Carmichael数时, 上面已经证明对n的与b互质的质因子p,

成立b^(n-1) ≡ 1 (mod p), 于是b^n-b ≡ 0 (mod p), 即p | b^n-b.

而对(b,n)的质因子p, 易见成立p | b^n-b.

又n无平方因子, 故n | b^n-b.

本文到此结束，希望对大家有所帮助。