跳至內容

初等數論/數論函數

維基教科書,自由的教學讀本

數論函數

[編輯]

數論函數是指定義域為正整數的函數。比如階乘,約數個數

約數個數函數

[編輯]

約數個數的計算公式1:

這種方式是求出約數個數最樸素的方式,也是最繁瑣的方式,因為這就是約數個數的定義。我們一般用下面說的公式2來計算約數個數:

,則。其中是素數,均為正整數。

這個公式很好推導,只是運用了一些簡單的乘法原理。對於任意一個的素因子,我們可以選擇種情況種的一個來作為一個一個約數的約數。由乘法原理,就可以推導出公式2。這個公式在計算約數個數時應該是最常用、最方便、最快速的。儘管它仍然很繁瑣。

約數和函數

[編輯]

約數和的計算公式1:

沒錯,這就是約數和的定義。計算約數個數一般也用下面的公式2:

,則

這裡我們給出詳細的推導過程。

首先我們考慮當只有兩個素因子時的情況。設這兩個素因子為,且次數分別為。如果我們選擇作為的標準分解形式,那我們先定死不動,那麼標準分解形式種含有的約數的和應該為

同樣地,對其它做其它相同的事,再將作為公因式提取出來,就可以得到:

現在,我們使用上面這種簡化版的問題的結論,將其推廣,就可以得到公式2。

歐拉函數

[編輯]

歐拉函數定義(公式1):

從上面的式子可以看出,歐拉函數計算的是在小於的正整數中與互質的數的個數。公式2如下:

的標準分解形式是,則

由這個數論函數可以推導出費馬-歐拉定理,再推出著名的費馬小定理。先看歐拉定理。我們定義一種數組叫做模的簡化剩餘系(以下簡稱縮系),其中含有個元素。在這些元素中任意取兩個數都不模同餘,且每個數都與互質。

假設有一個模的縮系,則對於一個正整數滿足。故也是一個模的縮系。所以。因為縮系裡的每一個元素都與互質,所以它們的乘積也與互質。所以我們可以得到

這就是費馬-歐拉定理。不難發現時,,即費馬小定理。