Funkcio φ

eta|dekstra|290px|La unuaj mil valoroj de *φ(n)*
En nombroteorio, la **eŭlera funkcio** *φ(n)* aŭ **eŭlera φ-funkcio** de pozitiva entjero *n* estas difinita kiel nombro de pozitivaj entjeroj malpli grandaj ol aŭ egalaj al *n* , kiuj estas reciproke primaj kun *n*.
Ekzemple, *φ(9)=6* pro tio, ke la ses nombroj 1, 2, 4, 5, 7 kaj 8 estas reciproke primaj kun 9.

La funkcio estas nomita omaĝe al svisa matematikisto Leonhard Euler, kiu studis ĝin.

La **eŭlera kuna φ-funkcio** de *n* estas difinita kiel *n-φ(n)*, la kvanto de pozitivaj entjeroj malpli grandaj ol aŭ egalaj al *n* , kiuj ne estas reciproke primaj kun *n*.

La φ funkcio estas grava ĉefe, ĉar ĝi donas la amplekson de la multiplika grupo de entjeroj module *n*. *φ(n)* estas ordo de grupo de unuoj de ringo \mathbb{Z}/n\mathbb{Z}. Ĉi tiu fakto, kaj ankaŭ teoremo de Lagrange koncerne al grupa teorio provizas pruvon de la eŭlera teoremo.

## Komputado de φ funkcio 
:*φ(1)=1*
:*φ(pk)=(p-1)p(k-1)* por prima *p*

*φ* estas multiplika funkcio, t.e. se *m* kaj *n* estas reciproke primaj, tiam *φ(mn) = φ(m)φ(n)*.

La valoro de *φ(n)* povas tial esti komputita per la fundamenta teoremo de aritmetiko: se

:n = p_1^{k_1} \cdots p_r^{k_r} ,

kie *pj* estas diversaj primoj, do

:\varphi(n)=(p_{1}-1)p_{1}^{k_{1}-1} \cdots (p_{r}-1)p_{r}^{k_{r}-1}.

Ĉi tiu la lasta formulo estas la eŭlera produto kaj estas ofte skribata kiel

:\varphi(n)=n\prod_{p|n}\left(1-\frac{1}{p}\right)

kun la produto ruliganta nur tra diversaj primoj *p* dividantaj na *n*.

Ekzemplo:

:\varphi(36)=\varphi\left(3^2 2^2\right)=36\left(1-\frac{1}{3}\right)\left(1-\frac{1}{2}\right)=36\cdot\frac{2}{3}\cdot\frac{1}{2}=12.

La diversaj primaj faktoroj de 36 estas 2 kaj 3; duono de entjeroj inter 1 kaj 36 estas dividebla per 2, restas 18; triono de tiuj estas dividebla per 3, restas 12 reciproke primaj kun 36. Ili estas 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35.

## Iuj valoroj de la funkcio 
Valoroj de la funkcio φ por 1 \leq \varphi(n) \leq 99 :

## Proprecoj 
Per inversiga formulo de Möbius eblas inversigi la sumon kaj ricevi la alian formulon por *φ(n)*:

:\varphi(n)=\sum_{d\mid n} d \cdot \mu(n/d)  ,

kie *μ* estas la kutima funkcio de Möbius difinita sur la pozitivaj entjeroj.

Laŭ eŭlera teoremo, se *a* estas reciproke prima kun *n* (alivorte *PGKD(a,n)=1*), do

: a^{\varphi(n)} \equiv 1\mod n .

Ĉi tio sekvas de teoremo de Lagrange kaj tio, ke *a* apartenas al la multiplika grupo de \mathbb{Z}/n\mathbb{Z} , se kaj nur se *a* estas reciproke prima kun *n*.

## Generante funkcioj 
La du sekvaj generantaj funkcioj aperas pro tio, ke

:\sum_{d|n} \varphi(d) = n.

Serio de Dirichlet kun *φ(n)* estas

:\sum_{n=1}^\infty \frac{\varphi(n)}{n^s}=\frac{\zeta(s-1)}{\zeta(s)} ,

kie *ζ(s)* estas la rimana ζ funkcio. Ĉi tio estas montrata sekve:

:\zeta(s) \sum_{f=1}^\infty \frac{\varphi(f)}{f^s} = \left(\sum_{g=1}^\infty \frac{1}{g^s}\right)\left(\sum_{f=1}^\infty \frac{\varphi(f)}{f^s}\right)
:\left(\sum_{g=1}^\infty \frac{1}{g^s}\right)\left(\sum_{f=1}^\infty \frac{\varphi(f)}{f^s}\right) = \sum_{h=1}^\infty \left(\sum_{fg=h} 1*\varphi(g)\right) \frac{1}{h^s}
:\sum_{h=1}^\infty \left(\sum_{fg=h} \varphi(g)\right) \frac{1}{h^s} = \sum_{h=1}^\infty \left(\sum_{d|h} \varphi(d)\right) \frac{1}{h^s}
:\sum_{h=1}^\infty \left(\sum_{d|h} \varphi(d)\right) \frac{1}{h^s} = \sum_{h=1}^\infty \frac{h}{h^s}
:\sum_{h=1}^\infty \frac{h}{h^s} = \zeta(s-1)

La serio de Lambert estas

:\sum_{n=1}^{\infty} \frac{\varphi(n) q^n}{1-q^n}= \frac{q}{(1-q)^2} ,

kiu konverĝas por *|q|\sum_{n=1}^{\infty} \frac{\varphi(n) q^n}{1-q^n} =
\sum_{n=1}^{\infty} \varphi(n) \sum_{r\ge 1} q^{rn} ,

kio estas

:
\sum_{k\ge 1} q^k \sum_{n|k} \varphi(n) =
\sum_{k\ge 1} k q^k = \frac{q}{(1-q)^2}.

## Kreskado de la funkcio 
La kreskado de *φ(n)* kiel funkcio de *n* estas interesa demando. Por malgrandaj *n* *φ(n)* estas signife pli malgranda ol *n*, Sed por grandaj *n* ĉi tio ne estas vera. Asimptote estas

:n^{1-\varepsilon}

por ĉiu donita *ε > 0* kaj *n > N(ε)*.

La funkcio *φ(n)/n* kalkuleblas jene:

:\varphi(n)/n=prod_{p|n}\left(1-\frac{1}{p}\right)

kun la produto rulanta tra ĉiuj primoj *p* dividantaj la entjeron *n*.

Pro tio la valoroj de *n* respektivaj al malgrandaj valoroj de la rilatumo estas tiuj, kiuj estas produtoj de komenca segmento de vico de ĉiuj primoj. El la prima teoremo sekvas, ke konstanto *ε* en la formulo pli supre povas pro tio esti anstataŭigita per

:C\,\log \log n/ \log n.

*φ(n)* estas ĝenerale proksime al *n* en averaĝa senco:

:\frac{1}{n^2} \sum_{k=1}^n \varphi(k)= \frac{3}{\pi^2} + \mathcal{O}\left(\frac{\log n }{n}\right) ,

kie *O* estas la granda O. Ĉi tiu ankaŭ diras, ke la probablo, ke du pozitiva entjeroj elektitaj hazarde de *{1, 2, ..., *n*}* estas reciproke primaj, estas proksimume 6/\pi^2 , kiam *n* strebas al malfinio. Rilatanta rezulto estas la averaĝa ordo de *φ(n)/n* , kiu estas

:\frac{1}{n} \sum_{k=1}^n \frac{\varphi(k)}{k} =
\frac{6}{\pi^2} + \mathcal{O}\left(\frac{\log n }{n}\right)

## Aliaj formuloj kun la funkcio 
:\varphi\left(n^m\right) = n^{m-1}\varphi(n)\text{ por }m\ge 1

:\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{ por }n>1

:\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

:\sum_{k=1}^n\frac{k}{\varphi(k)} = \mathcal{O}(n)

:\sum_{k=1}^n\frac{1}{\varphi(k)} = \mathcal{O}(\log(n))

:\sum_{1\le k\le n \atop (k,m)=1} 1 = n \frac {\varphi(m)}{m} +
\mathcal{O} \left ( 2^{\omega(m)} \right ) ,

kie *m* > 1 estas pozitiva entjero, kaj ω(*m*) estas kvanto de diversaj primaj faktoroj de *m*. (Ĉi tiuj formulaj kalkulas la nombron de pozitivaj entjeroj malpli grandaj ol aŭ egalaj al *n* kaj reciproke primaj kun *m*.)

### Neegalaĵoj 
Iuj neegalaĵoj kun la *φ(n)* estas:

:\varphi(n) > \frac {n} {e^\gamma\; \log \log n + \frac {3} {\log \log n}}

por *n>2*, kie γ estas eŭlera konstanto,

:\varphi(n) \ge \sqrt{\frac {n} {2} } por *n* > 0,

kaj

:\varphi(n) \ge \sqrt{n}\text{ por } n > 6.

Por primo *n*, *φ(n)=n-1*. Por komponita *n*:

:\varphi(n) \le n-\sqrt{n}

Por ĉiu *n* > 1:

:0

Por hazarda granda n, ĉi tiuj baroj ankoraŭ ne povas esti plibonigitaj, aŭ pli precize:

:\liminf \frac{\varphi (n)}{n}=0 \mbox{ and } \limsup \frac{\varphi (n)}{n}=1. 

Neegalaĵoj kun la *φ(n)* kaj la dividanta funkcio *σ*:

:\frac {6 n^2}{\pi^2} 1

## Vidu ankaŭ 
* Nombro, kiu ne estas valoro de eŭlera funkcio φ
* Nombro, kiu ne estas valoro de eŭlera kuna funkcio φ
* Nombro, kiu multfoje estas valoro de eŭlera funkcio φ
* Nombro, kiu multfoje estas valoro de eŭlera kuna funkcio φ
* Dividanta funkcio
* Funkcio de Carmichael

## Eksteraj ligiloj 
* Derivita logaritma funkcio de eŭlera funkcio  Miyata, Daisuke kaj Yamashita, Michinori
* http://les-mathematiques.u-strasbg.fr/phorum5/read.php?5,359275,359275  Nombro reciproke prima kun *q* en [1, n] de Olivier Bordellès
* http://www.t209.com/artikolo.php?arto_id=26 Kalkulo de ø(n) por nombroj supren ĝis 231
* Komputo de φ funkcio de Kirby Urner (2003)

Kategorio:Nombroteorio
Kategorio:Modula aritmetiko
Kategorio:Multiplikaj funkcioj
Kategorio:Leonhard Euler