Eulerin φ-funktio

Wikipedia
Loikkaa: valikkoon, hakuun

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.

Ominaisuuksia[muokkaa | muokkaa wikitekstiä]

  • \sum_{d \mid n} \frac{\mu^2(d)}{\varphi(d)} = \frac{n}{\varphi(n)}
  • \sum_{1\le k\le 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=\frac6{\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\le k\le 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[muokkaa | muokkaa wikitekstiä]

φ-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.

Menonin identiteetti[muokkaa | muokkaa wikitekstiä]


\sum_{\stackrel{1\le k\le n}{ \gcd(k,n)=1}} \gcd(k-1,n)
=\varphi(n)d(n)
Tämä matematiikkaan liittyvä artikkeli on tynkä. Voit auttaa Wikipediaa laajentamalla artikkelia.