什么叫卡迈克尔数
卡迈尔数的意义是什么？
卡迈克尔数是什么意思？
卡迈克尔数的定义是对于合数n，如果对于所有与n互质的正整数b，都有同余式b^(n-1)≡ 1 (mod n)成立，则称合数n为Carmichael数。
定理介绍：
每个Carmichael至少是三个不同素数的乘积。如561=3*11*17。
费马小定理(Fermat theorem)：
设p为一素数，对于任意整数a，有a(p-1)≡1 (mod p)。
假如p是质数，且gcd(a,p)=1，那么 a^(p-1) ≡1（mod p） 假如p是质数，且a,p互质，那么 a的(p-1)次方除以p的余数恒等于1。
伪素数的介绍？
伪素数是指满足素数的某种性质，但并非素数的数。最有名的伪素数是满足费马小定理的伪素数，即满足费马小定理，但其本身却不是素数。严格的定义是：n是一个伪素数，如果对于一个与其互素的自然数a，x 整除 ax-1 - 1，并称n是一个关于a的伪素数。最小的伪素数是341（=11×31，关于2）。如果n关于任何与其互素的数都是伪素数，则称n是绝对伪素数（或卡迈克尔数，来自找到第一个绝对伪素数的数学家罗伯特·丹尼·卡迈克尔）。最小的绝对伪素数是561。
关于卢卡斯数列和费波拿契数列恒式？
卢卡斯数列 卢卡斯数列 (Lucas Sequence) 和费波拿契数列 (Fibonnacci Sequence) 有莫大的关系。 先定义整数 P 和 Q 使 D = P2 - 4Q gt 0， 从而得一方程 x2 - Px Q = 0，其根为 a, b， 现定义卢卡斯数列为： Un(P,Q) = (an - bn) / (a-b) 及 Vn(P,Q) = an bn 其中 n 为非负整数，得 U0(P,Q) = 0、 U1(P,Q) = 1 、 V0(P,Q) = 2 、 V1(P,Q) = P、...... 我们有下列和卢卡斯数列相关的恒等式： Um n = UmVn - anbnUm-n 、 Vm n = VmVn - anbnVm-n Um 1 = P*Um - Q*Um-1 、 Vm 1 = P*Vm - Q*Vm-1 (取 n = 1) U2n = UnVn 、 V2n = Vn2 - Qn U2n 1 = Un 1Vn - Qn 、 V2n 1 = Vn 1Vn - PQn 若取 (P,Q) = (1,-1)，我们便有 Un 为费波拿契数， 即 0、 1、 1、 2、 3、 5、 8、 13、 21、 34、 55、 89、 144、 233、 377、 610、 987、 1597、 2584、 4141、 6765等。 而 Vn 为卢卡斯数 (Lucas Number)， 即 2、 1、 3、 4、 7、 11、18、 29、 47、 76、 123、 199、 322、 521、 843、 1364、 2207、 3571、 5781、 9349 等。 若取 (P,Q) = (2,-1)，我们便有 Un 为佩尔数 (Pell Number)， 即 0、 1、 2、 5、 12、 29、 70、 169、 408、 985、 2378、 5741等。 而 Vn 为佩尔 - 卢卡斯数 (Pell - Lucas Number) (详见另文《佩尔数列》)， 即 2、 2、 6、 14、 34、 82、 198、 478、 1154、 2786、 6726等。 此等全都是数学界很有名的数列。 卢卡斯数的性质 卢卡斯数 (简记 Ln) 有很多性质和费波拿契数很相似。如 Ln = Ln-1 Ln-2，其中不同的是 L1 = 1、 L2 = 3。 所以卢卡斯数有：1, 3, 4, 7, 11, 18, 29, 47, 76, 123, ...... (OEIS A000204)，当中的平方数只有 1 和 4，这是由哥恩 (John H. E. Cohn) 证明的。而素数，即卢卡斯素数 (Lucas Prime) 则有： 3, 7, 11, 29, 47, ...... 。当中现在知道最大的拟素数 (Probable Prime) 为 L574219 ，此数达 120005位之多。 我们有下列和卢卡斯数相关的恒等式： Ln2 - Ln-1Ln 1 = 5 (-1)n L12 L22 ...... Ln2 = LnLn 1 - 2 Lm n = (5FmFn LmLn) / 2 (式中的 Fn 为费波拿契数) Lm-n = (-1)n (LmLn - 5FmFn) / 2 Ln2 - 5Fn2 =4 (-1)n 若我们考虑的是拟素数，即那些通过费马小定理 (Fermat's Little Theorem) 逆命题测试的数，这有很大机会是素数，或可能是卡迈克尔数 (Carmichael Number)。那我们可把 n 推至 202667。但正因为 n 很大，要判断该数的素性的确不易。