Remove ads

卡邁克爾函數OEIS數列A002322)滿足,其中a與n互質

定義

當n為1、2、4、奇質數的次冪、奇質數的次冪的兩倍時為歐拉函數,當n為2,4以外的2的次冪時為它的一半。

歐拉函數有

算術基本定理,正整數n可寫為質數的積

對於所有n,是它們最小公倍數

Remove ads

例子

證明

證明當a與n互質時,滿足

費馬小定理

數學歸納法成立,這是一般情況。

數學歸納法得當時,成立。 [1]

Remove ads

原根的充要條件

證明為存在模n原根的充要條件。

若且唯若

Remove ads

必要性

,若,則不存在階為的模n元素,即不存在原根。[1]

Remove ads

λ原根

階為的模n元素為λ原根。模n的λ原根的個數參見OEISA111725

時,3、5為模n的λ原根,因而所有模8餘3或5的數都是模n的λ原根。

[1]
[1]
Remove ads

多項式除法

餘式: [2]

Remove ads

參見

參考資料

Wikiwand in your browser!

Seamless Wikipedia browsing. On steroids.

Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.

Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.

Remove ads