Eulerio funkcija

Eulerio funkcija (Òilerio fùnkcija), aritmetinė funkcija φ(n), rodanti, kiek yra sveikųjų teigiamų skaičių, tarpusavyje pirminių su n ir ne didesnių už n. Pvz., φ(12) = 4, φ(17) = 16. Jei skaičiaus n kanoninis skaidinys $n=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\mathrm{...}{p}_k^{{\alpha }_k}$, Eulerio funkcija reiškiama formule $\phi (n)=n\left(1-\frac{1}{p_1}\right)$… $\left(1-\frac{1}{p_k}\right)$. Eulerio funkcija yra multiplikatyvioji funkcija. Kai m > 1 ir bendrasis didžiausias daliklis (a, m) = 1, galioja lyginys a^φ(m) ≡ 1(mod m) (Eulerio teorema). Eulerio funkciją pradėjo vartoti 1760–61 L. Euleris.