卡邁克爾函數

卡邁克爾函数满足，其中a与n互质。

定义
当n为1、2、4、奇质数的次幂、奇质数的次幂的两倍时为欧拉函数，当n为2,4以外的2的次幂时为它的一半。

欧拉函数有

由算术基本定理，正整数n可写为质数的积

对于所有n，是它们最小公倍數：

例子

证明
证明当a与n互质时，满足

由费马小定理得

由数学归纳法得成立，这是一般情况。

由数学归纳法得当时，成立。

原根的充要条件
证明为存在模n原根的充要条件。

而当且仅当（）

必要性
，若，则不存在阶为的模n元素，即不存在原根。

λ原根
阶为的模n元素为λ原根。模n的λ原根的个数参见。

当时，3、5为模n的λ原根，因而所有模8余3或5的数都是模n的λ原根。

多项式除法

余式：

参见
卡邁克爾數

参考资料

同余
函数