跳至內容

卡邁克爾函數

維基百科,自由的百科全書

卡邁克爾函數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).