Ојлерова фи функција — разлика између измена
Садржај обрисан Садржај додат
м →Литература: претварање ISBN веза у шаблон |
м razne izmene; козметичке измене |
||
Ред 9:
== Рачунање Ојлерове функције ==
Из дефиниције следи да је <math>\phi(1) = 1</math>, и <math>\phi(n) = (p - 1)p^{k - 1}</math> када је ''-{n}-'' ''-{k}-''-ти степен [[прост број|простог броја]] ''-{p}-''. Штавише, <math>\phi</math> је [[мултипликативна функција]]; ако су ''-{m}-'' и ''-{n}-'' узајамно прости, онда <math>\phi(mn) = \phi(m) \phi(n)</math>. Вредност <math>\phi(n)</math> се стога може израчунати коришћењем [[Основна теорема аритметике|Основне теореме аритметике]]: ако
:<math>n = p_1^{k_1} \cdots p_r^{k_r}</math>
Ред 17:
:<math>\varphi(n)=(p_{1}-1)p_{1}^{k_{1}-1} \cdots (p_{r}-1)p_{r}^{k_{r}-1}</math>
Задња формула је [[Ојлеров производ]], и често се записује као
:<math>\varphi(n)=n\prod_{p|n}\left(1-\frac{1}{p}\right)</math>
а производ узима само вредности различитих простих бројева <math> p </math> који деле <math> n </math>.
Ред 73:
где је <math>\mu</math> уобичајена [[Мебијусова функција]] дефинисана за позитивне целе бројеве.
Према [[Ојлерова теорема|Ојлеровој теореми]], ако су ''-{a}-'' и ''-{n}-'' узајамно прости, то јест, [[највећи заједнички делилац|нзд]](''-{a}-'', ''-{n}-'') = 1, тада
:<math> a^{\varphi(n)} \equiv 1\mod n.</math><br />
Ово следи из [[Лагранжова теорема (теорија група)|Лагранжове теореме]] и чињенице да ''-{a}-'' припада [[Мултипликативна група целих бројева по модулу n|мултипликативној групи]] <math>\mathbb{Z}/n\mathbb{Z}</math> [[ако и само ако|акко]] је ''-{a}-'' узајамно просто са ''-{n}-''.
Ред 93:
Генераторна функција [[Ламберов ред|Ламберовог реда]] је
:<math>\sum_{n=1}^{\infty} \frac{\varphi(n) q^n}{1-q^n}= \frac{q}{(1-q)^2}</math>
што конвергира за |''-{q}-''|<1.
Ред 108:
== Раст функције ==
Раст <math>\varphi(n)</math> као функције од ''-{n}-'' је интересантно питање, јер је први утисак добијен на основу малих ''-{n}-'' да је <math>\varphi(n)</math> знатно мање од ''-{n}-'' је унеколико нетачан. Асимптотски имамо
:<math>\,n^{1-\epsilon}<\varphi(n)<n</math>
Ред 120:
:<math>1-p^{-1}\,</math>
изнад простих бројева ''-{p}-'' који деле ''-{n}-''. Стога вредности ''-{n}-'' које одговарају посебно малим вредностима односа су они ''-{n}-'' који су производ почетног сегмента низа простих бројева. Из [[Теорема простих бројева|Теореме простих бројева]] се може показати да се константа
:<math>C\,\log \log n/ \log n</math>
Ред 153:
:<math>
\varphi(n) > \frac {n} {e^\gamma\; \log \log n + \frac {3} {\log \log n}}
</math> за -{n}- > 2, где је
:<math>
Ред 159:
</math> за ''-{n}-'' > 0,
и
:<math>
\varphi(n) \ge \sqrt{n}
Ред 178:
== Литература ==
* ''-{Milton Abramowitz and Irene A. Stegun, Handbook of Mathematical Functions,
* ''-{Eric Bach and Jeffrey Shallit, ''Algorithmic Number Theory'', volume 1, 1996, MIT Press. {{
* ''-{Kirby Urner}-'', ''[http://groups.google.com/group/k12.ed.math/browse_thread/thread/19f74d278e88b65d/bd50b5ae25c74465?lnk=st&q=computing+euler+totient+function&rnum=4#bd50b5ae25c74465 Рачунање Ојлерове фи функције у програмском језику Питон]'', (2003.)
| |||