fbpx
维基百科

卡邁克爾函數

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

卡邁克爾函數, 卡邁克爾函数λ, displaystyle, lambda, oeis數列a002322, 满足aλ, modn, displaystyle, lambda, equiv, pmod, 其中a与n互质, 目录, 定义, 例子, 证明, 原根的充要条件, 必要性, λ原根, 多项式除法, 参见, 参考资料定义, 编辑当n为1, 奇质数的次幂, 奇质数的次幂的两倍时为欧拉函数, 当n为2, 4以外的2的次幂时为它的一半, 12φ, displaystyle, lambda, begin, cases, . 卡邁克爾函数l n displaystyle lambda n OEIS數列A002322 满足al n 1 modn displaystyle a lambda n equiv 1 pmod n 其中a与n互质 目录 1 定义 2 例子 3 证明 4 原根的充要条件 4 1 必要性 5 l原根 6 多项式除法 7 参见 8 参考资料定义 编辑当n为1 2 4 奇质数的次幂 奇质数的次幂的两倍时为欧拉函数 当n为2 4以外的2的次幂时为它的一半 l n f n n 1 2 3 4 5 6 7 9 10 11 13 14 17 19 22 23 25 26 27 29 12f n n 8 16 32 64 128 256 displaystyle lambda n begin cases varphi n amp n 1 2 3 4 5 6 7 9 10 11 13 14 17 19 22 23 25 26 27 29 dots dfrac 1 2 varphi n amp n 8 16 32 64 128 256 dots end cases nbsp 欧拉函数有f pk pk 1 p 1 displaystyle varphi p k p k 1 p 1 nbsp 由算术基本定理 正整数n可写为质数的积n p1a1p2a2 pw n aw n displaystyle n p 1 a 1 p 2 a 2 dots p omega n a omega n nbsp 对于所有n l n displaystyle lambda n nbsp 是它们最小公倍數 l n lcm l p1a1 l p2a2 l pw n aw n displaystyle lambda n operatorname lcm lambda p 1 a 1 lambda p 2 a 2 dots lambda p omega n a omega n nbsp 例子 编辑l 8 2 displaystyle lambda 8 2 nbsp 72 1 mod8 displaystyle 7 2 equiv 1 pmod 8 nbsp 证明 编辑证明当a与n互质时 满足al n 1 modn displaystyle a lambda n equiv 1 pmod n nbsp 由费马小定理得ap 1 1 hp displaystyle a p 1 1 hp nbsp apk 1 p 1 1 hpk displaystyle a p k 1 p 1 1 hp k nbsp apk p 1 1 hpk p 1 hppk 1 1 h0pk 1 displaystyle a p k p 1 1 hp k p 1 h p p k 1 dots 1 h 0 p k 1 nbsp 由数学归纳法得apk 1 p 1 1 modpk displaystyle a p k 1 p 1 equiv 1 pmod p k nbsp 成立 这是一般情况 a 1 2h displaystyle a 1 2h nbsp a2 1 4h h 1 1 8Ch 12 displaystyle a 2 1 4h h 1 1 8C h 1 2 nbsp a2k 2 1 2kh displaystyle a 2 k 2 1 2 k h nbsp a2k 1 1 2kh 2 1 2k 1 h 2k 1h2 displaystyle a 2 k 1 1 2 k h 2 1 2 k 1 h 2 k 1 h 2 nbsp 由数学归纳法得当k 3 displaystyle k geq 3 nbsp 时 a2k 2 1 mod2k displaystyle a 2 k 2 equiv 1 pmod 2 k nbsp 成立 1 原根的充要条件 编辑证明f n l n displaystyle varphi n lambda n nbsp 为存在模n原根的充要条件 而f n l n displaystyle varphi n lambda n nbsp 当且仅当n 1 2 4 pk 2pk displaystyle n 1 2 4 p k 2p k nbsp p 2 displaystyle p neq 2 nbsp 必要性 编辑 f n l n displaystyle varphi n geq lambda n nbsp 若f n gt l n displaystyle varphi n gt lambda n nbsp 则不存在阶为f n displaystyle varphi n nbsp 的模n元素 即不存在原根 1 l原根 编辑阶为l n displaystyle lambda n nbsp 的模n元素为l原根 模n的l原根的个数参见 nbsp A111725 当n 2k k gt 2 displaystyle n 2 k k gt 2 nbsp 时 3 5为模n的l原根 因而所有模8余3或5的数都是模n的l原根 32k 3 22 1 2k 3 1 2k 1 2kI displaystyle 3 2 k 3 2 2 1 2 k 3 1 2 k 1 2 k I nbsp 1 52k 3 1 22 2k 3 1 2k 1 2kI displaystyle 5 2 k 3 1 2 2 2 k 3 1 2 k 1 2 k I nbsp 1 多项式除法 编辑 p k xl p 1 x k displaystyle prod p k x lambda prod p 1 x k nbsp 余式 xl p k n k i 1k 1 i 1 n i 1i 1 n kk i xl p k i k mod p k displaystyle x lambda prod p k n k equiv sum i 1 k 1 i 1 binom n i 1 i 1 binom n k k i x lambda prod p k i k pmod prod p k nbsp 2 参见 编辑卡邁克爾數参考资料 编辑 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 黄嘉威 多项式除法解高次同余 数学学习与研究 2015 9 第104页 2017 09 24 原始内容存档于2020 10 20 取自 https zh wikipedia org w index php title 卡邁克爾函數 amp oldid 67193204, 维基百科,wiki,书籍,书籍,图书馆,

文章

,阅读,下载,免费,免费下载,mp3,视频,mp4,3gp, jpg,jpeg,gif,png,图片,音乐,歌曲,电影,书籍,游戏,游戏。