Eulerin φ-funktio
on niiden positiivisten kokonaislukujen
määrä, joille pätee syt(n, k) = 1 eli n ja k ovat suhteellisia alkulukuja.[1] Esimerkiksi
, 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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b3a75d2161f16f4e8d9552706a09be3b5c755729)
eli tuloon otetaan tekijöiksi kaikki alkuluvut
jotka jakavat luvun
.[2] Esimerkiksi
,
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)}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a910cb8792ad63d84754b85bbf7beeb19c2c43f2)
![{\displaystyle \sum _{1\leq k\leq n \atop (k,n)=1}\!\!k={\frac {1}{2}}n\varphi (n){\text{ jos }}n>1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6bf0c3cee28c1be58b3c67c749cf980a7378b22e)
![{\displaystyle \varphi (n)=\sum _{d\mid n}d\cdot \mu \left({\frac {n}{d}}\right)=n\sum _{d\mid n}{\frac {\mu (d)}{d}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2d61ea7c02655c58a8b54128ec20686bab907385)
![{\displaystyle \varphi (n)=\sum \limits _{k=1}^{n}\gcd(k,n)\cos {2\pi {\frac {k}{n}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ac9cb96f94a71c8a1ec6458bc22c199bc354e843)
![{\displaystyle \sum _{k=1}^{n}\varphi (k)={\frac {1}{2\zeta (2)}}n^{2}+{\mathcal {O}}(n\log n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/82455d7cfd588f229794da6dac6a04b5ea51872a)
missä ζ on Riemannin zeeta-funktio. Kaavasta seuraa approximaatio
![{\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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2f0e41fe0e6e41b4a6e119eeb8ad0b065ea1353f)
![{\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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d32271c7407016cc07233658234cb1b0220a7932)
![{\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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/09c6d780b35f2e456feca61c88dfab1504562453)
![{\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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c7ffc813d1178e1c7e9039ba448090cb5ffe44d4)
(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),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3d84a9f75a377b489f28c2657b390b0d9279cc7b)
missä m > 1 on positiivinen kokonaisluku ja ω(m) on m:n eri alkulukujakajien määrä.
Epäyhtälöitä φ-funktiolle
φ-funktiolle on voimassa
, kaikille n>6.
kun n > 2, missä
on Eulerin vakio.
kun n > 0,
Kaikille
:
![{\displaystyle 0<{\frac {\varphi (n)}{n}}<1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d13ba44888602ee31e996330cc81da1fcf9793e1)
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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/46ec08d89046e247b5e7aca3a70543124120a612)
Menonin identiteetti
![{\displaystyle \sum _{\stackrel {1\leq k\leq n}{\gcd(k,n)=1}}\gcd(k-1,n)=\varphi (n)d(n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b9832fcf50b324b4eb867acc9d8e0125304559f6)
Lähteet
- Rosen, Kenneth H.: Elementary Number Theory and Its Applications. Reading, Massachusetts: Addison-Wesley, 1984. ISBN 0-201-06561-4. (englanniksi)
Viitteet
- ↑ Rosen, s. 161
- ↑ Rosen, s. 169
Tämä matematiikkaan liittyvä artikkeli on tynkä. Voit auttaa Wikipediaa laajentamalla artikkelia.