Преглед на кода на Функция на Ойлер

[[Файл:EulerPhi.svg|мини|Първите хиляда стойности на {{math|''φ''(''n'')}}. Точките върху горната права представляват {{math|''φ''(''p'')}}, когато {{mvar|p}} е просто число, като {{math|''p'' − 1}}.<ref>{{cite web| url = https://www.khanacademy.org/computing/computer-science/cryptography/modern-crypt/v/euler-s-totient-function-phi-function| title = Euler's totient function| work = Khan Academy}}</ref>]]

В [[теория на числата|теорията на числата]] '''функцията на Ойлер''', наричана още '''Тотиента''' и отбелязвана с '''''φ''(''n'')''' е функция, дефинирана за произволно положително [[цяло число]] ''n'', като броя на естествените числа, ненадминаващи ''n'' и [[взаимно прости числа|взаимно прости]] с ''n''. Например ''φ''(8)&nbsp;=&nbsp;4, защото нечетните числа 1, 3, 5 и 7 са взаимно прости с 8, а ''φ''(9)&nbsp;=&nbsp;6, защото числата 1, 2, 4, 5, 7 и 8 са взаимно прости с 9. Функцията е наречена на швейцарския математик [[Леонард Ойлер]], който е изследвал много от нейните свойства.

== Изчисляване на функцията на Ойлер ==
Непосредствено от определението на функцията следва, че ''φ''(1)&nbsp;=&nbsp;1, а ''φ''(''n'')&nbsp;=&nbsp;(''p''&nbsp;−&nbsp;1)''p''<sup>''k''−1</sup>, когато ''n'' е ''k''-та степен на [[просто число]] ''p''<sup>''k''</sup>. Също така функцията е мултипликативна, т.е. когато ''m'' и ''n'' са [[взаимно прости числа|взаимно прости]]'' φ''(''mn'')&nbsp;=&nbsp;''φ''(''m'')''φ''(''n''). Следователно стойността на ''φ''(''n'') може да бъде изчислена посредством разлагане на прости множители (което съгласно [[основна теорема на аритметиката|основната теорема на аритметиката]] е единствено):

:<math>n=p_{1}^{k_1} \ldots p_{r}^{k_r}</math>,

където ''p<sub>i</sub>'' са различни [[просто число|прости числа]], и следователно

:<math>\varphi(n)=(p_{1}-1) p_{1}^{k_{1}-1} \ldots (p_{r}-1)p_{r}^{k_{r}-1}</math>.

Последната формула се нарича [[произведение на Ойлер]] и често се записва като:
:<math>\varphi(n)=n\prod_{p|n}\left(1-\frac{1}{p}\right)</math>
където произведението се извършва по простите числа ''p''<sub>''i''</sub> с ненулева степен в разлагането на ''n'' на прости множители.

Алгоритмичен начин за намиране на всички стойности на ''φ''(''x'') за ''x''=1..''n'' е така нареченото [[Тотиентно решето]], подобно на [[решето на Ератостен|решетото на Ератостен]].

== Други свойства ==
Числото ''φ''(''n'') също се равнява на броя на [[генератор на циклична подгрупа|генераторите]] на [[циклична група|цикличната група]] ''C<sub>n</sub>''. Тъй като всеки елемент от ''C<sub>n</sub>'' генерира циклична [[алгебрична подгрупа|подгрупа]] и подгрупите на ''C<sub>n</sub>'' са от вида ''C<sub>d</sub>'', където ''d'' [[делител|дели]] ''n'' (означава се като ''d''|''n''), получаваме
:<math>\sum_{d\mid n}\varphi(d)=n</math>
където сумата е върху всички положителни делители ''d'' на ''n''.

Прилагайки [[Формула на Мьобиус за обръщане|формулата на Мьобиус за обръщане]], може да се „обърне“ сумата и да се получи друга формула за ''φ''(''n''):

:<math>\varphi(n)=\sum_{d\mid n} d \mu(n/d) </math>

където ''μ'' е обикновената [[функция на Мьобиус]], дефинирана за положителни цели числа.

Ако ''a'' е [[Взаимно прости числа|взаимно просто]] с ''n'', т.е. [[най-голям общ делител|НОД]](''a'',''n'')&nbsp;=&nbsp;1, то
:<math>a^{\varphi(n)} \equiv 1\mod n.</math>

== Пораждаща функция|Пораждащи функции ==
[[Ред на Дирихле]], включващ ''φ''(''n''), е
:<math>\sum_{n=1}^{\infty} \frac{\varphi(n)}{n^s}=\frac{\zeta(s-1)}{\zeta(s)}.</math>

Функция, пораждаща [[ред на Ламберт]], e
:<math>\sum_{n=1}^{\infty} \frac{\varphi(n) q^n}{1-q^n}= \frac{q}{(1-q)^2}</math>
за |''q''|<1.

== Нарастване на функцията ==
Нарастването на ''φ''(''n'') като функция на ''n'' е интересен въпрос, тъй като първото впечатление при малки ''n'', че ''φ''(''n'') би могла да бъде значително по-малка от ''n'', е донякъде подвеждащо. Асимптотично

:<math>n^{1-\varepsilon}<\varphi(n)<n</math>

за всяко ''ε'' > 0 и ''n'' > ''N''(''ε''). Всъщност за

:<math>\varphi(n) \over n</math>

това може да се запише от горната формула като произведение на множители от типа

:<math>1-p^{-1} \,</math>

взети за простите числа ''p'', които са делители на ''n''. Следователно стойностите на ''n'', съответстващи на особено малки стойности на съотношението, са тези ''n'', които са произведение на един начален сегмент от редицата от всички прости числа. От [[теорема за простите числа|теоремата за простите числа]] може да се види, че константата ''ε'' в горната формула може следователно да се замени с

:<math>C\frac{\log \log n}{\log n}</math>.

Това поведение е валидно и за средната оценка
:<math>\frac{1}{n^2} \sum_{k=1}^n \varphi(k)= \frac{3}{\pi^2} + \mathcal{O}\left(\frac{\ln n }{n}\right)</math>
където главното ''O'' е [[символ на Ландау|символът на Ландау]].

== Неравенства ==
Някои [[неравенство|неравенства]], включващи ''φ''-функцията, са:
:<math>\varphi (n) > \frac {n} {e^\gamma\; \log \log n + \frac {3} {\log \log n}}</math>
за ''n''&nbsp;>&nbsp;2, където ''γ'' е [[Константа на Ойлер – Маскерони|Ойлеровата константа]],

:<math>\varphi(n) \ge \sqrt{\frac {n} {2} }</math>
за ''n''&nbsp;>&nbsp;0, и

:<math>\varphi(n) \ge \sqrt{n}</math>
за ''n''&nbsp;>&nbsp;6.

За прости ''n'' очевидно ''φ''(''n'')&nbsp;=&nbsp;''n''−1. За [[съставно число|съставно]] ''n'' имаме
:<math>\varphi(n) \le n-\sqrt{n}</math>.

Двойка неравенства, комбиниращи ''φ''-функцията и [[Сигма-функция (теория на числата)|''σ''-функцията]], са

:<math>\frac {6 n^2} {\pi^2} < \varphi(n) \sigma(n) < n^2</math>
за ''n'' > 1.

== Някои стойности ==
:{| class="wikitable"
! φ(n)
! +0 || +1 || +2 || +3 || +4 || +5 || +6 || +7 || +8 || +9 || +10 || +11
|-
! 0
| &nbsp; || 1 || 1 || 2 || 2 || 4 || 2 || 6 || 4 || 6 || 4 || 10
|-
!12
| 4 || 12 || 6 || 8 || 8 || 16 || 6 || 18 || 8 || 12 || 10 || 22
|-
!24
| 8 || 20 || 12 || 18 || 12 || 28 || 8 || 30 || 16 || 20 || 16 || 24
|-
!36
| 12 || 36 || 18 || 24 || 16 || 40 || 12 || 42 || 20 || 24 || 22 || 46
|-
!48
| 16 || 42 || 20 || 32 || 24 || 52 || 18 || 40 || 24 || 36 || 28 || 58
|-
!60
| 16 || 60 || 30 || 36 || 32 || 48 || 20 || 66 || 32 || 44 || 24 || 70
|-
!72
| 24 || 72 || 36 || 40 || 36 || 60 || 24 || 78 || 32 || 54 || 40 || 82
|}

== Източници ==
<references/>

[[Категория:Аритметични функции]]