Eulerin φ-funktio

Eulerin φ-funktio $\phi (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 $\phi (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

$\phi (n)=n\prod _{p|n}(1-\frac{1}{p})$

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

$\phi (10)=10\prod _{p|10}(1-\frac{1}{p})=10(1-\frac{1}{2})(1-\frac{1}{5})=4$,

koska vain alkuluvut 2 ja 5 jakavat luvun 10.

Ominaisuuksia

• $\sum _{d\mid n}\frac{{\mu }^2(d)}{\phi (d)}=\frac{n}{\phi (n)}$

• $\sum _{\genfrac{}{}{0ex}{}{1\le k\le n}{(k,n)=1}}k=\frac{1}{2}n\phi (n)\text{ jos }n>1$

• $\phi (n)=\sum _{d\mid n}d\cdot \mu \left(\frac{n}{d}\right)=n\sum _{d\mid n}\frac{\mu (d)}{d}$

• $\phi (n)=\sum _{k=1}^n\gcd (k,n)\cos 2\pi \frac{k}{n}$

• $\sum _{k=1}^n\phi (k)=\frac{1}{2\zeta (2)}{n}^2+𝒪(n\log n)$

missä ζ on Riemannin zeeta-funktio. Kaavasta seuraa approximaatio $\phi (n)\approx n\frac{3}{{\pi }^2}.$

• $\sum _{k=1}^n\phi (k)=\frac{1}{2}(1+\sum _{k=1}^n\mu (k){\lfloor \frac{n}{k}\rfloor }^2)$

• $\sum _{k=1}^n\frac{\phi (k)}{k}=\sum _{k=1}^n\frac{\mu (k)}{k}\lfloor \frac{n}{k}\rfloor =\frac{6}{{\pi }^2}n+𝒪((\log n{)}^{2/3}(\log \log n{)}^{4/3})$

• $\sum _{k=1}^n\frac{k}{\phi (k)}=\frac{315\zeta (3)}{2{\pi }^4}n-\frac{\log n}{2}+𝒪((\log n{)}^{2/3})$

• $\sum _{k=1}^n\frac{1}{\phi (k)}=\frac{315\zeta (3)}{2{\pi }^4}(\log n+\gamma -\sum _{p\text{ alkuluku}}\frac{\log p}{p^2-p+1})+𝒪\left(\frac{(\log n{)}^{2/3}}{n}\right)$

(missä γ on Eulerin vakio).

• $\sum _{\genfrac{}{}{0ex}{}{1\le k\le n}{(k,m)=1}}1=n\frac{\phi (m)}{m}+𝒪\left(2^{\omega (m)}\right),$

missä m > 1 on positiivinen kokonaisluku ja ω(m) on m:n eri alkulukujakajien määrä.

Epäyhtälöitä φ-funktiolle

φ-funktiolle on voimassa

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

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

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

Kaikille $n>1$:

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

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

$\mathrm{lim\; inf}\frac{\phi (n)}{n}=0\text{ ja }\mathrm{lim\; sup}\frac{\phi (n)}{n}=1.$

Menonin identiteetti

$\sum _{\stackrel{1\le k\le n}{\gcd (k,n)=1}}\gcd (k-1,n)=\phi (n)d(n)$

Lähteet

• Malline:Kirjaviite