Συνάρτηση Όιλερ: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Χωρίς σύνοψη επεξεργασίας |
Χωρίς σύνοψη επεξεργασίας |
||
Γραμμή 13:
Το 1879 ο Τζ. Συλβέστερ δημιούργησε τον όρο totient, έτσι τη λέμε "η συνάρτηση totient του Όιλερ". Γενίκευση της συνάρτησης είναι η totient του Τζόρνταν. Η "φ συνάρτηση του Όιλερ" να μη συγχέεται με τη "συνάρτηση του Όιλερ", που είναι μία q-σειρά στη Συνδυαστική και τη Μιγαδική Ανάλυση.
Οι αριθμοί που είναι μικρότεροι του n και πρώτοι με αυτόν ονομάζονται totatives του n, πχ οι 1, 5 είναι totatives του 6. Υπάρχουν φ(6)=2 τέτοιοι. Οι υπόλοιποι, δηλ. 2, 3 , 4, 6
== Ιδιότητες ==
Γραμμή 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). Πόσα το
=== Παρατήρηση ===
Μπορούμε
:<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==▼
Αν a, n πρώτοι μεταξύ τους, τότε
Γραμμή 123 ⟶ 151 :
που είναι το [[Μικρό θεώρημα του Φερμά]].
===Εφαρμογή στην κρυπτογραφία RSA===
Στην
Για να στείλω κρυπτογραφημένα έναν αριθμό 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}}.
[[Κατηγορία:Θεωρία αριθμών]]
|