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

Из пројекта Википедија

Првих хиљаду вредности за

φ(n)

У теорији бројева, Ојлерова фи функција $φ(n)$ , за позитивне целе бројеве n, је дефинисана као број позитивних целих бројева мањих или једнаких n, који су узајамно прости са n. На пример, $φ(9) = 6$ јер постоји шест бројева (1, 2, 4, 5, 7 и 8), који су узајамно прости са 9. Ојлерова функција је добила име по швајцарском математичару Леонарду Ојлеру.

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

Садржај

1 Рачунање Ојлерове функције
- 1.1 Пример рачунања
2 Неке вредности функције
3 Својства
4 Генераторне функције
5 Раст функције
6 Друге формуле које укључују Ојлерову функцију
7 Неједнакости
8 Референце
9 Спољне везе

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

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

$n = p_1^{k_1} \cdots p_r^{k_r}$

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

$\varphi(n)=(p_{11)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.

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

$φ(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)$

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

Према Ојлеровој теореми, ако су 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),$

где је $ζ(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$

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

$\,\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 / π 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$ позитиван цео број и $ω(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.

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

[уреди] Спољне везе

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

Добављено из "http://sr.wikipedia.org../../../%D0%BE/%D1%98/%D0%BB/%D0%9E%D1%98%D0%BB%D0%B5%D1%80%D0%BE%D0%B2%D0%B0_%D1%84%D0%B8_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%98%D0%B0.html"

Категорије страница: Теорија бројева · Модуларна аритметика · Мултипликативне функције · Теорија група