Eulerin φ-funktio

Eulerin φ-funktio ${\displaystyle \varphi (n)}$ on niiden positiivisten kokonaislukujen ${\displaystyle k\leq n}$ määrä, joille pätee syt(n, k) = 1 eli n ja k ovat suhteellisia alkulukuja.^[1] Esimerkiksi ${\displaystyle \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

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

eli tuloon otetaan tekijöiksi kaikki alkuluvut ${\displaystyle p}$ jotka jakavat luvun ${\displaystyle n}$.^[2] Esimerkiksi

${\displaystyle \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

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

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

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

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

• ${\displaystyle \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 ${\displaystyle \varphi (n)\approx n{\frac {3}{\pi ^{2}}}.}$

• ${\displaystyle \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)}$

• ${\displaystyle \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)}$

• ${\displaystyle \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)}$

• ${\displaystyle \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).

• ${\displaystyle \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

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

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

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

Kaikille ${\displaystyle n>1}$:

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

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

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

Menonin identiteetti

${\displaystyle \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)

Viitteet