Συνάρτηση Όιλερ: Διαφορά μεταξύ των αναθεωρήσεων

Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Χωρίς σύνοψη επεξεργασίας
Χωρίς σύνοψη επεξεργασίας
Γραμμή 13:
Το 1879 ο Τζ. Συλβέστερ δημιούργησε τον όρο totient, έτσι τη λέμε "η συνάρτηση totient του Όιλερ". Γενίκευση της συνάρτησης είναι η totient του Τζόρνταν. Η "φ συνάρτηση του Όιλερ" να μη συγχέεται με τη "συνάρτηση του Όιλερ", που είναι μία q-σειρά στη Συνδυαστική και τη Μιγαδική Ανάλυση.
 
Οι αριθμοί που είναι μικρότεροι του n και πρώτοι με αυτόν ονομάζονται totatives του n, πχ οι 1, 5 είναι totatives του 6. Υπάρχουν φ(6)=2 τέτοιοι. Οι υπόλοιποι, δηλ. 2, 3 , 4, 6 λέγονταιείναι cototientεκείνοι καιπου έχουν τουλάχιστον έναν κοινό παράγοντα με τον n· υπάρχουν n-φ(n) = 6-2 = 4 τέτοιοι· είναικαι εκείνοιτο πουπλήθος έχουντους τουλάχιστοναυτό ένανλέγεται κοινό παράγοντα με τον ncototient.
 
== Ιδιότητες ==
Γραμμή 62:
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.
 
=== Παρατήρηση ===
Μπορούμε να πάρουμε έναν άλλο τύπο για την <math>\phi(n)</math> , χρησιμοποιώντας την αντιστροφή του Μέμπιους στο: 
:<math>n=\sum_{d\mid n} \phi(d) </math>
Ο τύπος αυτός είναι ο εξής:
:<math>\phi(n)=\sum_{d\mid n}d \cdot \mu(n/d) </math>
 
όπου με <math>\mu</math> συμβολίζουμε την [[συνάρτηση του Μέμπιους]] πάνω από τους φυσικούς αριθμούς.
 
==Άλλοι τύποι για τη συνάρτηση φ==
*<math>a\mid b \implies \varphi(a)\mid\varphi(b)</math>
*<math>\varphi(mn)\varphi(d) = \varphi(m)\varphi(n)d</math>, όπου d = μκδ(m, n).
 
Ειδικές περιπτώσεις: αν m = 2 ο τελευταίος τύπος γίνεται
φ(2n) = 2φ(n) (αν n=άρτιος) ή = φ(n) (αν n=περιττός)
 
αν m = n ο τύπος γίνεται
φ(n<sup>2</sup>) = nφ(n) και γενικότερα φ(n<sup>k</sup>) = n<sup>k-1</sup>φ(n)
 
*<math>\varphi(\operatorname{lcm}(m,n))\cdot\varphi(\operatorname{gcd}(m,n)) = \varphi(m)\cdot\varphi(n)</math>
 
που μοιάζει με τον τύπο
:*<math>\operatorname{lcm}(m,n)\cdot \operatorname{gcd}(m,n) = m \cdot n</math>
:(δες [[Ελάχιστο Κοινό Πολλαπλάσιο]].)
 
* φ(n) = άρτιος για {{math|''n'' ≥ 3}}. Ακόμη, αν ο n έχει r διακριτούς περιττούς παράγοντες τότε {{math|2<sup>''r''</sup> {{!}} ''φ''(''n'')}}
 
==Μερικές τιμές της συνάρτησης==
Γραμμή 114 ⟶ 140 :
Στο διάγραμμα η ευθεία y = n-1 είναι ένα άνω όριο και είναι ακριβώς αυτό στις περιπτώσεις όπου n = πρώτος. Δεν υπάρχει ευθεία που να είναι κάτω όριο.
 
==Εφαρμογές==
==Εφαρμογή στο θεώρημα του Όιλερ και στην κρυπτογραφία RSA==
 
===Εφαρμογή στο θεώρημα του Όιλερ και στην κρυπτογραφία RSA===
Αν a, n πρώτοι μεταξύ τους, τότε
 
Γραμμή 123 ⟶ 151 :
που είναι το [[Μικρό θεώρημα του Φερμά]].
 
===Εφαρμογή στην κρυπτογραφία RSA===
Στην κρυπτογραφία των [[RSA|R.κρυπτογραφία S. A.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<sup>e</sup>)<sup>d</sup> = m<sup>ed</sup> = m<sup>1</sup> = m, το αρχικό μήνυμα.
==Άλλοι τύποι για τη συνάρτηση φ==
*<math>a\mid b \implies \varphi(a)\mid\varphi(b)</math>
*<math>\varphi(mn)\varphi(d) = \varphi(m)\varphi(n)d</math>, όπου d = μκδ(m, n).
 
===Εφαρμογή στην κυκλοτομία===
Ειδικές περιπτώσεις: αν m = 2 ο τελευταίος τύπος γίνεται
Στο τελευταίο κεφάλαιο του έργου του "Disquisitiones" o Γκάους αποδεικνύει ότι ένα κανονικό n-γωνο μπορεί να κατασκευαστεί με κανόνα και διαβήτη αν το φ(n) είναι δύναμη του 2. i) Αν n=2<sup>k</sup> τότε φ(n) = 2<sup>k-1</sup> = δύναμη του 2 και το πολύγωνο κατασκευάζεται: 2, 4, 8, 16, 32, ... ii) Αν n=p<sup>k</sup> όπου p = πρώτος > 2, τότε φ(n) = p<sup>k-1</sup>(p-1), που για να είναι δύναμη του 2 πρέπει (p-1) = δύναμη του 2. Οι αριθμοί αυτοί p λέγονται ''πρώτοι αριθμοί του Φερμά'' και είναι γνωστοί οι εξής: 3, 5, 17, 257, 65537. Δεν ξέρουμε αν υπάρχουν άλλοι. iii) Συνδυασμός των παραπάνω: 2 x 3, 2 x 5, 3 x 5, 2<sup>2</sup>5, 2<sup>3</sup>3, 2 x 3 x 5, 2 x 17, 2<sup>3</sup> x 5, ...
φ(2n) = 2φ(n) (αν n=άρτιος) ή = φ(n) (αν n=περιττός)
 
αν m = n ο τύπος γίνεται
φ(n<sup>2</sup>) = nφ(n) και γενικότερα φ(n<sup>k</sup>) = n<sup>k-1</sup>φ(n)
 
*<math>\varphi(\operatorname{lcm}(m,n))\cdot\varphi(\operatorname{gcd}(m,n)) = \varphi(m)\cdot\varphi(n)</math>
 
που μοιάζει με τον τύπο
:*<math>\operatorname{lcm}(m,n)\cdot \operatorname{gcd}(m,n) = m \cdot n</math>
:(δες [[Ελάχιστο Κοινό Πολλαπλάσιο]].)
 
* φ(n) = άρτιος για {{math|''n'' ≥ 3}}. Ακόμη, αν ο n έχει r διακριτούς περιττούς παράγοντες τότε {{math|2<sup>''r''</sup> {{!}} ''φ''(''n'')}}
 
== Παρατηρήσεις ==
Μπορούμε να πάρουμε έναν άλλο τύπο για την <math>\phi(n)</math> χρησιμοποιώντας την αντιστροφή του Μέμπιους στο: 
:<math>n=\sum_{d\mid n} \phi(d) </math>
Ο τύπος αυτός είναι ο εξής:
:<math>\phi(n)=\sum_{d\mid n}d \cdot \mu(n/d) </math>
 
όπου με <math>\mu</math> συμβολίζουμε την [[συνάρτηση του Μέμπιους]] πάνω από τους φυσικούς αριθμούς.
 
Τελικά τα κατασκευάσιμα κανονικά πολύγωνα είναι 2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 17, 20, 24, 30, 32, 34, 40, ... {{OEIS|A003401}}.
[[Κατηγορία:Θεωρία αριθμών]]