跳转到内容

卡邁克爾函數

维基百科,自由的百科全书

卡邁克爾函数OEIS數列A002322)满足,其中a与n互质

定义

[编辑]

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

欧拉函数有

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

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

例子

[编辑]

证明

[编辑]

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

费马小定理

数学归纳法成立,这是一般情况。

数学归纳法得当时,成立。 [1]

原根的充要条件

[编辑]

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

当且仅当

必要性

[编辑]

,若,则不存在阶为的模n元素,即不存在原根。[1]

λ原根

[编辑]

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

时,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. [2015-07-29]. ISBN 1144400341. (原始内容存档于2020-12-02). 
  2. ^ 黄嘉威. 多项式除法解高次同余. 数学学习与研究. 2015, (9): 第104页 [2017-09-24]. (原始内容存档于2020-10-20).