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

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Μετάβαση σε: πλοήγηση, αναζήτηση

Η συνάρτηση 'Οιλερ (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 συμβολίζουμε την συνάρτηση του Μέμπιους πάνω από τους φυσικούς αριθμούς.