Eulerin φ-funktio

Eulerin φ-funktio $\varphi(n)$ on niiden positiivisten kokonaislukujen $k\le n$ määrä, joille pätee syt(n, k) = 1 eli n ja k ovat suhteellisia alkulukuja. Esimerkiksi $\varphi(10)=4$, koska lukua 10 pienemmistä positiivisista kokonaisluvuista ainoastaan luvut 1,3,7 ja 9 ovat suhteellisia alkulukuja luvun 10 kanssa.

φ-funktion arvo voidaan laskea kaavasta

$\varphi(n)=n\prod_{p|n}\left(1-\frac{1}{p}\right)$

eli tuloon otetaan tekijöiksi kaikki alkuluvut $p$ jotka jakavat luvun $n$. Esimerkiksi

$\varphi(10)=10\prod_{p|10}\left(1-\frac{1}{p}\right)=10\left(1-\frac{1}{2}\right)\left(1-\frac{1}{5}\right)=4$,

koska vain alkuluvut 2 ja 5 jakavat luvun 10.

Epäyhtälöitä φ-funktiolle

φ-funktiolle on voimassa

$\varphi(n)\ge \sqrt{n}$, kaikille n>6.

$\varphi(n) > \frac {n} {e^\gamma\; \log \log n + \frac {3} {\log \log n}}$ kun n > 2, missä $\gamma$ on Eulerin vakio.

$\varphi(n) \ge \sqrt{\frac {n} {2} }$ kun n > 0,

Kaikille $n>1$:

$0<\frac{\varphi (n)}{n}<1$

Suurillekaan luvuille n, yllä olevaa epäyhtälöä ei voi parantaa. Tarkemmin sanoen:

$\liminf \frac{\varphi (n)}{n}=0 \mbox{ ja } \limsup \frac{\varphi (n)}{n}=1.$