Apskatīt Eilera funkcija izejas kodu

Skaitļu teorijā '''Eilera funkcija''' <math>\varphi(n)</math> 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 <math>\varphi(1) = 1</math>, jo 1 ir savstarpējs pirmskaitlis ar sevi. Tālāk, piemēram, <math>\varphi(9) = 6</math>, 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 [[Leonards Eilers|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 ''fī''.

== Eilera funkcijas aprēķināšana ==

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

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

:<math>n = p_1^{k_1} \cdot ... \cdot p_r^{k_r}</math>

kur ''p''<sub>''i''</sub> ir dažādi pirmskaitļi, tad

:<math>\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}</math>.
Pēdējo formulu var uzrakstīt arī šādi:

:<math>\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)</math>.

== Skatīt arī ==

* [[Eilera teorēma]]

[[Kategorija:Skaitļu teorija]]