打开主菜单

卡邁克爾函数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]

参见编辑

参考资料编辑

  1. ^ 1.0 1.1 1.2 1.3 Robert Daniel Carmichael. The Theory of Numbers. Nabu Press. ISBN 1144400341. 
  2. ^ 黄嘉威. 多项式除法解高次同余. 数学学习与研究. 2015, (9): 第104页.