Eulerova funkcija

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

Prvih tisuću vrijednosti Eulerove funkcije. Točke na gornjoj liniji predstavljaju vrijednosti za proste brojeve.

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

Uočimo da je $\phi (1)=1,\phi (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 $\phi (1)=1$ te $\phi (mn)=\phi (m)\phi (n)$,

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

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

▪ Vrijedi $\sum _{d\mid n}\phi (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,\mathrm{\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\ge 3$ kardinalnost skupova $S_n$ paran broj, a znamo da je $\phi (1)=\phi (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_{10}=\{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\}$.