Funkcio φ: Malsamoj inter versioj
| [nekontrolita versio] | [nekontrolita versio] |
Enhavo forigita Enhavo aldonita
e roboto aldono de: ro:Indicatorul lui Euler |
Neniu resumo de redakto |
||
Linio 1:
[[Dosiero:EulerPhi.PNG|thumb|right|La unuaj mil valoroj de ''φ(n)'']]
En [[nombroteorio]], la '''eŭlera φ funkcio''' ''φ(n)'' de [[pozitiva entjero]] ''n'' estas difinita kiel kvanto de pozitivaj entjeroj malpli grandaj ol aŭ egala al ''n'' , kiuj estas [[interprimo]]j al ''n''.
Ekzemple, ''φ(9)=6'' pro tio, ke la ses nombroj 1, 2, 4, 5, 7 kaj 8 estas interprimoj al 9.
La funkcio estas nomita pro [[svislando|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ŭ egala al ''n'' , kiu estas ne interprimoj al ''n''.
La φ funkcio estas grava ĉefe, ĉar ĝi donas la amplekson de la multiplika [[grupo (matematiko)|grupo]] de entjeroj [[modula aritmetiko|module]] ''n''. ''φ(n)'' estas ordo de grupo de [[unuo (ringa teorio)|unuoj]] de [[ringo (algebro)|ringo]] <math>\mathbb{Z}/n\mathbb{Z}</math>. Ĉi tiu fakto, kaj ankaŭ [[teoremo de Lagrange (grupa teorio)|teoremo de Lagrange]] koncerne al grupa teorio provizas pruvon de la [[eŭlera teoremo]].
==Komputado de φ funkcio==
Linio 14:
:''φ(p<sup>k</sup>)=(p-1)p<sup>(k-1)</sup>'' por prima ''p''
''φ'' estas [[multiplika funkcio]], ĉi tio estas, ke se ''m'' kaj ''n'' estas interprimoj do ''φ(mn) = φ(m)φ(n)''.
La valoro de ''φ(n)'' povas tial esti komputita per la [[fundamenta teoremo de aritmetiko]]: se
:<math>n = p_1^{k_1} \cdots p_r^{k_r}</math> ,
kie ''p<sub>j''</sub> estas diversaj [[primo]]j, do
Linio 77:
Per [[inversiga formulo de Möbius]] eblas inversigi la sumon kaj ricevi la alian formulon por ''φ(n)'':
:<math>\varphi(n)=\sum_{d\mid n} d \cdot \mu(n/d) </math> ,
kie ''μ'' estas la kutima [[funkcio de Möbius]] difinita sur la pozitivaj entjeroj.
Linio 83:
Laŭ [[eŭlera teoremo]], se ''a'' estas [[interprimo]] al ''n'' (alivorte ''[[plej granda komuna divizoro|PGKD]](a,n)=1''), do
:<math> a^{\varphi(n)} \equiv 1\mod n .</math>
Ĉi tio sekvas de [[teoremo de Lagrange (grupa teorio)|teoremo de Lagrange]] kaj tio, ke ''a'' apartenas al la [[multiplika grupo de entjeroj module n|multiplika grupo]] de <math>\mathbb{Z}/n\mathbb{Z}</math> , [se kaj nur se]] ''a'' estas [[interprimo]] al ''n''.
==Generante funkcioj==
La du sekvaj [[generanta funkcio|generantaj funkcioj]] aperas pro tio, ke
:<math>\sum_{d|n} \varphi(d) = n.</math>
Linio 95:
[[Serio de Dirichlet]] kun ''φ(n)'' estas
:<math>\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:
Linio 107:
La [[serio de Lambert]] estas
:<math>\sum_{n=1}^{\infty} \frac{\varphi(n) q^n}{1-q^n}= \frac{q}{(1-q)^2}</math> ,
kiu konverĝas por ''|q|<1''.
Linio 114:
:<math>\sum_{n=1}^{\infty} \frac{\varphi(n) q^n}{1-q^n} =
\sum_{n=1}^{\infty} \varphi(n) \sum_{r\ge 1} q^{rn}</math> ,
kio estas
Linio 136:
kun la produto ruliganta nur tra diversaj primoj ''p'' dividantaj na ''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. De la [[prima teoremo]] ĝi povas esti montrite, ke konstanto ''ε'' en la formulo pli supre povas pro tio esti anstataŭigita per
:<math>C\,\log \log n/ \log n.</math>
Linio 142:
''φ(n)'' estas ĝenerale proksime al ''n'' en averaĝa senco:
:<math>\frac{1}{n^2} \sum_{k=1}^n \varphi(k)= \frac{3}{\pi^2} + \mathcal{O}\left(\frac{\log n }{n}\right)</math> ,
kie ''O'' estas la [[granda O skribmaniero|granda O]]. Ĉi tiu ankaŭ diras, ke la probablo de du pozitiva entjeroj elektitaj hazarde de ''{1, 2, ..., ''n''}'' al esti interprimoj estas proksimume <math>6/\pi^2</math> , kiam ''n'' strebas al malfinio. Rilatanta rezulto estas la averaĝa ordo de ''φ(n)/n'' , kiu estas
:<math>\frac{1}{n} \sum_{k=1}^n \frac{\varphi(k)}{k} =
Linio 166:
:<math>\sum_{1\le k\le n \atop (k,m)=1} 1 = n \frac {\varphi(m)}{m} +
\mathcal{O} \left ( 2^{\omega(m)} \right )</math> ,
kie ''m'' > 1 estas pozitiva entjero, kaj ω(''m'') estas kvanto de diversaj primaj faktoroj de ''m''. (Ĉi tiuj formulaj kalkulas kvanton de pozitivaj entjeroj malpli grandaj ol aŭ egala al ''n'' kaj interprimaj al ''m''.)
=== Neegalaĵoj ===
| |||