Η συνάρτηση 'Οιλερ (Euler's totient function) (Euler - από τον μαθηματικό Λέοναρντ Όιλερ Leonhard Euler) , η οποία έχει καθιερωθεί να συμβολίζεται με το ελληνικό γράμμα φ, είναι μια αριθμοθεωρητική συνάρτηση η οποία ορίζεται στους θετικούς ακέραιους αριθμούς.

Για κάθε θετικό ακέραιο \( \,n \), το \( \varphi(n) \) μας δίνει το πλήθος των φυσικών αριθμών οι οποίοι είναι μικρότεροι ή ίσοι με το \( \,n\) και οι οποίοι είναι πρώτοι (σχετικά πρώτοι) με το \( \,n \) (έχουν δηλαδή μέγιστο κοινό διαιρέτη τη μονάδα).

Για παράδειγμα ας θεωρήσουμε τον αριθμό 6. To \( \varphi(6)\) είναι ίσο με 2, αφού από τους φυσικούς αριθμούς από το 1 μέχρι το 6 ακριβώς δύο, οι 1 και 5, είναι πρώτοι με το 6.

Η συνάρτηση του Όιλερ είναι πολύ χρήσιμη στην θεωρία αριθμών. Αρκεί και μόνο να παρατηρήσει κάποιος ότι το πλήθος των στοιχείων της πολλαπλασιαστικής ομάδας των ακεραίων modulo n είναι ακριβώς \varphi(n). Αυτό το γεγονός, μαζί με το θεώρημα του Λαγκράνζ, μας δίνουν την απόδειξη για το θεώρημα του Όιλερ που αποτελεί γενίκευση του μικρού θεωρήματος του Φερμά.

Ιδιότητες

\( \varphi(1) =1 \)

Η συνάρτηση του Όιλερ είναι πολλαπλασιαστική συνάρτηση που σημαίνει ότι για δύο φυσικούς m,n με μκδ(m, n) =1 ισχύει \( \varphi (mn) = \varphi (m) \varphi (n). \)

Είναι εύκολο να παρατηρήσει κάποιος ότι αν ο n είναι πρώτος αριθμός τότε όλοι οι φυσικοί που είναι μικρότεροι από αυτόν είναι πρώτοι με το n, οπότε \varphi(n) = n-1.

Με χρήση των παραπάνω και του Κινέζικου Θεωρήματος Υπολοίπων η τιμή της \( \phi(n) \) μπορεί να υπολογιστεί με χρήση του Θεμελιώδους Θεωρήματος της Αριθμητικής:

Αν \( n = p_1^{k_1} \cdots p_r^{k_r} \), όπου τα \( \,p_j \) είναι διακεκριμένοι πρώτοι αριθμοί, τότε

\( \phi(n)=(p_{1}-1)p_{1}^{k_{1}-1} \cdots (p_{r}-1)p_{r}^{k_{r}-1}. \)

Ο τελευταίος τύπος μπορεί να γραφτεί και ως εξής:

\( \phi(n)=n\prod_{p|n}\left(1-\frac{1}{p}\right) \)

όπου το γινόμενο διατρέχει όλα τα pr.
Παραδείγματα

\( \varphi(101) = 100 \) επειδή το 101 είναι πρώτος

\( \phi(36)=\phi(3^22^2)=36\left(1-\frac{1}{3}\right)\left(1-\frac{1}{2}\right)=36\cdot\frac{2}{3}\cdot\frac{1}{2}=12 \)

Παρατηρήσεις

Μπορούμε να χρησιμοποιήσουμε επίσης την συνάρτηση αντιστροφής του Μέμπιους για να "αντιστρέψουμε" το γινόμενο σε άθροισμα και να πάρουμε έναν άλλο τύπο για την \( \phi(n) \):

\( \phi(n)=\sum_{d\mid n} d \cdot \mu(n/d) \)

όπου με \( \mu \) συμβολίζουμε την συνάρτηση του Μέμπιους πάνω από τους φυσικούς αριθμούς.

Μαθηματική Εγκυκλοπαίδεια

Scientific Library