Συνάρτηση Όιλερ
Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Η συνάρτηση 'Οιλερ (αγγλ. Euler - από τον μαθηματικό Λέοναρντ Όιλερ Leonhard Euler) , η οποία έχει καθιερωθεί να συμβολίζεται με το ελληνικό γράμμα φ, είναι μια αριθμοθεωρητική συνάρτηση η οποία ορίζεται στους θετικούς ακέραιους αριθμούς.
Για κάθε θετικό ακέραιο n, το μας δίνει το πλήθος των φυσικών αριθμών οι οποίοι είναι μικρότεροι ή ίσοι με το n και οι οποίοι είναι πρώτοι με το n (έχουν δηλαδή μέγιστο κοινό διαιρέτη 1).
Για παράδειγμα ας θεωρήσουμε τον αριθμό 6. To είναι με 3 αφού από τους φυσικούς αριθμούς από το 1 μέχρι το 6 ακριβώς οι 1, 5 είναι πρώτοι με το 6.
Η συνάρτηση του Euler είναι πολύ χρήσιμη στην Θεωρία αριθμών. Αρκεί και μόνο να παρατηρήσει κάποιος ότι το πλήθος των στοιχείων της πολλαπλασιαστικής ομάδας των ακεραίων modulo n είναι ακριβώς . Αυτό το γεγονός, μαζί με το θεώρημα του Lagrange, μας δίνουν την απόδειξη για το Θεώρημα του Euler που αποτελεί γενίκευση του μικρού θεωρήματος του Φερμά.
[Επεξεργασία] Ιδιότητες
Η συνάρτηση του Euler είναι πολλαπλασιαστική συνάρτηση που σημαίνει ότι για δύο φυσικούς m,n με μκδ(m, n) =1 ισχύει
Είναι εύκολο να παρατηρήσει κάποιος ότι αν ο n είναι πρώτος αριθμός τότε όλοι οι φυσικοί που είναι μικρότεροι από αυτόν είναι πρώτοι με το n οπότε
Με χρήση των παραπάνω και του Κινέζικου Θεωρήματος Υπολοίπων η τιμή της φ(n) μπορεί να υπολογιστεί με χρήση του Θεμελιώδους Θεωρήματος της Αριθμητικής: αν
όπου τα pj είναι διακεκριμένοι πρώτοι αριθμοί, τότε
Ο τελευταίος τύπος μπορεί να γραφτεί και ως εξής:
όπου το γινόμενο διατρέχει όλα τα pr.
[Επεξεργασία] Παραδείγματα
επειδή το 101 είναι πρώτος
[Επεξεργασία] Παρατηρήσεις
Μπορούμε να χρησιμοποιήσουμε επίσης την συνάρτηση αντιστροφής του Möbius για να "αντιστρέψουμε" το γινόμενο σε άθροισμα και να πάρουμε έναν άλλο τύπο για την φ(n):
όπου με μ συμβολίζουμε την συνάρτηση του Möbius πάνω από τους φυσικούς αριθμούς.