.
Η συνάρτηση 'Οιλερ (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) \) χρησιμοποιώντας την αντιστροφή του Μέμπιους στο:
\( n=\sum_{d\mid n} \phi(d) \)
Ο τύπος αυτός είναι ο εξής:
\( \phi(n)=\sum_{d\mid n}d \cdot \mu(n/d) \)
όπου με \mu συμβολίζουμε την συνάρτηση του Μέμπιους πάνω από τους φυσικούς αριθμούς.
Hellenica World - Scientific Library
Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License
