Ојлерова фи функција

У теорији бројева, Ојлерова фи функција $\phi (n)$, за позитивне целе бројеве n, је дефинисана као број позитивних целих бројева мањих или једнаких n, који су узајамно прости са n.

Првих хиљаду вредности за $\phi (n)$

На пример, $\phi (9)=6$ јер постоји шест бројева (1, 2, 4, 5, 7 и 8), који су узајамно прости са 9.

Ојлерова функција је добила име по швајцарском математичару Леонарду Ојлеру.

Ојлерова фи функција је важна углавном због тога што даје величину мултипликативних група целих бројева по модулу n. Прецизније, $\phi (n)$ је ред групе јединица прстена $\mathbb {Z} /n\mathbb {Z}$. Ова чињеница, заједно са Лагранжовом теоремом, даје доказ Ојлерове теореме.

Рачунање Ојлерове функције

Из дефиниције следи да је $\phi (1)=1$, и $\phi (n)=(p-1)p^{k-1}$ када је n k-ти степен простог броја p. Штавише, $\phi$ је мултипликативна функција; ако су m и n узајамно прости, онда $\phi (mn)=\phi (m)\phi (n)$. Вредност $\phi (n)$ се стога може израчунати коришћењем Основне теореме аритметике: ако

$n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}$

где су $p_{j}$ различити прости бројеви, онда

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

Задња формула је Ојлеров производ, и често се записује као

$\varphi (n)=n\prod _{p|n}\left(1-{\frac {1}{p}}\right)$

а производ узима само вредности различитих простих бројева $p$ који деле $n$.

Пример рачунања

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

Речима, ово значи да су различити прости фактори броја 36 бројеви 2 и 3; половина тридесет и шест целих бројева од 1 до 36 су дељиви са 2, што оставља осамнаест; трећина њих је дељиво са 3, што оставља дванаест узајамно простих са 36. А ових 12 бројева су: 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, и 35.

Неке вредности функције

$\phi (n)$	+0	+1	+2	+3	+4	+5	+6	+7	+8	+9
0+		1	1	2	2	4	2	6	4	6
10+	4	10	4	12	6	8	8	16	6	18
20+	8	12	10	22	8	20	12	18	12	28
30+	8	30	16	20	16	24	12	36	18	24
40+	16	40	12	42	20	24	22	46	16	42
50+	20	32	24	52	18	40	24	36	28	58
60+	16	60	30	36	32	48	20	66	32	44
70+	24	70	24	72	36	40	36	60	24	78
80+	32	54	40	82	24	64	42	56	40	88
90+	24	72	44	60	46	72	32	96	42	60

Својства

Број $\varphi (n)$ је такође једнак броју могућих генератора цикличне групе $C_{n}$. Како сваки елемент из $C_{n}$ генерише цикличну подгрупу и подгрупе од $C_{n}$ су облика $C_{d}$ где d дели n (што се записује као $d|n$), добијамо

$\sum _{d\mid n}\varphi (d)=n$

где сума пролази кроз све позитивне делиоце d од n.

Сада можемо да искористимо Мебијусову инверзиону формулу да инвертујемо ову суму и добијемо још једну формулу за $\varphi (n)$:

$\varphi (n)=\sum _{d\mid n}d\cdot \mu (n/d)$

где је $\mu$ уобичајена Мебијусова функција дефинисана за позитивне целе бројеве.

Према Ојлеровој теореми, ако су a и n узајамно прости, то јест, нзд(a, n) = 1, тада

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

Ово следи из Лагранжове теореме и чињенице да a припада мултипликативној групи $\mathbb {Z} /n\mathbb {Z}$ акко је a узајамно просто са n.

Генераторне функције

Две генераторне функције представљене овде су обе последице чињенице да

$\sum _{d|n}\varphi (d)=n.$

Дирехлеов ред са $\varphi$(n) је

$\sum _{n=1}^{\infty }{\frac {\varphi (n)}{n^{s}}}={\frac {\zeta (s-1)}{\zeta (s)}}.$

Ово се изводи на следећи начин:

$\zeta (s)\sum _{n=1}^{\infty }{\frac {\varphi (n)}{n^{s}}}=\sum _{n=1}^{\infty }\left(\sum _{d|n}\varphi (d)\right){\frac {1}{n^{s}}}=\sum _{n=1}^{\infty }{\frac {n}{n^{s}}}=\zeta (s-1),$

где је $\zeta (s)$ Риманова зета функција.

Генераторна функција Ламберовог реда је

$\sum _{n=1}^{\infty }{\frac {\varphi (n)q^{n}}{1-q^{n}}}={\frac {q}{(1-q)^{2}}}$

што конвергира за |q|<1.

Ово следи из

$\sum _{n=1}^{\infty }{\frac {\varphi (n)q^{n}}{1-q^{n}}}=\sum _{n=1}^{\infty }\varphi (n)\sum _{r\geq 1}q^{rn}$

што је

$\sum _{k\geq 1}q^{k}\sum _{n|k}\varphi (n)=\sum _{k\geq 1}kq^{k}={\frac {q}{(1-q)^{2}}}.$

Раст функције

Раст $\varphi (n)$ као функције од n је интересантно питање, јер је први утисак добијен на основу малих n да је $\varphi (n)$ знатно мање од n је унеколико нетачан. Асимптотски имамо

$\,n^{1-\epsilon }<\varphi (n)<n$

за свако дато $\epsilon >0$ и $n>N(\epsilon )$. У ствари, ако размотримо

$\,\varphi (n)/n$

можемо из горње формуле да добијемо, као производ фактора

$1-p^{-1}\,$

изнад простих бројева p који деле n. Стога вредности n које одговарају посебно малим вредностима односа су они n који су производ почетног сегмента низа простих бројева. Из Теореме простих бројева се може показати да се константа ε у горњој формули може заменити са

$C\,\log \log n/\log n$

$\varphi$ је такође генерално близу n у смислу просека:

${\frac {1}{n^{2}}}\sum _{k=1}^{n}\varphi (k)={\frac {3}{\pi ^{2}}}+{\mathcal {O}}\left({\frac {\log n}{n}}\right)$

где је велико O Ландауов симбол. Ово такође значи да је вероватноћа да ће два позитивна цела броја случајно изабрана из {1, 2, ..., n} бити релативно прости тежи $6/\pi ^{2}$ када n тежи бесконачности.

Друге формуле које укључују Ојлерову функцију

$\;\varphi \left(n^{m}\right)=n^{m-1}\varphi (n)$ за $m\geq 1$

$\sum _{d\mid n}{\frac {\mu ^{2}(d)}{\varphi (d)}}={\frac {n}{\varphi (n)}}$

$\sum _{1\leq k\leq n \atop (k,n)=1}\!\!k={\frac {1}{2}}n\varphi (n)$ за $\;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\leq k\leq n \atop (k,m)=1}1=n{\frac {\varphi (m)}{m}}+{\mathcal {O}}\left(2^{\omega (m)}\right),$

где је $m>1$ позитиван цео број и $\omega (m)$ означава број различитих простих фактора од $m$. (Ова формула рачуна број природних бројева мањих или једнаких n и релативно простих са m.)

Неједнакости

Неке неједнакости које укључују $\varphi$ функцију су:

$\varphi (n)>{\frac {n}{e^{\gamma }\;\log \log n+{\frac {3}{\log \log n}}}}$ за n > 2, где је γ Ојлерова константа,

$\varphi (n)\geq {\sqrt {\frac {n}{2}}}$ за n > 0,

и

$\varphi (n)\geq {\sqrt {n}}$ за n > 6.

За прост n, јасно је да $\varphi (n)=n-1$. За не-прост n имамо

$\varphi (n)\leq n-{\sqrt {n}}$

За све $n>1$:

$0<{\frac {\varphi (n)}{n}}<1$

За случајно велики n, ове границе се и даље не могу побољшати, или учинити прецизнијим:

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

Литература

• Milton Abramowitz and Irene A. Stegun, Handbook of Mathematical Functions,. Dover Publications, New York. 1964. ISBN 978-0-486-61272-0.. See paragraph 24.3.2.

• Eric Bach and Jeffrey Shallit, Algorithmic Number Theory, volume 1, 1996, MIT Press. ISBN 978-0-262-02405-1., see page 234 in section 8.8.

• Kirby Urner, Рачунање Ојлерове фи функције у програмском језику Питон, (2003)

Спољашње везе

• Изведена логаритамска функција Ојлерове функције