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

Из Википедије, слободне енциклопедије
Првих хиљаду вредности за \phi(n)

У теорији бројева, Ојлерова фи функција \phi(n), за позитивне целе бројеве n, је дефинисана као број позитивних целих бројева мањих или једнаких n, који су узајамно прости са 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\ge 1} q^{rn}

што је


\sum_{k\ge 1} q^k \sum_{n|k} \varphi(n) =
\sum_{k\ge 1} k q^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\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) за \;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),

где је 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) \ge \sqrt{\frac {n} {2} }
за n > 0,

и


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

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


\varphi(n) \le 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, (1964) Dover Publications, New York. ISBN 0-486-61272-4. See paragraph 24.3.2.
  • Eric Bach and Jeffrey Shallit, Algorithmic Number Theory, volume 1, 1996, MIT Press. ISBN 0-262-02405-5, see page 234 in section 8.8.

Спољашње везе[уреди]