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.




Ukoliko sa $U{}_n$ označimo skup svih prirodnih brojeva koji nisu veći od $n$ i relativno su prosti s $n$, tj. tada Eulerovu funkciju možemo definirati kao funkciju $\varphi :\mathbb{N}\to \mathbb{N}$ zadanu s $\varphi \left(n\right)=\#U{}_n$.

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



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

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 \left(n\right)$ 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}\to ℂ$ za koje vrijedi:

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

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 \{1,\dots ,k\}$, primjenom svojstva multiplikativnosti Eulerove funkcije i upravo dokazane propozicije, dobivamo


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





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

Pretpostavimo da je $n>2$. Ako postoji neparan faktor $p{}_i$ od $n$, onda je $p{}_i-1$ paran broj pa je $\varphi \left(n\right)$ paran broj zbog (1). Ako ne postoji neparan faktor $p{}_i$ od $n$, onda je $n=2{}^{\alpha }$, $\alpha \ge 2$, pa je Kako je $\alpha -1\ge 1$ slijedi da je $\varphi \left(n\right)$ paran broj.

Zaključujemo da je $\varphi \left(n\right)$ neparan broj samo za $n\in \{1,2\}$. $\diamond$






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








U nastavku donosimo dvije ocjene za Eulerovu funkciju.








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




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







Rješenje: Kako je $\varphi \left(55\right)=\varphi \left(5\right)\varphi \left(11\right)=40$ i $(2017,55)=1$, iz Eulerovog teorema slijedi No, onda je Stoga je traženi ostatak 1.  $\diamond$



Rješenje: Uočimo da rješenje možemo dobiti određivanjem ostatka pri dijeljenju danog broja s 1000. Budući da je $\varphi \left(1000\right)=\varphi \left(2{}^3\right)\varphi \left(5{}^3\right)=400$ i $(3,1000)=1$ primjenom Eulerovog teorema dobivamo odakle slijedi Odavde zaključujemo da su zadnje tri znamenke broja $3{}^{400}$ jednake 081.  $\diamond$



Rješenje: Za $(n,18)=1$ primjenom Eulerovog teorema dobivamo pa je i time je tvrdnja dokazana. $\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 \left(\mathrm{mod}341\right)$, ali $341=11\cdot 31$), Mali Fermatov teorem je baza za razne testove prostosti (vidi npr. [16]).

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


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š.



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



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

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




1907. godine Carmichael [3] je objavio teorem u kojem je tvrdio da ne postoji broj $n$ takav da za sve $m\ne n$ vrijedi $\varphi \left(n\right)\ne \varphi \left(m\right)$. 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: 



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 \left(n\right)$ 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 \left(x\right)=n$ poznata je i slutnja koju je iznio Sierpi$\stackrel{ʹ}{\mathrm{n}}$ski:

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