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

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

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

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

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

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

Ιστορία, ορολογία, συμβολισμός[Επεξεργασία | επεξεργασία κώδικα]

Ο Λέοναρτ Όιλερ εισήγαγε τη συνάρτηση το 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 είναι πρώτος.

3η ιδιότητα[Επεξεργασία | επεξεργασία κώδικα]

Αν n = pk, k ≥ 1 τότε

Για παράδειγμα φ(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 ≥ 3. Ακόμη, αν ο n έχει r διακριτούς περιττούς παράγοντες τότε 2r | φ(n).

Μερικές τιμές της συνάρτησης[Επεξεργασία | επεξεργασία κώδικα]

Οι πρώτες 143 τιμές (ακολουθία A000010 στην OEIS) εμφανίζονται στο γράφημα και στον πιο κάτω πίνακα:


Graph of the first 100 values
φ(n) for 1 ≤ n ≤ 143
+ 0 1 2 3 4 5 6 7 8 9 10 11
0 N/A 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" o Γκάους αποδεικνύει ότι ένα κανονικό 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, ... (ακολουθία A003401 στην OEIS).

Πηγές[Επεξεργασία | επεξεργασία κώδικα]

  • 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)).
Στο λήμμα αυτό έχει ενσωματωθεί κείμενο από το λήμμα Euler's totient function της Αγγλικής Βικιπαίδειας, η οποία διανέμεται υπό την GNU FDL και την CC-BY-SA 3.0. (ιστορικό/συντάκτες).