Eilera funkcija

Vikipēdijas lapa
Pārlēkt uz: navigācija, meklēt

Skaitļu teorijā Eilera funkcija \varphi(n) no naturāla skaitļa n ir visu to naturālo skaitļu skaits, kas nepārsniedz n un ir savstarpēji pirmskaitļi ar n. Turklāt \varphi(1) = 1, jo 1 ir savstarpējs pirmskaitlis ar sevi. Tālāk, piemēram, \varphi(9) = 6, jo seši skaitļi 1, 2, 4, 5, 7 un 8 ir savstarpēji pirmskaitļi ar 9.

Funkcija ir nosaukta Šveices matemātiķa L. Eilera vārdā, kas to ir pētījis. Dažreiz to sauc arī par Eilera fī funkciju, jo to parasti apzīmē ar grieķu burtu .

Eilera funkcijas aprēķināšana[labot šo sadaļu | labot pirmkodu]

Nav grūti saprast, ka ja p ir pirmskaitlis, tad \varphi(p) = p-1. Tālāk, jebkuram naturālam k un pirmskaitlim p \varphi(p^k) = (p-1)p^{k-1}. Vēl vairāk, \varphi ir multiplikatīva funkcija. Tas nozīmē, ka ja m un n ir savstarpēji pirmskaitļi, tad \varphi(mn) = \varphi(m) \varphi(n).

Tāpēc \varphi(n) vērtību pie n>1 var aprēķināt, izmantojot aritmētikas pamatteorēmu: ja

n = p_1^{k_1} \cdot ... \cdot p_r^{k_r}

kur pi ir dažādi pirmskaitļi, tad

\varphi(n)=(p_1-1)p_1^{k_1-1} \times (p_2-1)p_2^{k_2-1} \times ... \times(p_r-1)p_r^{k_r-1}.

Pēdējo formulu var uzrakstīt arī šādi:

\varphi(n)= n(p_1-1)p_1^{-1} \times (p_2-1)p_2^{-1} \times ... \times(p_r-1)p_r^{-1}=n \cdot \prod_{p|n} \left( 1-\frac{1}{p} \right).

Skatīt arī[labot šo sadaļu | labot pirmkodu]