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

Ιστορία, ορολογία, συμβολισμός

Ο Λέοναρτ Όιλερ εισήγαγε τη συνάρτηση το 1763, αλλά χωρίς να τη συμβολίσει. Το 1784 επέλεξε το ελληνικό γράμμα π για το συμβολισμό της: πD "το πλήθος των αριθμών, μικρότερων του D, που δεν έχουν κοινό διαιρέτη με το Ν"· o ορισμός είναι ίδιος με αυτόν που χρησιμοποιούμε, εκτός για D=1. To 1801 o Γκάους χρησιμοποίησε τον συμβολισμό φD στη διατριβή του "Disquisitiones Arithmeticae". Ονομάστηκε "η συνάρτηση φ του Όιλερ" ή "η συνάρτηση φ" και γράφουμε φ(D). 
Το 1879 ο Τζ. Συλβέστερ δημιούργησε τον όρο totient, έτσι τη λέμε "η συνάρτηση totient του Όιλερ". Γενίκευση της συνάρτησης είναι η totient του Τζόρνταν. Η "φ συνάρτηση του Όιλερ" να μη συγχέεται με τη "συνάρτηση του Όιλερ", που είναι μία q-σειρά στη Συνδυαστική και τη Μιγαδική Ανάλυση. 
Οι αριθμοί που είναι μικρότεροι του n και πρώτοι με αυτόν ονομάζονται totatives του n, πχ οι 1, 5 είναι totatives του 6. Υπάρχουν φ(6)=2 τέτοιοι. Οι υπόλοιποι, δηλ. 2, 3, 4, 6 είναι εκείνοι που έχουν τουλάχιστον έναν κοινό παράγοντα με τον n· υπάρχουν n-φ(n) = 6-2 = 4 τέτοιοι και το πλήθος τους αυτό λέγεται cototient.

Ιδιότητες

Στο 0 δεν ορίζεται. Είναι .

1η ιδιότητα

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

2η ιδιότητα

Είναι εύκολο να παρατηρήσει κάποιος ότι αν ο n είναι πρώτος αριθμός τότε όλοι οι φυσικοί που είναι μικρότεροι από αυτόν είναι πρώτοι ως προς τον n, οπότε .
Για παράδειγμα:  επειδή το 101 είναι πρώτος.

Εφαρμογή στην κρυπτογραφία RSA

Στην κρυπτογραφία RSA ξεκινάμε με δύο μεγάλους πρώτους p, q. Για απλοποίηση ας είναι p=5, q=11. Παίρνουμε το γινόμενό τους n = pq = 55 και το φ(n) = φ(55) = 40. Διαλέγουμε έναν αριθμό e < φ(n) έτσι ώστε e, φ(n) πρώτοι μεταξύ τους, ας είναι το e = 7. Υπολογίζουμε τον αντίστροφό του (mod φ(n)) με τη βοήθεια του αλγορίθμου του Ευκλείδη, που είναι το d = 23. Πράγματι 7 x 23 = 161 = 1 (mod 40). To δημόσιο κλειδί είναι το ζεύγος (e, n) = (7, 55) και το ιδιωτικό κλειδί είναι το (d, n) = (23, 55). Αν ξέρει κάποιος άλλος το (e, n) δεν μπορεί να βρει το d αν δεν ξέρει το φ(n), που υπολογίζεται από την παραγοντοποίηση του n. Η δυσκολία της παραγοντοποίησης μεγάλων αριθμών είναι η εγγύηση ότι δεν θα βρει κάποιος άλλος το ιδιωτικό κλειδί.
Για να στείλω κρυπτογραφημένα έναν αριθμό m, τον υψώνω στην e. Ο παραλήπτης τον υψώνει στη δύναμη d και λαμβάνει το (mᵉ)ᵈ = mᵉᵈ = m¹ = m, το αρχικό μήνυμα.

Εφαρμογή στην κυκλοτομία

Στο τελευταίο κεφάλαιο του έργου του "Disquisitiones" o Γκάους αποδεικνύει ότι ένα κανονικό n-γωνο μπορεί να κατασκευαστεί με κανόνα και διαβήτη αν το φ(n) είναι δύναμη του 2. 
Αναλύουμε τον n σε γινόμενο πρώτων παραγόντων. Τότε:
i) Αν n=2ᵏ τότε φ(n) = 2ᵏ⁻¹ = δύναμη του 2 και το πολύγωνο κατασκευάζεται: 2, 4, 8, 16, 32, ... 
ii) Αν n=pᵏ όπου p = πρώτος > 2, τότε φ(n) = pᵏ⁻¹(p-1), που για να είναι δύναμη του 2 πρέπει k=1 και (p-1) = δύναμη του 2. Οι αριθμοί αυτοί p λέγονται πρώτοι αριθμοί του Φερμά και είναι γνωστοί οι εξής: 3, 5, 17, 257, 65537. Δεν ξέρουμε αν υπάρχουν άλλοι. 
iii) Συνδυασμός των παραπάνω: 2 x 3, 2 x 5, 2²3, 3 x 5, 2²5, 2³3, 2 x 3 x 5, 2 x 17, 2³5, ... 
Τελικά τα κατασκευάσιμα κανονικά πολύγωνα είναι 2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 17, 20, 24, 30, 32, 34, 40, ... (ακολουθία A003401 στην OEIS).