Eulerova funkcija

Eulerova funkcija je funkcija koja svakom prirodnom broju $n$ pridružuje broj relativno prostih s $n$ koji su manji od $n$ (ili jednaki kada je $n=1$). Označavamo ju s $\varphi {(n)}$.

Primjerice, $\varphi (2)=1,\varphi (6)=2,\varphi (11)=10,$ itd.

Uočimo da je $\varphi (1)=1,\varphi (p)=p-1$ gdje je $p$ bilo koji prosti broj.

Skup relativno prostih brojeva s $n$ u $\{1,2,...n\}$ označavat ćemo sa $S_{n}$.

Ovu je funkciju 1763. uveo znameniti švicarski matematičar Leonhard Euler.

Osnovna svojstva

▪Eulerova funkcija je multiplikativna, odnosno vrijedi $\varphi {(mn)}=\varphi (m)\varphi (n)$,

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

▪ Vrijedi $\varphi (n)=n\prod _{p\mid n}\left(1-{\frac {1}{p}}\right),$

▪ Vrijedi $\sum _{d\mid n}\varphi (d)=n$ (Gaussova lema o Eulerovoj funkciji).

Struktura skupa $S_{n}$

Uzmimo $n=20.$ Navodimo skup $S_{20}$ relativno prostih brojeva s 20 manjih od 20:

$S_{20}=\{1,3,7,9,11,13,17,19\}.$

Uočimo da je $1+19=3+17=7+13=9+11=20.$

Pretpostavljamo da struktura skupa $S_{n}=\{k_{1}=1,k_{2},...,k_{r}=n-1\}$ ima sljedeću invarijantu: $k_{i}+k_{n-i}=n,\forall i=1,2,...,r.$

Sada ćemo tvrdnju ovog naslućivanja i dokazati. Neka je $k\in \mathbb {N}$ takav da $M(k,n)=1.$ Želimo pokazati da je tada nužno $M(n-k,n)=1.$ Pretpostavimo da je $M(n-k,n)=d>1.$ To bi značilo da $d|n,d|n-k.$ Da bi izraz $n-k$ bio djeljiv s $d$ mora biti $d|k.$ To povlači $d=1,$ što je i trebalo dokazati.

Zato je za $n\geq 3$ kardinalnost skupova $S_{n}$ paran broj, a znamo da je $\varphi (1)=\varphi (2)=1.$

Dodatna svojstva djeljivosti elemenata skupa $S_{n}$

Isto tako, treba uočiti da vrijedi sljedeće.

Ako je $n$ paran

Ako je dakle $n=2k$, tada je razlika bilo koja dva člana skupa $S_{2n}$ paran broj. Ovo slijedi iz činjenice da je očito svaki element skupa $S_{2n}$ neparan. Primjerice $S_{4}=\{1,3,7,9\}$ te $S_{12}=\{1,5,7,11\}$.

Ako je $n$ neparan

Ako je pak $n=2k+1$, primijetimo da razlike elemenata skupa $S_{2n}$ ne moraju nužno sve biti parne, ali s druge strane $k,k+1$ su članovi skupa $S_{2n}$ (pa je njihova razlika najmanji neparni broj, broj $1$), tj. mora biti $M(2k+1,k)=M(2k+1,k+1)=1.$ Naime, iz $M(k+(k+1),k)=d$ slijedi $d|k+1$. No, kako $d|k,d|k+1$ slijedi $d=1$ jer je $M(k,k+1)=1$. (1)

Svojstvo $M(2k+1,k+1)=1$ je ekvivalento s $M(2k+1,2k+1-k)=1$ pa, zbog (1), ono vrijedi. Primjer ovakvog skupa bio bi $S_{9}=\{1,2,4,5,7,8\}$ te primjerice $S_{15}=\{1,2,4,7,8,11,13,14\}$.