Eulerin φ-funktio

Eulerin φ-funktio $\varphi (n)$ on niiden positiivisten kokonaislukujen $k\leq 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.

Ominaisuuksia

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

• $\sum _{1\leq k\leq n \atop (k,n)=1}\!\!k={\frac {1}{2}}n\varphi (n){\text{ jos }}n>1$

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

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

• $\sum _{k=1}^{n}\varphi (k)={\frac {1}{2\zeta (2)}}n^{2}+{\mathcal {O}}(n\log n)$

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

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

• $\sum _{k=1}^{n}{\frac {\varphi (k)}{k}}=\sum _{k=1}^{n}{\frac {\mu (k)}{k}}\left\lfloor {\frac {n}{k}}\right\rfloor ={\frac {6}{\pi ^{2}}}n+{\mathcal {O}}\left((\log n)^{2/3}(\log \log n)^{4/3}\right)$

• $\sum _{k=1}^{n}{\frac {k}{\varphi (k)}}={\frac {315\zeta (3)}{2\pi ^{4}}}n-{\frac {\log n}{2}}+{\mathcal {O}}\left((\log n)^{2/3}\right)$

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

(missä γ on Eulerin vakio).

• $\sum _{1\leq k\leq n \atop (k,m)=1}1=n{\frac {\varphi (m)}{m}}+{\mathcal {O}}\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

$\varphi (n)\geq {\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)\geq {\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.$

Menonin identiteetti

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

Lähteet

• Rosen, Kenneth H.: Elementary Number Theory and Its Applications. Reading, Massachusetts: Addison-Wesley, 1984. ISBN 0-201-06561-4. (englanniksi)