Συνάρτηση Όιλερ

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια

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

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

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

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

[Επεξεργασία] Ιδιότητες

\varphi(1) =1

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

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

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

n = p_1^{k_1} \cdots p_r^{k_r}

όπου τα pj είναι διακεκριμένοι πρώτοι αριθμοί, τότε

\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

[Επεξεργασία] Παρατηρήσεις

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

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

όπου με μ συμβολίζουμε την συνάρτηση του Möbius πάνω από τους φυσικούς αριθμούς.