卡迈克尔函数(OEIS数列A002322)满足,其中a与n互质。
定义
当n为1、2、4、奇质数的次幂、奇质数的次幂的两倍时为欧拉函数,当n为2,4以外的2的次幂时为它的一半。
欧拉函数有
由算术基本定理,正整数n可写为质数的积
对于所有n, 是它们最小公倍数:
例子
证明
证明当a与n互质时,满足
由费马小定理得
由数学归纳法得 成立,这是一般情况。
由数学归纳法得当 时, 成立。
[1]
原根的充要条件
证明 为存在模n原根的充要条件。
而 当且仅当 ( )
必要性
,若 ,则不存在阶为 的模n元素,即不存在原根。[1]
λ原根
阶为 的模n元素为λ原根。模n的λ原根的个数参见 A111725。
当 时,3、5为模n的λ原根,因而所有模8余3或5的数都是模n的λ原根。
- [1]
- [1]
多项式除法
余式: [2]
参见
参考资料