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
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
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:
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
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.
\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 (
\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.
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
Množenjem faktora ovog produkta dobivamo sumu pribrojnika oblika
Stoga je
(2)
\prod\limits_{i=1}^{k}(1 + \varphi(p_{i}) + \varphi(p_{i}^{2}) +\cdots+ \varphi(p_{i}^{\alpha_{i}})).
\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}})).
\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
U slučaju kada je p\ne 2 vrijedi i
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
Za p\ge 5 analogno se može pokazati da je
Ako je n neparan ili 4\mid n, (4 ) i (6 ) povlače da vrijedi
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
(4)
\begin{eqnarray} \varphi(n)&=&p^{m-1}(p-1) \ge p^{m-1}\geq \sqrt{p^{m}}=\sqrt{n}. \end{eqnarray}
(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}
(7)
\begin{eqnarray} \varphi(n)&=&p-1 \gt \sqrt{2p}=\sqrt{2n}. \end{eqnarray}
Ako je n neparan ili 4\mid n, (
\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 (
\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. |
| \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. |
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
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
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
5.3Carmichaelova slutnja i Fordov teorem
1907. godine Carmichael
Za sve prirodne brojeven jednadžba \varphi(x)= n ne može imati jedinstveno rješenje.}
Carmichael
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
Bibliografija
