P	U	S	Č	P	S	N
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30	31

Mali Fermatov teorem

Eulerova funkcija

Sažetak

Eulerova funkcija je jedna od najvažnijih funkcija u teoriji brojeva. U članku ćemo izvesti formulu za određivanje vrijednosti ove funkcije te ćemo dokazati neka od njezinih svojstava. Na primjerima ćemo pokazati neke od primjena dobivenih rezultata, a na kraju ćemo opisati nekoliko problema koji su usko vezani uz Eulerovu funkciju.

1Uvod

Leonhard Euler izložio je na skupovima iz 1758. i 1759., a u članku [8] iz 1763. godine i objavio svoje rezultate vezane uz funkciju koja "broji broj prirodnih brojeva manjih od prirodnog broja $n$ koji nemaju zajedničkih djelitelja s $n$ ". Kao što ćemo vidjeti, ova definicija razlikuje se od današnje samo utoliko što se umjesto izraza "manjih" koristi izraz "manjih ili jednakih". Godine 1784. Euler je za ovako definiranu funkciju koristio oznaku $\pi$ , a danas se koristi oznaka $\varphi$ koju je uveo Gauss u Disquisitiones Arithmeticae [11] objavljenim 1801. godine. U teoriji brojeva standardno se koristi termin Eulerova funkcija (ili Eulerova $\varphi$ funkcija), dok se u engleskoj literaturi najčešće koristi termin Euler's totient function koji je 1879. godine uveo Sylvester [17].

U članku ćemo dokazati neka svojstva Eulerove funkcije i Eulerov teorem, jedan od najvažnijih teorema u kojemu se javlja Eulerova funkcija. Dokazane tvrdnje ćemo primijeniti na primjerima, a na kraju ćemo opisati neke od poznatih problema u kojima se pojavljuje Eulerova funkcija.

2Eksplicitna formula

Ukoliko sa $U_{n}$ označimo skup svih prirodnih brojeva koji nisu veći od $n$ i relativno su prosti s $n$ , tj.

$U_{n}=\lbrace k \in \mathbb{N}:1\leq k\le n \text{ i } (n,k)=1 \rbrace ,$

tada Eulerovu funkciju možemo definirati kao funkciju $\varphi:\mathbb{N}\to\mathbb{N}$ zadanu s $\varphi(n)=\# U_{n}$ .

Uočimo da se vrijednosti ovako definirane funkcije razlikuju u odnosu na spomenutu Eulerovu definiciju samo za broj 1 - ovdje je $\varphi(1)=1$ , dok bi primjenom Eulerove definicije dobili vrijednost 0 u broju 1.

Primjer 1. Ako je

$p$ prost broj, tada je svaki prirodan broj

$j$ takav da je

$j\lt p$ relativno prost s

$p$ pa vrijedi

$\varphi(p) = p-1$ .

Grafički prikaz Eulerove funkcije dan je na Slici 1.

Slika 1: Graf Eulerove funkcije

Vrijednosti Eulerove funkcije usko su vezane uz broj elemenata u tzv. reduciranom sustavu ostataka modulo $n$ .

Reducirani sustav ostataka modulo $n$ je skup $R\subseteq \mathbb{Z}$ koji sadrži po točno jedan element iz svake od $\varphi(n)$ klasa ekvivalencije od $U_{n}$ .

U nastavku ćemo dokazati jedno važno svojstvo Eulerove funkcije, a to je tzv. svojstvo multiplikativnosti. Multiplikativne funkcije su funkcije $f : \mathbb{N} \rightarrow \mathbb{C}$ za koje vrijedi:

1	$f(1) = 1$ ,
2	$f(mn) = f(m)f(n)$ , za sve $m,n$ takve da je $(m,n) = 1$ .

Teorem 2. Eulerova funkcija je multiplikativna funkcija.

Proof. Iz definicije je jasno da je

$\varphi(1)=1$ . Neka su

$m,n$ prirodni brojevi sa svojstvom da je

$(m,n)=1$ . Posložimo brojeve

$1,2,\dots,mn$ u tablicu s

$n$ redova i

$m$ stupaca na sljedeći način:

$\begin{matrix} 1 & 2 & 3 & \dots & m \\ m+1 & m+2 & m+3 & \dots & 2m \\ \vdots & \vdots & \vdots & & \vdots \\ (n-1)m+1 & (n-1)m+2 & (n-1)m+3 & \dots & nm \end{matrix}$ U ovom nizu brojeva postoji, prema definiciji,

$\varphi(mn)$ brojeva koji su relativno prosti s

$mn$ . Uočimo da su svi brojevi u pojedinom stupcu međusobno kongruentni modulo

$m$ , a svih

$m$ stupaca odgovaraju

$m$ klasa ekvivalencije modulo

$m$ . Stoga su brojevi u istom stupcu ili svi relativno prosti s

$m$ ili nijedan nije relativno prost s

$m$ . Zaključujemo da se točno

$\varphi(m)$ stupaca sastoji od brojeva relativno prostih s

$m$ , dok ostali stupci sadrže brojeve koji nisu relativno prosti s

$m$ .

Promotrimo jedan od tih

$\varphi(m)$ stupaca. Neka je to

$k$ -ti stupac. Označimo sa

$S_{k}$ skup koji sadrži sve elemente toga stupca, tj.

$S_{k}=\lbrace k,m+k,2m+k,\dots, (n-1)m+k\rbrace$ . Dokažimo da su u skupu

$S_{k}$ svi elementi međusobno nekongruentni. Ako bi postojali

$i,j\in\lbrace 0,1,\ldots,n-1\rbrace$ takvi da vrijedi

$im+k\equiv jm+k\pmod{n},$ onda oduzimanjem broja

$k$ i korištenjem činjenice da je

$(m,n)=1$ dobivamo da je

$i\equiv j \pmod{n}$ pa je

$i=j$ .

Kako

$S_{k}$ ima

$n$ međusobno nekongruentnih elemenata modulo

$n$ zaključujemo da u

$S_{k}$ imamo predstavnike svih mogućih klasa modulo

$n$ (tj.

$S_{k}$ je potpun sustav ostataka modulo

$n$ ). Neka je

$R_{k}$ skup koji sadrži elemente skupa

$S_{k}$ koji su relativno prosti s

$n$ . Tada je

$R_{k}$ reducirani sustav ostataka modulo

$n$ i ima

$\varphi(n)$ elemenata.

Zaključujemo da svaki od

$\varphi(m)$ stupaca iz gornje tablice sadrži

$\varphi(n)$ brojeva relativno prostih s

$n$ pa je u gornjoj tablici

$\varphi(m)\varphi(n)$ brojeva koji su relativno prosti i sa

$m$ i sa

$n$ , a onda i s

$mn$ .

Stoga je

$\varphi(mn)=\varphi(m)\varphi(n)$ i tvrdnja je dokazana.

$\ \blacksquare$

Primjer 3. Odredimo

$\varphi(1111)$ . Kako je

$1111=11\cdot 101$ , primjenom svojstva multiplikativnosti Eulerove funkcije i činjenice da su 11 i 101 prosti brojevi dobivamo

$\varphi(1111)=\varphi(11\cdot101)=\varphi(11)\varphi(101)=10\cdot 100=1000.$

Propozicija 4. Neka je

$p$ prost broj i

$\alpha \in \mathbb{N}$ . Tada vrijedi

$\varphi(p^{\alpha}) = p^{\alpha-1}(p-1).$

Proof. Neka je

$p$ prost broj i

$\alpha \geq 1$ . Pozitivni djelitelji broja

$p^{\alpha}$ su

$1, p,\dots, p^{\alpha}$ . Jedini brojevi

$i$ takvi da

$1 \leq i \leq p^{\alpha}$ koji nisu relativno prosti s

$p^{\alpha}$ su višekratnici broja

$p$ , a to su

$1\cdot p, 2\cdot p,\dots, p^{\alpha-1}\cdot p = p^{\alpha}$ . Dakle, ima ih

$p^{\alpha-1}$ pa je

$\varphi(p^{\alpha}) =p^{\alpha} - p^{\alpha-1} = p^{\alpha-1}(p - 1).$

$\ \blacksquare$

Kako se svaki prirodan broj veći od 1 može prikazati u obliku $n = p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}}\cdots p_{k}^{\alpha_{k}}$ , $\alpha_{i}\in\mathbb{N}$ , $p_{i}$ prosti brojevi, $i\in\lbrace 1,\ldots,k\rbrace$ , primjenom svojstva multiplikativnosti Eulerove funkcije i upravo dokazane propozicije, dobivamo

(1)

$\varphi(n) = \prod\limits_{i=1}^{k}p_{i}^{\alpha_{i}-1}\left(p_{i} - 1\right) =n\prod\limits_{i=1}^{k}\left(1 - \frac{1}{p_{i}}\right).$

Primjer 5. Odredimo broj prirodnih brojeva koji su relativno prosti s brojem googol tj. s brojem

$10^{100}$ i manji su od njega.

Rješenje: Trebamo odrediti $\varphi(10^{100})$ . Primjenom prethodne formule dobivamo

$\varphi(10^{100})=\varphi(2^{100}5^{100})=2^{99}5^{99}4=4\cdot10^{99}.$

\hfill $\Diamond$

Primjer 6. Odredimo sve prirodne brojeve

$n$ za koje je

$\varphi(n)$ neparan broj.

Rješenje: Već smo komentirali da je $\varphi(1) = 1$ , a lako se vidi i da je $\varphi(2) = 1$ .

Pretpostavimo da je $n\gt 2$ . Ako postoji neparan faktor $p_{i}$ od $n$ , onda je $p_{i} - 1$ paran broj pa je $\varphi(n)$ paran broj zbog (1). Ako ne postoji neparan faktor $p_{i}$ od $n$ , onda je $n =2^{\alpha}$ , $\alpha \geq 2$ , pa je

$\varphi(n) = 2^{a-1}(2-1) = 2^{a-1}.$

Kako je $\alpha - 1 \geq 1$ slijedi da je $\varphi(n)$ paran broj.

Zaključujemo da je $\varphi(n)$ neparan broj samo za $n\in\lbrace 1,2\rbrace$ . \hfill $\Diamond$

Primjer 7. Pokažimo da postoji beskonačno mnogo pozitivnih cijelih brojeva

$n$ takvih da je

$\varphi(n)=\frac{n}{3}.$

Rješenje: Za sve

$n=2\cdot3^{m}$ ,

$m\in\mathbb{N}$ , vrijedi

$\varphi(n)=\varphi(2\cdot3^{m})=\varphi(2)\varphi(3^{^{m}})=3^{m-1}(3-1) =2\cdot3^{m-1}=\frac{n}{3}.$ Time je tvrdnja dokazana. \hfill

$\Diamond$

3Svojstva Eulerove funkcije

U ovom ćemo dijelu dokazati još neka svojstva Eulerove funkcije.

Propozicija 8. Neka je

$n$ prirodan broj. Ako

$d\mid n$ , onda

$\varphi(d) \mid \varphi(n)$ .

Proof. Neka je

$n = p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} \cdots p_{k}^{\alpha_{k}}$ . Ako

$d\mid n$ , onda je

$d=p_{1}^{\beta_{1}}\cdots p_{k}^{\beta_{k}}$ , gdje je

$0\le \beta_{i}\le\alpha_{i}$ ,

$i=1,\ldots,k$ . Uvrštavanjem u formulu (1) dobije se da je

$\frac{\varphi(n)}{\varphi(d)}=\prod_{i=1}^{k}p^{\alpha_{i}-\beta_{i}}.$ Kako je, zbog

$\alpha_{i}-\beta_{i}\ge 0$ , broj s desne strane ove jednakosti prirodan, time je tvrdnja dokazana.

$\ \blacksquare$

Propozicija 9.[Gauss] Za sve prirodne brojeve

$n$ vrijedi

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

Proof. Neka je

$n = p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}}\cdots p_{k}^{\alpha_{k}}$ . Promatrajmo sljedeći produkt

(2)

$\prod\limits_{i=1}^{k}(1 + \varphi(p_{i}) + \varphi(p_{i}^{2}) +\cdots+ \varphi(p_{i}^{\alpha_{i}})).$

Množenjem faktora ovog produkta dobivamo sumu pribrojnika oblika

$\varphi(p_{1}^{\beta_{1}})\cdots\varphi(p_{k}^{\beta_{k}}) = \varphi(p_{1}^{\beta_{1}}\cdots p_{k}^{\beta_{k}}),$ gdje je

$0\leq\beta_{i}\leq\alpha_{i}$ ,

$i = 1,\dots,k$ . Kako su s

$p_{1}^{\beta_{1}}\cdots p_{k}^{\beta_{k}}$ ,

$0\leq\beta_{i}\leq\alpha_{i}$ ,

$i = 1,\dots,k$ , dani svi djelitelji broja

$n$ , zaključujemo da je

(3)

$\sum\limits_{d \mid n}\varphi(d) =\prod\limits_{i=1}^{k}(1 + \varphi(p_{i}) + \varphi(p_{i}^{2}) +\cdots+ \varphi(p_{i}^{\alpha_{i}})).$

Stoga je

$\sum\limits_{d \mid n}\varphi(d) =\prod\limits_{i=1}^{k}(1 + (p_{i} - 1) + (p_{i}^{2} - p_{i}) +\cdots+ (p_{i}^{\alpha_{i}} - p_{i}^{\alpha_{i}-1})) = \prod\limits_{i=1}^{k} p_{i}^{\alpha_{i}} = n$ i time je tvrdnja dokazana.

$\ \blacksquare$

Propozicija 10. Za svaki prirodan broj

$m$ postoji konačno mnogo prirodnih brojeva

$n$ takvih da je

$\varphi(n)=m$ .

Proof. Ako neka potencija prostog broja

$p$ dijeli

$n$ , tj.

$p^{\alpha}\mid n$ , prema Propoziciji (8) vrijedi

$p^{\alpha-1}(p-1)\mid \varphi(n)=m$ . No, onda je

$p^{\alpha}\leq\frac{mp}{p-1}\leq2m.$ Kako postoji samo konačno mnogo brojeva

$p^{\alpha}$ takvih da je

$p^{\alpha}\leq2m$ , postoji i konačno mnogo produkata takvih potencija prostih brojeva. Stoga postoji i konačno mnogo prirodnih brojeva s danim svojstvom.

$\ \blacksquare$

U nastavku donosimo dvije ocjene za Eulerovu funkciju.

Propozicija 11. Ako je

$n$ složen prirodan broj, tada je

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

Proof. Budući da je

$n$ složen broj,

$n$ ima prost faktor

$p_{j}\leq \sqrt{n}$ . Sada imamo

$\varphi(n)=n\left(1-\frac{1}{p_{1}}\right) \cdots \left(1-\frac{1}{p_{k}}\right)\leq n\left(1-\frac{1}{p_{j}}\right) \leq n\left(1-\frac{1}{\sqrt{n}}\right)=n-\sqrt{n}.$

$\ \blacksquare$

Propozicija 12. Za sve prirodne brojeve

$n$ ,

$n \ne 2, 6$ , vrijedi

$\varphi(n)\geq \sqrt{n}.$

Proof. Za

$n=p^{m}$ , gdje je

$p$ prost broj i

$m\geq 2$ , vrijedi

$\dfrac{m}{2} \le m-1$ pa slijedi

(4)

$\begin{eqnarray} \varphi(n)&=&p^{m-1}(p-1) \ge p^{m-1}\geq \sqrt{p^{m}}=\sqrt{n}. \end{eqnarray}$

U slučaju kada je

$p\ne 2$ vrijedi i

(5)

$\begin{eqnarray} \varphi(n)&=&p^{m-1}(p-1) \ge p^{m-1} \sqrt{2}\geq \sqrt{2p^{m}}=\sqrt{2n}. \end{eqnarray}$

Neka je

$n=p$ ,

$p\ge 3$ , gdje je

$p$ prost broj. Lako se vidi da je kvadratna funkcija

$f(x)=x^{2}-x-1$ pozitivna za

$x\gt \dfrac{1+\sqrt{5}}{2}$ . Uz supstituciju

$x=\sqrt{t}$ dobivamo da za

$t\gt \left(\dfrac{1+\sqrt{5}}{2}\right)^{2}$ vrijedi

$\sqrt{t}\lt t-1$ . Stoga za

$p\ge 3$ vrijedi

$\sqrt{p}\lt p-1$ pa je

(6)

$\begin{eqnarray} \varphi(n)&=&p-1 \gt \sqrt{p}=\sqrt{n}. \end{eqnarray}$

$p\ge 5$ analogno se može pokazati da je

(7)

$\begin{eqnarray} \varphi(n)&=&p-1 \gt \sqrt{2p}=\sqrt{2n}. \end{eqnarray}$

Ako je

$n$ neparan ili

$4\mid n$ , (4) i (6) povlače da vrijedi

$\varphi(n)=\varphi(p_{1}^{\alpha_{1}})\cdots\varphi(p_{k}^{\alpha_{k}}) \geq \sqrt{p_{1}^{\alpha_{1}}} \cdots \sqrt{p_{k}^{\alpha_{k}}}=\sqrt{n}.$
Ako je

$n=2k$ , gdje je

$k$ neparan broj, tada za

$n \ne 6$ slijedi da 9 dijeli

$k$ ili

$k$ ima barem jedan prost faktor

$p\ge 5$ . Iz (5)–(7) slijedi

$\varphi(n)=\varphi(k)\geq\sqrt{2k}=\sqrt{n}.$

$\ \blacksquare$

4Eulerov teorem

Eulerova funkcija sastavni je dio Eulerovog teorema, jednog od najvažnijih teorema u teoriji brojeva.

Teorem 13.{(Eulerov teorem)} Ako su

$n \in \mathbb{N}$ i

$a \in \mathbb{Z}$ takvi da

$(a,n) = 1$ , onda je

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

Proof. Ako je

$\lbrace r_{1},\dots,r_{\varphi(n)}\rbrace$ reducirani sustav ostataka modulo

$n$ , onda je, za

$(a,n)=1$ , i

$\lbrace ar_{1},\dots,ar_{\varphi(n)}\rbrace$ reducirani sustav ostataka modulo

$n$ (jer iz

$ar_{i} \equiv ar_{j} \pmod{n}$ i

$(a,n)=1$ slijedi

$i=j$ ). No, onda mora vrijediti

$\prod\limits_{j=1}^{\varphi(n)}ar_{j}\equiv\prod\limits_{i=1}^{\varphi(n)} r_{i} \pmod{n},$ odnosno

$\begin{alignat*}{2} a^{\varphi(n)}\prod\limits_{j=1}^{\varphi(n)}r_{j} \equiv \prod\limits_{i=1}^{\varphi(n)} r_{i} \pmod{n}. \end{alignat*}$ Kako je

$(r_{i},n)=1$ ,

$i=1,\ldots,n$ , odavde slijedi

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

$\ \blacksquare$

Ako je $n$ prost broj, onda iz Eulerovog teorema direktno slijedi Mali Fermatov teorem.

Korolar 14. (Mali Fermatov teorem) Neka je

$p$ prost broj. Ako

$p \nmid a$ , onda je

$a^{p-1}\equiv 1 \pmod{p}.$

Primjer 15. Odredimo ostatak pri dijeljenju broja

$2017^{10^{6}}$ sa 55.

Rješenje: Kako je $\varphi(55)=\varphi(5)\varphi(11)=40$ i $(2017,55)=1$ , iz Eulerovog teorema slijedi

$2017^{40}\equiv 1 \pmod{55}.$

No, onda je

$2017^{10^{6}}\equiv 2017^{40\cdot25000}\equiv 1\pmod{55}.$

Stoga je traženi ostatak 1. \hfill $\Diamond$

Primjer 16. Odredimo posljednje tri znamenke u decimalnom zapisu broja

$3^{4004}$ .

Rješenje: Uočimo da rješenje možemo dobiti određivanjem ostatka pri dijeljenju danog broja s 1000. Budući da je $\varphi(1000)=\varphi({2^{3}}) \varphi(5^{3})=400$ i $(3,1000)=1$ primjenom Eulerovog teorema dobivamo

$3^{400} \equiv 1 \pmod{1000},$

odakle slijedi

$3^{4004} \equiv 3^{400\cdot 10 +4}\equiv 3^{4}\equiv 81 \pmod{1000}.$

Odavde zaključujemo da su zadnje tri znamenke broja $3^{400}$ jednake 081. \hfill $\Diamond$

Primjer 17. Dokažimo da su prirodni brojevi oblika

$n^{24}+17$ djeljivi s 18 za sve prirodne brojeve

$n$ za koje je

$(n,18)=1$ .

Rješenje: Za $(n,18)=1$ primjenom Eulerovog teorema dobivamo

$n^{\varphi{(18)}}\equiv n^{6}\equiv 1\pmod{18}$

pa je

$n^{24}+17\equiv1+17\equiv 0\pmod{18}$

i time je tvrdnja dokazana. \hfill $\Diamond$

Spomenimo samo da Eulerov teorem i Mali Fermatov teorem imaju dvije važne primjene:

$\bullet$	Najpoznatiji kriptosustav s javnim ključem, RSA kriptosustav, bazira se na Eulerovom teoremu (vidi npr. [12]).
$\bullet$	Iako obrat Malog Fermatovog teorema ne vrijedi (može se pokazati da je npr. $2^{340}\equiv 1 \pmod{341}$ , ali $341=11\cdot 31$ ), Mali Fermatov teorem je baza za razne testove prostosti (vidi npr. [16]).

5Problemi vezani uz Eulerovu funkciju

U ovom dijelu opisat ćemo neke od poznatih problema koji su vezani uz Eulerovu funkciju.

5.1Gauss-Wantzelov teorem

Kažemo da je pravilni $n$ -terokut konstruktibilan ako se može konstruirati samo pomoću ravnala i šestara. Gauss je 1796. godine pokazao da je pravilni $17$ -terokut konstruktibilan, a u Disquisitiones Arithmeticae je poopćio ovaj rezultat te je dokazao uvjet dovoljnosti iz teorema koji ćemo navesti. Uvjet nužnosti dokazao dokazao je Wantzel [18] 1837. godine.

Tvrdnja teorema u uskoj je vezi s Fermatovim prostim brojevima tj. prostim brojevima oblika $F_{n} = 2^{2^{n}} + 1$ . Poznato je samo 5 prostih Fermatovih brojeva (to su $F_{0}=3$ , $F_{1}=5$ , $F_{2}=17$ , $F_{3}=257$ i $F_{4}=65537$ ) i otvoreni je problem ima li ih još.

Teorem 18. Pravilan

$n$ -terokut može se konstruirati ravnalom i šestarom ako i samo ako se

$n$ može prikazati u obliku produkta neke potencije broja dva i različitih Fermatovih prostih brojeva tj.

$n=2^{i}F_{n_{1}}\cdots F_{n_{j}}$ , gdje su

$n\ge 3$ ,

$i\geq0$ ,

$j\geq0$ i

$F_{n_{1}}, \dots,F_{n_{j}}$ su različiti Fermatovi prosti brojevi.

Wantzel je pokazao da se Teorem (18) može izreći i na sljedeći način:

Teorem 19. Pravilan

$n$ -terokut može se konstruirati ravnalom i šestarom ako i samo ako je

$n$ prirodan broj veći od 2 takav da je

$\varphi(n)$ potencija broja 2.

5.2Lehmerov problem

Znamo da za prost broj $p$ vrijedi $\varphi(p) = p - 1$ . Lehmer je 1932. godine postavio pitanje postoje li složeni brojevi $n$ takvi da $\varphi(n) \mid n - 1$ . Pretpostavlja se da takvi brojevi ne postoje i danas je ta pretpostavka poznata kao Lehmerov problem/slutnja o Eulerovoj funkciji:

Ne postoji složen prirodan broj

$n$ sa svojstvom da

$\varphi(n) \mid n - 1$ .}

1933. godine Lehmer je dokazao da ako takav $n$ postoji, mora biti neparan, kvadratno slobodan i djeljiv s barem 7 prostih brojeva, odnosno $\omega(n)\geq 7$ ( $\omega$ je funkcija koja "broji" sve proste djelitelje zadanog broja $n$ ). Cohen i Hagis [6] dokazali su 1980. godine da je $n\gt 10^{20}$ i $\omega(n)\geq14$ . Burcsi, Czirbusz i Farkas su 2011. pokazali da ako $3\mid n$ , onda je $n\gt 10^{360 000 000}$ i $\omega(n)\geq 40 000 000$ .

5.3Carmichaelova slutnja i Fordov teorem

1907. godine Carmichael [3] je objavio teorem u kojem je tvrdio da ne postoji broj $n$ takav da za sve $m \neq n$ vrijedi $\varphi(n) \neq \varphi(m)$ . Međutim, 1922. godine pronađena je greška u dokazu. Iako tvrdnja još uvijek nije dokazana, pretpostavlja se da je točna i danas je ta pretpostavka poznata kao Carmichaelova slutnja. Često se iskazuje i u sljedećem obliku:

Za sve prirodne brojeve

$n$ jednadžba

$\varphi(x)= n$ ne može imati jedinstveno rješenje.}

Carmichael [4] je dokazao da kontraprimjer njegovoj pretpostavci mora biti broj veći ili jednak od $10^{37}$ . Pomerance [15] je pokazao 1974. da je prirodan broj $n$ kontraprimjer ovoj pretpostavci ako za svaki prost broj $p$ takav da $p-1\mid \varphi(n)$ vrijedi $p^{2}\mid n$ . Ford [9] je 1998. godine pokazao da eventualni kontraprimjer mora biti veći od $10^{10^{10}}$ .

Vezano uz broj rješenja jednadžbe $\varphi(x)= n$ poznata je i slutnja koju je iznio Sierpi $\acute{\text{n}}$ ski:

Za svaki prirodni broj

$k\ge 2$ postoji prirodni broj

$n$ takav da jednadžba

$\varphi(x)=n$ ima točno

$k$ rješenja.}

Ford [10] je 1998. dokazao da je slutnja točna.

Bibliografija

[1]	T. Andreescu, D. Andrica, Number theory, Birkhäuser, Basel, 2009.
[2]	P. Burcsi, S. Czirbusz, G. Farkas, Computational investigation of Lehmer's totient problem, Ann. Univ. Sci. Budap. Rolando Eötvös, Sect. Comput. {\bf 35} (2011), 43–49.
[3]	R. D. Carmichael, On Eulers $\varphi$ -function}, Bull. Amer. Math. Soc. (N.S.) {\bf 13} (1907), 241–243.
[4]	R. D. Carmichael, Note on Eulers $\varphi$ -function}, Bull. Amer. Math. Soc. (N.S.) {\bf 28} (1922), 109–110.
[5]	P. L. Clark, Number Theory: A Contemporary Introduction, http://math.uga.edu/ pete/4400FULL.pdf
[6]	G. L. Cohen, P. Hagis, On the Number of Prime Factors of $n$ if $\varphi(n)\mid (n-1)$ }, Nieuw Arch. Wiskd. {\bf 28} (1980), 177–185.
[7]	A. Dujella, Uvod u teoriju brojeva, PMF - Matematički odjel, Sveučilište u Zagrebu, skripta.
[8]	L. Euler, Theoremata arithmetica nova methodo demonstrata, Novi commentarii academiae scientiarum imperialis Petropolitanae {\bf 8} (1763), 74–104.
[9]	K. Ford, The number of solutions of $\varphi(x) = m$ }, Ann. of Math. {\bf 150} (1999), 283–311.
[10]	K. Ford, The distribution of totients, Ramanujan J. {\bf 2} (1998), 67–151.
[11]	C. F. Gauss, Disquisitiones Arithmeticae, Leipzig, Germany, 1801, (Yale University Press, New Haven, 1965).
[12]	B. Ibrahimpašić, RSA kriptosustav, Osječki matematički list {\bf 5} (2005), 101–112.
[13]	G. A. Jones, J. M. Jones, Elementary Number Theory, Springer, 2003.
[14]	R. A. Mollin, Fundamental Number Theory with Applications, CRC Press, New York, 2008.
[15]	C. Pomerance, On Carmichael's conjecture, Proc. Amer. Math. Soc. {\bf 43} (1974), 297–298.
[16]	H. Riesel, Prime Numbers and Computer Methods for Factorization, Birkh $\ddot{\text{a}}$ user, Boston, 1994.
[17]	J. J. Sylvester, On certain ternary cubic-form equations, Amer. J. Math. {\bf 2} (1879), 357–393.
[18]	P. L. Wantzel, Recherches sur les moyens de reconnaître si un problème de géométrie peut se résoudre avec la règle et le compas, J. Math. Pures Appliq. {\bf 1} (1836), 366–372.

Eulerova funkcija

Mirela Jukić Bokun i Andrea Behin, Sveučilište u Osijeku

Sažetak

1Uvod

Leonhard Euler izložio je na skupovima iz 1758. i 1759., a u članku [8] iz 1763. godine i objavio svoje rezultate vezane uz funkciju koja "broji broj prirodnih brojeva manjih od prirodnog broja

$n$ koji nemaju zajedničkih djelitelja s

$n$ ". Kao što ćemo vidjeti, ova definicija razlikuje se od današnje samo utoliko što se umjesto izraza "manjih" koristi izraz "manjih ili jednakih". Godine 1784. Euler je za ovako definiranu funkciju koristio oznaku

$π$ , a danas se koristi oznaka

$ϕ$ koju je uveo Gauss u Disquisitiones Arithmeticae [11] objavljenim 1801. godine. U teoriji brojeva standardno se koristi termin Eulerova funkcija (ili Eulerova

$ϕ$ funkcija), dok se u engleskoj literaturi najčešće koristi termin Euler's totient function koji je 1879. godine uveo Sylvester [17].

U članku ćemo dokazati neka svojstva Eulerove funkcije i Eulerov teorem, jedan od najvažnijih teorema u kojemu se javlja Eulerova funkcija. Dokazane tvrdnje ćemo primijeniti na primjerima, a na kraju ćemo opisati neke od poznatih problema u kojima se pojavljuje Eulerova funkcija.

2Eksplicitna formula

Ukoliko sa

$U_{n}$ označimo skup svih prirodnih brojeva koji nisu veći od

$n$ i relativno su prosti s

$n$ , tj.

$U_{n} = {k \in ℕ : 1 \leq k \leq n i (n, k) = 1},$

tada Eulerovu funkciju možemo definirati kao funkciju

$ϕ : ℕ \to ℕ$ zadanu s

$ϕ (n) = # U_{n}$ .

Uočimo da se vrijednosti ovako definirane funkcije razlikuju u odnosu na spomenutu Eulerovu definiciju samo za broj 1 - ovdje je

$ϕ (1) = 1$ , dok bi primjenom Eulerove definicije dobili vrijednost 0 u broju 1.

Primjer 1. Ako je

$p$ prost broj, tada je svaki prirodan broj

$j$ takav da je

$j < p$ relativno prost s

$p$ pa vrijedi

$ϕ (p) = p - 1$ .

Grafički prikaz Eulerove funkcije dan je na Slici 1.

Slika 1: Graf Eulerove funkcije

Vrijednosti Eulerove funkcije usko su vezane uz broj elemenata u tzv. reduciranom sustavu ostataka modulo

$n$ .

Reducirani sustav ostataka modulo

$n$ je skup

$R \subseteq ℤ$ koji sadrži po točno jedan element iz svake od

$ϕ (n)$ klasa ekvivalencije od

$U_{n}$ .

U nastavku ćemo dokazati jedno važno svojstvo Eulerove funkcije, a to je tzv. svojstvo multiplikativnosti. Multiplikativne funkcije su funkcije

$f : ℕ \to ℂ$ za koje vrijedi:

1	$f (1) = 1$ ,
2	$f (m n) = f (m) f (n)$ , za sve $m, n$ takve da je $(m, n) = 1$ .

Teorem 2. Eulerova funkcija je multiplikativna funkcija.

Proof. Iz definicije je jasno da je

$ϕ (1) = 1$ . Neka su

$m, n$ prirodni brojevi sa svojstvom da je

$(m, n) = 1$ . Posložimo brojeve

$1, 2, \dots, m n$ u tablicu s

$n$ redova i

$m$ stupaca na sljedeći način:

$\begin{matrix} 1 & 2 & 3 & \dots & m \\ m + 1 & m + 2 & m + 3 & \dots & 2 m \\ ⋮ & ⋮ & ⋮ & ⋮ \\ (n - 1) m + 1 & (n - 1) m + 2 & (n - 1) m + 3 & \dots & n m \end{matrix}$

U ovom nizu brojeva postoji, prema definiciji,

$ϕ (m n)$ brojeva koji su relativno prosti s

$m n$ . Uočimo da su svi brojevi u pojedinom stupcu međusobno kongruentni modulo

$m$ , a svih

$m$ stupaca odgovaraju

$m$ klasa ekvivalencije modulo

$m$ . Stoga su brojevi u istom stupcu ili svi relativno prosti s

$m$ ili nijedan nije relativno prost s

$m$ . Zaključujemo da se točno

$ϕ (m)$ stupaca sastoji od brojeva relativno prostih s

$m$ , dok ostali stupci sadrže brojeve koji nisu relativno prosti s

$m$ .

Promotrimo jedan od tih

$ϕ (m)$ stupaca. Neka je to

$k$ -ti stupac. Označimo sa

$S_{k}$ skup koji sadrži sve elemente toga stupca, tj.

$S_{k} = {k, m + k, 2 m + k, \dots, (n - 1) m + k}$ . Dokažimo da su u skupu

$S_{k}$ svi elementi međusobno nekongruentni. Ako bi postojali

$i, j \in {0, 1, \dots, n - 1}$ takvi da vrijedi

$i m + k \equiv j m + k (\mod n),$

onda oduzimanjem broja

$k$ i korištenjem činjenice da je

$(m, n) = 1$ dobivamo da je

$i \equiv j (\mod n)$ pa je

$i = j$ .

Kako

$S_{k}$ ima

$n$ međusobno nekongruentnih elemenata modulo

$n$ zaključujemo da u

$S_{k}$ imamo predstavnike svih mogućih klasa modulo

$n$ (tj.

$S_{k}$ je potpun sustav ostataka modulo

$n$ ). Neka je

$R_{k}$ skup koji sadrži elemente skupa

$S_{k}$ koji su relativno prosti s

$n$ . Tada je

$R_{k}$ reducirani sustav ostataka modulo

$n$ i ima

$ϕ (n)$ elemenata.

Zaključujemo da svaki od

$ϕ (m)$ stupaca iz gornje tablice sadrži

$ϕ (n)$ brojeva relativno prostih s

$n$ pa je u gornjoj tablici

$ϕ (m) ϕ (n)$ brojeva koji su relativno prosti i sa

$m$ i sa

$n$ , a onda i s

$m n$ .

Stoga je

$ϕ (m n) = ϕ (m) ϕ (n)$ i tvrdnja je dokazana.

Primjer 3. Odredimo

$ϕ (1111)$ . Kako je

$1111 = 11 \cdot 101$ , primjenom svojstva multiplikativnosti Eulerove funkcije i činjenice da su 11 i 101 prosti brojevi dobivamo

$ϕ (1111) = ϕ (11 \cdot 101) = ϕ (11) ϕ (101) = 10 \cdot 100 = 1000 .$

Propozicija 4. Neka je

$p$ prost broj i

$α \in ℕ$ . Tada vrijedi

$ϕ (p^{α}) = p^{α - 1} (p - 1) .$

Proof. Neka je

$p$ prost broj i

$α \geq 1$ . Pozitivni djelitelji broja

$p^{α}$ su

$1, p, \dots, p^{α}$ . Jedini brojevi

$i$ takvi da

$1 \leq i \leq p^{α}$ koji nisu relativno prosti s

$p^{α}$ su višekratnici broja

$p$ , a to su

$1 \cdot p, 2 \cdot p, \dots, p^{α - 1} \cdot p = p^{α}$ . Dakle, ima ih

$p^{α - 1}$ pa je

$ϕ (p^{α}) = p^{α} - p^{α - 1} = p^{α - 1} (p - 1) .$

Kako se svaki prirodan broj veći od 1 može prikazati u obliku

$n = p_{1}^{α_{1}} p_{2}^{α_{2}} \dots p_{k}^{α_{k}}$ ,

$α_{i} \in ℕ$ ,

$p_{i}$ prosti brojevi,

$i \in {1, \dots, k}$ , primjenom svojstva multiplikativnosti Eulerove funkcije i upravo dokazane propozicije, dobivamo

(1)

$ϕ (n) = \prod_{i = 1}^{k} p_{i}^{α_{i} - 1} (p_{i} - 1) = n \prod_{i = 1}^{k} (1 - \frac{1}{p_{i}}) .$

Primjer 5. Odredimo broj prirodnih brojeva koji su relativno prosti s brojem googol tj. s brojem

$10^{100}$ i manji su od njega.

Rješenje: Trebamo odrediti

$ϕ (10^{100})$ . Primjenom prethodne formule dobivamo

$ϕ (10^{100}) = ϕ (2^{100} 5^{100}) = 2^{99} 5^{99} 4 = 4 \cdot 10^{99} .$

$⋄$

Primjer 6. Odredimo sve prirodne brojeve

$n$ za koje je

$ϕ (n)$ neparan broj.

Rješenje: Već smo komentirali da je

$ϕ (1) = 1$ , a lako se vidi i da je

$ϕ (2) = 1$ .

Pretpostavimo da je

$n > 2$ . Ako postoji neparan faktor

$p_{i}$ od

$n$ , onda je

$p_{i} - 1$ paran broj pa je

$ϕ (n)$ paran broj zbog (1). Ako ne postoji neparan faktor

$p_{i}$ od

$n$ , onda je

$n = 2^{α}$ ,

$α \geq 2$ , pa je

$ϕ (n) = 2^{a - 1} (2 - 1) = 2^{a - 1} .$

Kako je

$α - 1 \geq 1$ slijedi da je

$ϕ (n)$ paran broj.

Zaključujemo da je

$ϕ (n)$ neparan broj samo za

$n \in {1, 2}$ .

$⋄$

Primjer 7. Pokažimo da postoji beskonačno mnogo pozitivnih cijelih brojeva

$n$ takvih da je

$ϕ (n) = \frac{n}{3} .$

Rješenje: Za sve

$n = 2 \cdot 3^{m}$ ,

$m \in ℕ$ , vrijedi

$ϕ (n) = ϕ (2 \cdot 3^{m}) = ϕ (2) ϕ (3^{^{m}}) = 3^{m - 1} (3 - 1) = 2 \cdot 3^{m - 1} = \frac{n}{3} .$

Time je tvrdnja dokazana.

$⋄$

3Svojstva Eulerove funkcije

U ovom ćemo dijelu dokazati još neka svojstva Eulerove funkcije.

Propozicija 8. Neka je

$n$ prirodan broj. Ako

$d ∣ n$ , onda

$ϕ (d) ∣ ϕ (n)$ .

Proof. Neka je

$n = p_{1}^{α_{1}} p_{2}^{α_{2}} \dots p_{k}^{α_{k}}$ . Ako

$d ∣ n$ , onda je

$d = p_{1}^{β_{1}} \dots p_{k}^{β_{k}}$ , gdje je

$0 \leq β_{i} \leq α_{i}$ ,

$i = 1, \dots, k$ . Uvrštavanjem u formulu (1) dobije se da je

$\frac{ϕ (n)}{ϕ (d)} = \prod_{i = 1}^{k} p^{α_{i} - β_{i}} .$

Kako je, zbog

$α_{i} - β_{i} \geq 0$ , broj s desne strane ove jednakosti prirodan, time je tvrdnja dokazana.

Propozicija 9.[Gauss] Za sve prirodne brojeve

$n$ vrijedi

$\sum_{d ∣ n} ϕ (d) = n .$

Proof. Neka je

$n = p_{1}^{α_{1}} p_{2}^{α_{2}} \dots p_{k}^{α_{k}}$ . Promatrajmo sljedeći produkt

(2)

$\prod_{i = 1}^{k} (1 + ϕ (p_{i}) + ϕ (p_{i}^{2}) + \dots + ϕ (p_{i}^{α_{i}})) .$

Množenjem faktora ovog produkta dobivamo sumu pribrojnika oblika

$ϕ (p_{1}^{β_{1}}) \dots ϕ (p_{k}^{β_{k}}) = ϕ (p_{1}^{β_{1}} \dots p_{k}^{β_{k}}),$

gdje je

$0 \leq β_{i} \leq α_{i}$ ,

$i = 1, \dots, k$ . Kako su s

$p_{1}^{β_{1}} \dots p_{k}^{β_{k}}$ ,

$0 \leq β_{i} \leq α_{i}$ ,

$i = 1, \dots, k$ , dani svi djelitelji broja

$n$ , zaključujemo da je

(3)

$\sum_{d ∣ n} ϕ (d) = \prod_{i = 1}^{k} (1 + ϕ (p_{i}) + ϕ (p_{i}^{2}) + \dots + ϕ (p_{i}^{α_{i}})) .$

Stoga je

$\sum_{d ∣ n} ϕ (d) = \prod_{i = 1}^{k} (1 + (p_{i} - 1) + (p_{i}^{2} - p_{i}) + \dots + (p_{i}^{α_{i}} - p_{i}^{α_{i} - 1})) = \prod_{i = 1}^{k} p_{i}^{α_{i}} = n$

i time je tvrdnja dokazana.

Propozicija 10. Za svaki prirodan broj

$m$ postoji konačno mnogo prirodnih brojeva

$n$ takvih da je

$ϕ (n) = m$ .

Proof. Ako neka potencija prostog broja

$p$ dijeli

$n$ , tj.

$p^{α} ∣ n$ , prema Propoziciji (8) vrijedi

$p^{α - 1} (p - 1) ∣ ϕ (n) = m$ . No, onda je

$p^{α} \leq \frac{m p}{p - 1} \leq 2 m .$

Kako postoji samo konačno mnogo brojeva

$p^{α}$ takvih da je

$p^{α} \leq 2 m$ , postoji i konačno mnogo produkata takvih potencija prostih brojeva. Stoga postoji i konačno mnogo prirodnih brojeva s danim svojstvom.

U nastavku donosimo dvije ocjene za Eulerovu funkciju.

Propozicija 11. Ako je

$n$ složen prirodan broj, tada je

$ϕ (n) \leq n - \sqrt{n} .$

Proof. Budući da je

$n$ složen broj,

$n$ ima prost faktor

$p_{j} \leq \sqrt{n}$ . Sada imamo

$ϕ (n) = n (1 - \frac{1}{p_{1}}) \dots (1 - \frac{1}{p_{k}}) \leq n (1 - \frac{1}{p_{j}}) \leq n (1 - \frac{1}{\sqrt{n}}) = n - \sqrt{n} .$

Propozicija 12. Za sve prirodne brojeve

$n$ ,

$n \neq 2, 6$ , vrijedi

$ϕ (n) \geq \sqrt{n} .$

Proof. Za

$n = p^{m}$ , gdje je

$p$ prost broj i

$m \geq 2$ , vrijedi

$\frac{m}{2} \leq m - 1$ pa slijedi

(4)

$\begin{matrix} ϕ (n) & = & p^{m - 1} (p - 1) \geq p^{m - 1} \geq \sqrt{p^{m}} = \sqrt{n} . \end{matrix}$

U slučaju kada je

$p \neq 2$ vrijedi i

(5)

$\begin{matrix} ϕ (n) & = & p^{m - 1} (p - 1) \geq p^{m - 1} \sqrt{2} \geq \sqrt{2 p^{m}} = \sqrt{2 n} . \end{matrix}$

Neka je

$n = p$ ,

$p \geq 3$ , gdje je

$p$ prost broj. Lako se vidi da je kvadratna funkcija

$f (x) = x^{2} - x - 1$ pozitivna za

$x > \frac{1 + \sqrt{5}}{2}$ . Uz supstituciju

$x = \sqrt{t}$ dobivamo da za

$t > {(\frac{1 + \sqrt{5}}{2})}^{2}$ vrijedi

$\sqrt{t} < t - 1$ . Stoga za

$p \geq 3$ vrijedi

$\sqrt{p} < p - 1$ pa je

(6)

$\begin{matrix} ϕ (n) & = & p - 1 > \sqrt{p} = \sqrt{n} . \end{matrix}$

$p \geq 5$ analogno se može pokazati da je

(7)

$\begin{matrix} ϕ (n) & = & p - 1 > \sqrt{2 p} = \sqrt{2 n} . \end{matrix}$

Ako je

$n$ neparan ili

$4 ∣ n$ , (4) i (6) povlače da vrijedi

$ϕ (n) = ϕ (p_{1}^{α_{1}}) \dots ϕ (p_{k}^{α_{k}}) \geq \sqrt{p_{1}^{α_{1}}} \dots \sqrt{p_{k}^{α_{k}}} = \sqrt{n} .$

Ako je

$n = 2 k$ , gdje je

$k$ neparan broj, tada za

$n \neq 6$ slijedi da 9 dijeli

$k$ ili

$k$ ima barem jedan prost faktor

$p \geq 5$ . Iz (5)–(7) slijedi

$ϕ (n) = ϕ (k) \geq \sqrt{2 k} = \sqrt{n} .$

4Eulerov teorem

Eulerova funkcija sastavni je dio Eulerovog teorema, jednog od najvažnijih teorema u teoriji brojeva.

Teorem 13.{(Eulerov teorem)} Ako su

$n \in ℕ$ i

$a \in ℤ$ takvi da

$(a, n) = 1$ , onda je

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

Proof. Ako je

${r_{1}, \dots, r_{ϕ (n)}}$ reducirani sustav ostataka modulo

$n$ , onda je, za

$(a, n) = 1$ , i

${a r_{1}, \dots, a r_{ϕ (n)}}$ reducirani sustav ostataka modulo

$n$ (jer iz

$a r_{i} \equiv a r_{j} (\mod n)$ i

$(a, n) = 1$ slijedi

$i = j$ ). No, onda mora vrijediti

$\prod_{j = 1}^{ϕ (n)} a r_{j} \equiv \prod_{i = 1}^{ϕ (n)} r_{i} (\mod n),$

odnosno

$\begin{alignat*}{2} a^{\varphi(n)}\prod\limits_{j=1}^{\varphi(n)}r_{j} \equiv \prod\limits_{i=1}^{\varphi(n)} r_{i} \pmod{n}. \end{alignat*}$ Kako je

$(r_{i}, n) = 1$ ,

$i = 1, \dots, n$ , odavde slijedi

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

Ako je

$n$ prost broj, onda iz Eulerovog teorema direktno slijedi Mali Fermatov teorem.

Korolar 14. (Mali Fermatov teorem) Neka je

$p$ prost broj. Ako

$p ∤ a$ , onda je

$a^{p - 1} \equiv 1 (\mod p) .$

Primjer 15. Odredimo ostatak pri dijeljenju broja

$2017^{10^{6}}$ sa 55.

Rješenje: Kako je

$ϕ (55) = ϕ (5) ϕ (11) = 40$ i

$(2017, 55) = 1$ , iz Eulerovog teorema slijedi

$2017^{40} \equiv 1 (\mod 55) .$

No, onda je

$2017^{10^{6}} \equiv 2017^{40 \cdot 25000} \equiv 1 (\mod 55) .$

Stoga je traženi ostatak 1.

$⋄$

Primjer 16. Odredimo posljednje tri znamenke u decimalnom zapisu broja

$3^{4004}$ .

Rješenje: Uočimo da rješenje možemo dobiti određivanjem ostatka pri dijeljenju danog broja s 1000. Budući da je

$ϕ (1000) = ϕ (2^{3}) ϕ (5^{3}) = 400$ i

$(3, 1000) = 1$ primjenom Eulerovog teorema dobivamo

$3^{400} \equiv 1 (\mod 1000),$

odakle slijedi

$3^{4004} \equiv 3^{400 \cdot 10 + 4} \equiv 3^{4} \equiv 81 (\mod 1000) .$

Odavde zaključujemo da su zadnje tri znamenke broja

$3^{400}$ jednake 081.

$⋄$

Primjer 17. Dokažimo da su prirodni brojevi oblika

$n^{24} + 17$ djeljivi s 18 za sve prirodne brojeve

$n$ za koje je

$(n, 18) = 1$ .

Rješenje: Za

$(n, 18) = 1$ primjenom Eulerovog teorema dobivamo

$n^{ϕ (18)} \equiv n^{6} \equiv 1 (\mod 18)$

pa je

$n^{24} + 17 \equiv 1 + 17 \equiv 0 (\mod 18)$

i time je tvrdnja dokazana.

$⋄$

Spomenimo samo da Eulerov teorem i Mali Fermatov teorem imaju dvije važne primjene:

$∙$	Najpoznatiji kriptosustav s javnim ključem, RSA kriptosustav, bazira se na Eulerovom teoremu (vidi npr. [12]).
$∙$	Iako obrat Malog Fermatovog teorema ne vrijedi (može se pokazati da je npr. $2^{340} \equiv 1 (\mod 341)$ , ali $341 = 11 \cdot 31$ ), Mali Fermatov teorem je baza za razne testove prostosti (vidi npr. [16]).

5Problemi vezani uz Eulerovu funkciju

U ovom dijelu opisat ćemo neke od poznatih problema koji su vezani uz Eulerovu funkciju.

5.1Gauss-Wantzelov teorem

Kažemo da je pravilni

$n$ -terokut konstruktibilan ako se može konstruirati samo pomoću ravnala i šestara. Gauss je 1796. godine pokazao da je pravilni

$17$ -terokut konstruktibilan, a u Disquisitiones Arithmeticae je poopćio ovaj rezultat te je dokazao uvjet dovoljnosti iz teorema koji ćemo navesti. Uvjet nužnosti dokazao dokazao je Wantzel [18] 1837. godine.

Tvrdnja teorema u uskoj je vezi s Fermatovim prostim brojevima tj. prostim brojevima oblika

$F_{n} = 2^{2^{n}} + 1$ . Poznato je samo 5 prostih Fermatovih brojeva (to su

$F_{0} = 3$ ,

$F_{1} = 5$ ,

$F_{2} = 17$ ,

$F_{3} = 257$ i

$F_{4} = 65537$ ) i otvoreni je problem ima li ih još.

Teorem 18. Pravilan

$n$ -terokut može se konstruirati ravnalom i šestarom ako i samo ako se

$n$ može prikazati u obliku produkta neke potencije broja dva i različitih Fermatovih prostih brojeva tj.

$n = 2^{i} F_{n_{1}} \dots F_{n_{j}}$ , gdje su

$n \geq 3$ ,

$i \geq 0$ ,

$j \geq 0$ i

$F_{n_{1}}, \dots, F_{n_{j}}$ su različiti Fermatovi prosti brojevi.

Wantzel je pokazao da se Teorem (18) može izreći i na sljedeći način:

Teorem 19. Pravilan

$n$ -terokut može se konstruirati ravnalom i šestarom ako i samo ako je

$n$ prirodan broj veći od 2 takav da je

$ϕ (n)$ potencija broja 2.

5.2Lehmerov problem

Znamo da za prost broj

$p$ vrijedi

$ϕ (p) = p - 1$ . Lehmer je 1932. godine postavio pitanje postoje li složeni brojevi

$n$ takvi da

$ϕ (n) ∣ n - 1$ . Pretpostavlja se da takvi brojevi ne postoje i danas je ta pretpostavka poznata kao Lehmerov problem/slutnja o Eulerovoj funkciji:

Ne postoji složen prirodan broj

$n$ sa svojstvom da

$ϕ (n) ∣ n - 1$ .

1933. godine Lehmer je dokazao da ako takav

$n$ postoji, mora biti neparan, kvadratno slobodan i djeljiv s barem 7 prostih brojeva, odnosno

$ω (n) \geq 7$ (

$ω$ je funkcija koja "broji" sve proste djelitelje zadanog broja

$n$ ). Cohen i Hagis [6] dokazali su 1980. godine da je

$n > 10^{20}$ i

$ω (n) \geq 14$ . Burcsi, Czirbusz i Farkas su 2011. pokazali da ako

$3 ∣ n$ , onda je

$n > 10^{360000000}$ i

$ω (n) \geq 40000000$ .

5.3Carmichaelova slutnja i Fordov teorem

1907. godine Carmichael [3] je objavio teorem u kojem je tvrdio da ne postoji broj

$n$ takav da za sve

$m \neq n$ vrijedi

$ϕ (n) \neq ϕ (m)$ . Međutim, 1922. godine pronađena je greška u dokazu. Iako tvrdnja još uvijek nije dokazana, pretpostavlja se da je točna i danas je ta pretpostavka poznata kao Carmichaelova slutnja. Često se iskazuje i u sljedećem obliku:

Za sve prirodne brojeve

$n$ jednadžba

$ϕ (x) = n$ ne može imati jedinstveno rješenje.

Carmichael [4] je dokazao da kontraprimjer njegovoj pretpostavci mora biti broj veći ili jednak od

$10^{37}$ . Pomerance [15] je pokazao 1974. da je prirodan broj

$n$ kontraprimjer ovoj pretpostavci ako za svaki prost broj

$p$ takav da

$p - 1 ∣ ϕ (n)$ vrijedi

$p^{2} ∣ n$ . Ford [9] je 1998. godine pokazao da eventualni kontraprimjer mora biti veći od

$10^{10^{10}}$ .

Vezano uz broj rješenja jednadžbe

$ϕ (x) = n$ poznata je i slutnja koju je iznio Sierpi

$\overset{ʹ}{n}$ ski:

Za svaki prirodni broj

$k \geq 2$ postoji prirodni broj

$n$ takav da jednadžba

$ϕ (x) = n$ ima točno

$k$ rješenja.

Ford [10] je 1998. dokazao da je slutnja točna.

Bibliografija

[1]	T. Andreescu, D. Andrica, Number theory, Birkhäuser, Basel, 2009.
[2]	P. Burcsi, S. Czirbusz, G. Farkas, Computational investigation of Lehmer's totient problem, Ann. Univ. Sci. Budap. Rolando Eötvös, Sect. Comput. 35 (2011), 43–49.
[3]	R. D. Carmichael, On Eulers $ϕ$ -function, Bull. Amer. Math. Soc. (N.S.) 13 (1907), 241–243.
[4]	R. D. Carmichael, Note on Eulers $ϕ$ -function, Bull. Amer. Math. Soc. (N.S.) 28 (1922), 109–110.
[5]	P. L. Clark, Number Theory: A Contemporary Introduction, http://math.uga.edu/ pete/4400FULL.pdf
[6]	G. L. Cohen, P. Hagis, On the Number of Prime Factors of $n$ if $ϕ (n) ∣ (n - 1)$ }, Nieuw Arch. Wiskd. 28 (1980), 177–185.
[7]	A. Dujella, Uvod u teoriju brojeva, PMF - Matematički odjel, Sveučilište u Zagrebu, skripta.
[8]	L. Euler, Theoremata arithmetica nova methodo demonstrata, Novi commentarii academiae scientiarum imperialis Petropolitanae 8 (1763), 74–104.
[9]	K. Ford, The number of solutions of $ϕ (x) = m$ , Ann. of Math. 150 (1999), 283–311.
[10]	K. Ford, The distribution of totients, Ramanujan J. 2 (1998), 67–151.
[11]	C. F. Gauss, Disquisitiones Arithmeticae, Leipzig, Germany, 1801, (Yale University Press, New Haven, 1965).
[12]	B. Ibrahimpašić, RSA kriptosustav, Osječki matematički list 5 (2005), 101–112.
[13]	G. A. Jones, J. M. Jones, Elementary Number Theory, Springer, 2003.
[14]	R. A. Mollin, Fundamental Number Theory with Applications, CRC Press, New York, 2008.
[15]	C. Pomerance, On Carmichael's conjecture, Proc. Amer. Math. Soc. 43 (1974), 297–298.
[16]	H. Riesel, Prime Numbers and Computer Methods for Factorization, Birkh $\overset{..}{a}$ user, Boston, 1994.
[17]	J. J. Sylvester, On certain ternary cubic-form equations, Amer. J. Math. 2 (1879), 357–393.
[18]	P. L. Wantzel, Recherches sur les moyens de reconnaître si un problème de géométrie peut se résoudre avec la règle et le compas, J. Math. Pures Appliq. 1(1836), 366–372.

math.e

Secondary links

Novi brojevi časopisa math.e

Matematička događanja

Kalendar

Srpanj

Matematički blogovi

Sponzori

Mali Fermatov teorem

Eulerova funkcija

Eulerova funkcija