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}
Za 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 brojn 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 brojeven 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 brojk\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 ofn 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.
 


  • Share this

Eulerova funkcija


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



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 π, 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 Un označimo skup svih prirodnih brojeva koji nisu veći od n i relativno su prosti s n, tj.
 
Un={k∈ℕ:1≤k≤n   i   (n,k)=1},
 
tada Eulerovu funkciju možemo definirati kao funkciju ϕ:ℕ→ℕ zadanu s ϕ(n)=#Un.

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⊆ℤ koji sadrži po točno jedan element iz svake od ϕ(n) klasa ekvivalencije od Un.

U nastavku ćemo dokazati jedno važno svojstvo Eulerove funkcije, a to je tzv. svojstvo multiplikativnosti. Multiplikativne funkcije su funkcije f:ℕ→ℂ 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 ϕ(1)=1. Neka su m,n prirodni brojevi sa svojstvom da je (m,n)=1. Posložimo brojeve 1,2,…,mn u tablicu s n redova i m stupaca na sljedeći način:
 
123…mm+1m+2m+3…2m⋮⋮⋮⋮(n-1)m+1(n-1)m+2(n-1)m+3…nm
 
U ovom nizu brojeva postoji, prema definiciji, ϕ(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 ϕ(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 Sk skup koji sadrži sve elemente toga stupca, tj. Sk={k,m+k,2m+k,…,(n-1)m+k}. Dokažimo da su u skupu Sk svi elementi međusobno nekongruentni. Ako bi postojali i,j∈{0,1,…,n-1} takvi da vrijedi
 
im+k≡jm+k   (modn),
 
onda oduzimanjem broja k i korištenjem činjenice da je (m,n)=1 dobivamo da je i≡j   (modn) pa je i=j.

Kako Sk ima n međusobno nekongruentnih elemenata modulo n zaključujemo da u Sk imamo predstavnike svih mogućih klasa modulo n (tj. Sk je potpun sustav ostataka modulo n). Neka je Rk skup koji sadrži elemente skupa Sk koji su relativno prosti s n. Tada je Rk 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 mn.

Stoga je ϕ(mn)=ϕ(m)ϕ(n) i tvrdnja je dokazana.
     

Primjer 3. Odredimo ϕ(1111). Kako je 1111=11⋅101, primjenom svojstva multiplikativnosti Eulerove funkcije i činjenice da su 11 i 101 prosti brojevi dobivamo
 
ϕ(1111)=ϕ(11⋅101)=ϕ(11)ϕ(101)=10⋅100=1000.
 

Propozicija 4. Neka je p prost broj i α∈ℕ. Tada vrijedi
 
ϕ(pα)=pα-1(p-1).
 

Proof. Neka je p prost broj i α≥1. Pozitivni djelitelji broja pα su 1,p,…,pα. Jedini brojevi i takvi da 1≤i≤pα koji nisu relativno prosti s pα su višekratnici broja p, a to su 1⋅p,2⋅p,…,pα-1⋅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=p1α1p2α2⋯pkαk, αi∈ℕ, pi prosti brojevi, i∈{1,…,k}, primjenom svojstva multiplikativnosti Eulerove funkcije i upravo dokazane propozicije, dobivamo
 
(1)
ϕ(n)=∏i=1kpiαi-1pi-1=n∏i=1k1-1pi.
 

Primjer 5. Odredimo broj prirodnih brojeva koji su relativno prosti s brojem googol tj. s brojem 10100 i manji su od njega.


Rješenje: Trebamo odrediti ϕ(10100). Primjenom prethodne formule dobivamo
 
ϕ(10100)=ϕ(21005100)=2995994=4⋅1099.
 
 ⋄



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 pi od n, onda je pi-1 paran broj pa je ϕ(n) paran broj zbog (1). Ako ne postoji neparan faktor pi od n, onda je n=2α, α≥2, pa je
 
ϕ(n)=2a-1(2-1)=2a-1.
 
Kako je α-1≥1 slijedi da je ϕ(n) paran broj.

Zaključujemo da je ϕ(n) neparan broj samo za n∈{1,2}. ⋄



Primjer 7. Pokažimo da postoji beskonačno mnogo pozitivnih cijelih brojeva n takvih da je
 
ϕ(n)=n3.
 

Rješenje: Za sve n=2⋅3m, m∈ℕ, vrijedi
 
ϕ(n)=ϕ(2⋅3m)=ϕ(2)ϕ(3m)=3m-1(3-1)=2⋅3m-1=n3.
 
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=p1α1p2α2⋯pkαk. Ako d∣n, onda je d=p1β1⋯pkβk, gdje je 0≤βi≤αi, i=1,…,k. Uvrštavanjem u formulu (1) dobije se da je
 
ϕ(n)ϕ(d)=∏i=1kpαi-βi.
 
Kako je, zbog αi-βi≥0, broj s desne strane ove jednakosti prirodan, time je tvrdnja dokazana.
     

Propozicija 9.[Gauss] Za sve prirodne brojeve n vrijedi
 
∑d∣nϕ(d)=n.
 

Proof. Neka je n=p1α1p2α2⋯pkαk. Promatrajmo sljedeći produkt
 
(2)
∏i=1k(1+ϕ(pi)+ϕ(pi2)+⋯+ϕ(piαi)).
 
Množenjem faktora ovog produkta dobivamo sumu pribrojnika oblika
 
ϕ(p1β1)⋯ϕ(pkβk)=ϕ(p1β1⋯pkβk),
 
gdje je 0≤βi≤αi, i=1,…,k. Kako su s p1β1⋯pkβk, 0≤βi≤αi, i=1,…,k, dani svi djelitelji broja n, zaključujemo da je
 
(3)
∑d∣nϕ(d)=∏i=1k(1+ϕ(pi)+ϕ(pi2)+⋯+ϕ(piαi)).
 
Stoga je
 
∑d∣nϕ(d)=∏i=1k(1+(pi-1)+(pi2-pi)+⋯+(piαi-piαi-1))=∏i=1kpiα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α≤mpp-1≤2m.
 
Kako postoji samo konačno mnogo brojeva pα takvih da je pα≤2m, 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)≤n-n.
 

Proof. Budući da je n složen broj, n ima prost faktor pj≤n. Sada imamo
 
ϕ(n)=n1-1p1⋯1-1pk≤n1-1pj≤n1-1n=n-n.
 
     

Propozicija 12. Za sve prirodne brojeve n, n≠2,6, vrijedi
 
ϕ(n)≥n.
 

Proof. Za n=pm, gdje je p prost broj i m≥2, vrijedi m2≤m-1 pa slijedi
 
(4)
ϕ(n)=pm-1(p-1)≥pm-1≥pm=n.
 
U slučaju kada je p≠2 vrijedi i
 
(5)
ϕ(n)=pm-1(p-1)≥pm-12≥2pm=2n.
 

Neka je n=p, p≥3, gdje je p prost broj. Lako se vidi da je kvadratna funkcija f(x)=x2-x-1 pozitivna za x>1+52. Uz supstituciju x=t dobivamo da za t>1+522 vrijedi t<t-1. Stoga za p≥3 vrijedi p<p-1 pa je
 
(6)
ϕ(n)=p-1>p=n.
 
Za p≥5 analogno se može pokazati da je
 
(7)
ϕ(n)=p-1>2p=2n.
 

Ako je n neparan ili 4∣n, (4) i (6) povlače da vrijedi
 
ϕ(n)=ϕ(p1α1)⋯ϕ(pkαk)≥p1α1⋯pkαk=n.
 

Ako je n=2k, gdje je k neparan broj, tada za n≠6 slijedi da 9 dijeli k ili k ima barem jedan prost faktor p≥5. Iz (5)–(7) slijedi
 
ϕ(n)=ϕ(k)≥2k=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∈ℕ i a∈ℤ takvi da (a,n)=1, onda je
 
aϕ(n)≡1   (modn).
 

Proof. Ako je {r1,…,rϕ(n)} reducirani sustav ostataka modulo n, onda je, za (a,n)=1, i {ar1,…,arϕ(n)} reducirani sustav ostataka modulo n (jer iz ari≡arj   (modn) i (a,n)=1 slijedi i=j). No, onda mora vrijediti
 
∏j=1ϕ(n)arj≡∏i=1ϕ(n)ri   (modn),
 
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 (ri,n)=1, i=1,…,n, odavde slijedi
 
aϕ(n)≡1   (modn).
 
     


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
 
ap-1≡1   (modp).
 


 

Primjer 15. Odredimo ostatak pri dijeljenju broja 2017106 sa 55.


Rješenje: Kako je ϕ(55)=ϕ(5)ϕ(11)=40 i (2017,55)=1, iz Eulerovog teorema slijedi
 
201740≡1   (mod55).
 
No, onda je
 
2017106≡201740⋅25000≡1   (mod55).
 
Stoga je traženi ostatak 1.  ⋄

Primjer 16. Odredimo posljednje tri znamenke u decimalnom zapisu broja 34004.


Rješenje: Uočimo da rješenje možemo dobiti određivanjem ostatka pri dijeljenju danog broja s 1000. Budući da je ϕ(1000)=ϕ(23)ϕ(53)=400 i (3,1000)=1 primjenom Eulerovog teorema dobivamo
 
3400≡1   (mod1000),
 
odakle slijedi
 
34004≡3400⋅10+4≡34≡81   (mod1000).
 
Odavde zaključujemo da su zadnje tri znamenke broja 3400 jednake 081.  ⋄

Primjer 17. Dokažimo da su prirodni brojevi oblika n24+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)≡n6≡1   (mod18)
 
pa je
 
n24+17≡1+17≡0   (mod18)
 
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. 2340≡1   (mod341), ali 341=11⋅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 Fn=22n+1. Poznato je samo 5 prostih Fermatovih brojeva (to su F0=3, F1=5, F2=17, F3=257 i F4=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=2iFn1⋯Fnj, gdje su n≥3, i≥0, j≥0 i Fn1,…,Fnj 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 brojn 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)≥7 (ω je funkcija koja "broji" sve proste djelitelje zadanog broja n). Cohen i Hagis [6] dokazali su 1980. godine da je n>1020 i ω(n)≥14. Burcsi, Czirbusz i Farkas su 2011. pokazali da ako 3∣n, onda je n>10360000000 i ω(n)≥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≠n vrijedi ϕ(n)≠ϕ(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 brojeven 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 1037. 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 p2∣n. Ford [9] je 1998. godine pokazao da eventualni kontraprimjer mora biti veći od 101010.

Vezano uz broj rješenja jednadžbe ϕ(x)=n poznata je i slutnja koju je iznio Sierpinʹski:

Za svaki prirodni brojk≥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 ofn 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, Birkha..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.
 

 

 

  • Share this