Eulerova funkcija

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

Primjerice, [math]\displaystyle{ \varphi(2) = 1, \varphi(6) = 2, \varphi(11) = 10, }[/math] itd.

Uočimo da je [math]\displaystyle{ \varphi(1) = 1, \varphi(p) = p - 1 }[/math] gdje je [math]\displaystyle{ p }[/math] bilo koji prosti broj.

Skup relativno prostih brojeva s [math]\displaystyle{ n }[/math] u [math]\displaystyle{ \{1, 2, ... n\} }[/math] označavat ćemo sa [math]\displaystyle{ S_n }[/math].

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

Osnovna svojstva

▪Eulerova funkcija je multiplikativna, odnosno vrijedi [math]\displaystyle{ \varphi{(mn)} = \varphi(m)\varphi(n) }[/math],

▪[math]\displaystyle{ \varphi(p^{\alpha}) = p^{\alpha} - p^{\alpha - 1}, }[/math]

▪ Vrijedi [math]\displaystyle{ \varphi(n) =n \prod_{p\mid n} \left(1-\frac{1}{p}\right), }[/math]

▪ Vrijedi [math]\displaystyle{ \sum_{d \mid n}\varphi(d) = n }[/math] (Gaussova lema o Eulerovoj funkciji).

Struktura skupa [math]\displaystyle{ S_n }[/math]

Uzmimo [math]\displaystyle{ n = 20. }[/math] Navodimo skup [math]\displaystyle{ S_{20} }[/math] relativno prostih brojeva s 20 manjih od 20:

[math]\displaystyle{ S_{20} = \{1, 3, 7, 9, 11, 13, 17, 19\}. }[/math]

Uočimo da je [math]\displaystyle{ 1 + 19 = 3 + 17 = 7 + 13 = 9 + 11 = 20. }[/math]

Pretpostavljamo da struktura skupa [math]\displaystyle{ S_{n} = \{k_1 = 1, k_2, ..., k_r = n - 1\} }[/math] ima sljedeću invarijantu: [math]\displaystyle{ k_i + k_{n - i} = n, \forall i = 1, 2, ..., r. }[/math]

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

Zato je za [math]\displaystyle{ n \geq 3 }[/math] kardinalnost skupova [math]\displaystyle{ S_n }[/math] paran broj, a znamo da je [math]\displaystyle{ \varphi(1) = \varphi(2) = 1. }[/math]

Dodatna svojstva djeljivosti elemenata skupa [math]\displaystyle{ S_n }[/math]

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

Ako je [math]\displaystyle{ n }[/math] paran

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

Ako je [math]\displaystyle{ n }[/math] neparan

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

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