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

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

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

Για παράδειγμα ας θεωρήσουμε τον αριθμό 9. Το  είναι ίσο με 6, αφού από τους φυσικούς αριθμούς από το 1 μέχρι το 9 ακριβώς έξι, οι 1, 2, 4, 5, 7 και 8, είναι πρώτοι ως προς το 9.

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

Ιστορία, ορολογία, συμβολισμός
Ο Λέοναρτ Όιλερ εισήγαγε τη συνάρτηση το 1763, αλλά χωρίς να τη συμβολίσει. Το 1784 επέλεξε το ελληνικό γράμμα π για το συμβολισμό της: πD "το πλήθος των αριθμών, μικρότερων του D, που δεν έχουν κοινό διαιρέτη με το Ν"· ο ορισμός είναι ίδιος με αυτόν που χρησιμοποιούμε, εκτός για D=1. To 1801 ο Γκάους χρησιμοποίησε τον συμβολισμό φ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 είναι πρώτος.

3η ιδιότητα
Αν n = pk,  τότε 

Για παράδειγμα φ(81) = φ(34) = 34-1(3-1) = 332 = 54 ή φ(34) = 34 (1 - 1/3) = 81 (3-1)/3 = 54.

Ο τύπος του Όιλερ
Με χρήση των παραπάνω και του Κινεζικού Θεωρήματος Υπολοίπων η τιμή της  μπορεί να υπολογιστεί με χρήση του Θεμελιώδους Θεωρήματος της Αριθμητικής: 

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

Για παράδειγμα φ(72) = φ(3223) = (3-1)32-1 (2-1)23-1 = 2 x 31 x 1 x 22= 24

Ο τελευταίος τύπος μπορεί να γραφτεί και ως εξής: 

όπου το γινόμενο διατρέχει όλα τα pr.

Για παράδειγμα

4η ιδιότητα
Πιο πάνω υπολογίσαμε το φ(9). Οι διαιρέτες του 9 είναι οι 1, 3, 9 με φ(1)=1, φ(3)=2, φ(9)=6. Ο Γκάους παρατήρησε ότι φ(1)+φ(3)+φ(9) = 1+2+6 = 9 και γενικότερα

όπου d είναι όλοι οι (θετικοί) διαιρέτες του n.

Για παράδειγμα τα κλάσματα 1/9, 2/9, 3/9, 4/9, 5/9, 6/9, 7/9, 8/9, 9/9 αν απλοποιηθούν δίνουν 1/9, 2/9, 1/3, 4/9, 5/9, 2/3, 7/9, 8/9, 1/1.

Οι παρονομαστές είναι όλοι οι διαιρέτες του 9: 9,3, 1. Πόσα έχουν παρονομαστή το 9; όσα ο αριθμητής τους δεν είχε κοινό διαιρέτη με το 9, δηλ. φ(9). Πόσα έχουν παρονομαστή το 3; φ(3). Πόσα το 1; φ(1). Και αυτά είναι όλα τα κλάσματα. Συνολικά είναι 9, δηλ. φ(9)+φ(3)+φ(1) = 9.

Παρατήρηση 
Μπορούμε να πάρουμε έναν άλλο τύπο για την , χρησιμοποιώντας την αντιστροφή του Μέμπιους στο: 

Ο τύπος αυτός είναι ο εξής:

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

Άλλοι τύποι για τη συνάρτηση φ
.
, όπου d = μκδ(m, n)

Ειδικές περιπτώσεις: αν m = 2 ο τελευταίος τύπος γίνεται
 
φ(2n) = 2φ(n), αν n=άρτιος ή 
= φ(n), αν n=περιττός

αν m = n ο τύπος γίνεται φ(n2) = nφ(n) και γενικότερα φ(nk) = nk-1φ(n).

φ(εκπ(m, n)) φ(μκδ(m, n)) = φ(m) φ(n).

που μοιάζει με τον τύπο εκπ(m, n) μκδ(m, n) = m n (δες Ελάχιστο Κοινό Πολλαπλάσιο).

 φ(n) = άρτιος για . Ακόμη, αν ο n έχει r διακριτούς περιττούς παράγοντες τότε .

Μερικές τιμές της συνάρτησης
Οι πρώτες 143 τιμές  εμφανίζονται στο γράφημα και στον πιο κάτω πίνακα:

{| class="wikitable" style="text-align: center"
|+ for 
! +
! 0 || 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11
|- 
! 0 
|  || 1 || 1 || 2 || 2 || 4 || 2 || 6 || 4 || 6 || 4 || 10
|-
! 12
| 4 || 12 || 6 || 8 || 8 || 16 || 6 || 18 || 8 || 12 || 10 || 22
|- 
! 24
| 8 || 20 || 12 || 18 || 12 || 28 || 8 || 30 || 16 || 20 || 16 || 24
|-
! 36
| 12 || 36 || 18 || 24 || 16 || 40 || 12 || 42 || 20 || 24 || 22 || 46
|-
! 48
| 16 || 42 || 20 || 32 || 24 || 52 || 18 || 40 || 24 || 36 || 28 || 58
|-
! 60
| 16 || 60 || 30 || 36 || 32 || 48 || 20 || 66 || 32 || 44 || 24 || 70
|-
! 72
| 24 || 72 || 36 || 40 || 36 || 60 || 24 || 78 || 32 || 54 || 40 || 82
|-
! 84
| 24 || 64 || 42 || 56 || 40 || 88 || 24 || 72 || 44 || 60 || 46 || 72
|-
! 96
| 32 || 96 || 42 || 60 || 40 || 100 || 32 || 102 || 48 || 48 || 52 || 106
|-
! 108
| 36 || 108 || 40 || 72 || 48 || 112 || 36 || 88 || 56 || 72 || 58 || 96
|-
! 120
| 32 || 110 || 60 || 80 || 60 || 100 || 36 || 126 || 64 || 84 || 48 || 130
|-
! 132
| 40 || 108 || 66 || 72 || 64 || 136 || 44 || 138 || 48 || 92 || 70 || 120
|}

Στο διάγραμμα η ευθεία y = n-1 είναι ένα άνω όριο και είναι ακριβώς αυτό στις περιπτώσεις όπου n = πρώτος. Δεν υπάρχει ευθεία που να είναι κάτω όριο.

Εφαρμογές

Εφαρμογή στο θεώρημα του Όιλερ
Αν a, n  πρώτοι μεταξύ τους, τότε 

Το Θεώρημα του Όιλερ αυτό έχει ειδική περίπτωση το να είναι ο n πρώτος, έστω p. Τότε 

που είναι το Μικρό θεώρημα του Φερμά.

Εφαρμογή στην κρυπτογραφία 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 και λαμβάνει το (me)d = med = m1 = m, το αρχικό μήνυμα.

Εφαρμογή στην κυκλοτομία
Στο τελευταίο κεφάλαιο του έργου του "Disquisitiones" ο Γκάους αποδεικνύει ότι ένα κανονικό n-γωνο μπορεί να κατασκευαστεί με κανόνα και διαβήτη αν το φ(n) είναι δύναμη του 2. 

Αναλύουμε τον n σε γινόμενο πρώτων παραγόντων. Τότε:

i) Αν n=2k τότε φ(n) = 2k-1 = δύναμη του 2 και το πολύγωνο κατασκευάζεται: 2, 4, 8, 16, 32, ... 

ii) Αν n=pk όπου p = πρώτος > 2, τότε φ(n) = pk-1(p-1), που για να είναι δύναμη του 2 πρέπει k=1 και (p-1) = δύναμη του 2. Οι αριθμοί αυτοί p λέγονται πρώτοι αριθμοί του Φερμά και είναι γνωστοί οι εξής: 3, 5, 17, 257, 65537. Δεν ξέρουμε αν υπάρχουν άλλοι. 

iii) Συνδυασμός των παραπάνω: 2 x 3, 2 x 5, 223, 3 x 5, 225, 233, 2 x 3 x 5, 2 x 17, 235, ... 

Τελικά τα κατασκευάσιμα κανονικά πολύγωνα είναι 2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 17, 20, 24, 30, 32, 34, 40, ... .

Παραπομπές

Πηγές 

 Βλάμος Π., Ράππος Ε. «Η συνάρτηση φ του Euler », σελ.96-103, από Ελληνική Ψηφιακή Μαθηματική Βιβλιοθήκη . Αρχειοθετήθηκε 16/01/2019. Ανακτήθηκε 16/01/2019.

Βιβλιογραφία
 Abramowitz, M.; Stegun, I. A. (1964), Handbook of Mathematical Functions, New York: Dover Publications, ISBN 0-486-61272-4. See paragraph 24.3.2.
 Bach, Eric; Shallit, Jeffrey (1996), Algorithmic Number Theory (Vol I: Efficient Algorithms), MIT Press Series in the Foundations of Computing, Cambridge, MA: The MIT Press, ISBN 0-262-02405-5, Zbl 0873.11070
 Ford, Kevin (1999), "The number of solutions of φ(x) = m", Annals of Mathematics, 150 (1): 283–311, doi:10.2307/121103, ISSN 0003-486X, JSTOR 121103, MR 1715326, Zbl 0978.11053.
 Gauss, Carl Friedrich; Clarke, Arthur A. (translator into English) (1986), Disquisitiones Arithmeticae (Second, corrected edition), New York: Springer, ISBN 0-387-96254-9
 Gauss, Carl Friedrich; Maser, H. (translator into German) (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithmeticae & other papers on number theory) (Second edition), New York: Chelsea, ISBN 0-8284-0191-8
 Graham, Ronald; Knuth, Donald; Patashnik, Oren (1994), Concrete Mathematics: a foundation for computer science (2nd ed.), Reading, MA: Addison-Wesley, ISBN 0-201-55802-5, Zbl 0836.00001
 Guy, Richard K. (2004), Unsolved Problems in Number Theory, Problem Books in Mathematics (3rd ed.), New York, NY: Springer-Verlag, ISBN 0-387-20860-7, Zbl 1058.11001
 Hardy, G. H.; Wright, E. M. (1979), An Introduction to the Theory of Numbers (Fifth ed.), Oxford: Oxford University Press, ISBN 978-0-19-853171-5
 Long, Calvin T. (1972), Elementary Introduction to Number Theory (2nd ed.), Lexington: D. C. Heath and Company, LCCN 77-171950
 Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Elements of Number Theory, Englewood Cliffs: Prentice Hall, LCCN 77-81766
 Ribenboim, Paulo (1996), The New Book of Prime Number Records (3rd ed.), New York: Springer, ISBN 0-387-94457-5, Zbl 0856.11001
 Sandifer, Charles (2007), The early mathematics of Leonhard Euler, MAA, ISBN 0-88385-559-3
 Sándor, József; Mitrinović, Dragoslav S.; Crstici, Borislav, eds. (2006), Handbook of number theory I, Dordrecht: Springer-Verlag, pp. 9–36, ISBN 1-4020-4215-9, Zbl 1151.11300
 Sándor, Jozsef; Crstici, Borislav (2004). Handbook of number theory II. Dordrecht: Kluwer Academic. pp. 179–327. ISBN 1-4020-2546-7. Zbl 1079.11001.
 Schramm, Wolfgang (2008), "The Fourier transform of functions of the greatest common divisor", Electronic Journal of Combinatorial Number Theory, A50 (8(1)).

Θεωρία αριθμών