卡迈克尔函数

2022-03-01 09:12:50 浏览数 (1)

1. 定义

卡迈克尔函数定义为：当 nnn 为 1、2、4、奇质数的次幂、奇质数的次幂的两倍时为欧拉函数，当 nnn 为 2、4 以外的 2 的次幂时为欧拉函数的一半。

begin{array}{c} lambda(n) = left{ begin{aligned} phi(n) ,, & ,, n = 1,2,3,4,5,6,7,9,10,cdots \ {1 over 2}phi(n) ,, & ,, n = 8,16,32,64,128,256,cdots end{aligned} right. end{array}

2. 性质

  • 对于任意整数 n，由算数基本定理（整数唯一分解定理）：

，则卡迈克尔函数满足：

begin{array}{c} lambda(n) = lcm[lambda(p_1^{a_1}),lambda(p_2^{a_2}),cdots,lambda(p_w^{a_w})] end{array}

证明：根据欧拉函数性质，有phi(p^k) = p^{k-1}(p-1)，（ p 为质数）

serverless

0 人点赞