Θεώρημα του Όιλερ

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Πήδηση στην πλοήγηση Πήδηση στην αναζήτηση
Θεώρημα του Όιλερ
Ταξινόμηση
Dewey 511
MSC2010 11-XX
π  σ  ε

Το θεώρημα του Όιλερ ονόμαστηκε έτσι προς τιμή του γερμανόφωνου Ελβετού μαθηματικού Λέοναρντ Όιλερ (Leonhard Euler).

Δηλώνει ότι για κάθε φυσικό αριθμό ισχύει:

,

όπου οι α και n σχετικά πρώτοι (i.e. πρώτοι μεταξύ τους). Δηλώνει δηλαδή ότι το είναι ισοδύναμο της μονάδας ως προς modulo n ή αλλιώς ότι το n διαιρεί το .

Με συμβολίζεται η συνάρτηση Όιλερ (totient function), που μας δίνει το πλήθος των φυσικών αριθμών, μικρότερων ή ίσων του n, που είναι σχετικά πρώτοι με το n.

Εξήγηση: στο Ζ10 έχουμε 14=1, 24=6, 34=1, 44=6, 54=5, 64=6, 74=1, 84=6, 94=1. Ο Όιλερ παρατήρησε ότι το α4=1 συμβαίνει για α=1, 3, 7, 9, δηλ. όποτε οι α, 10 είναι πρώτοι μεταξύ τους.

Το θεώρημα μπορεί να χρησιμοποιηθεί για να μειωθούν εύκολα μεγάλες δυνάμεις (modulo n). Για παράδειγμα στο 7222 (mod 10), επειδή οι αριθμοί 7 και 10 είναι πρώτοι μεταξύ τους και φ(10) = φ(2 x 5) = (2-1)(5-1) = 4, από το θεώρημα του Όιλερ ισχύει 74 ≡ 1 (mod 10), έτσι έχουμε 7222 ≡ 74 × 55 + 2 ≡ (74)55 × 72 ≡ 155 × 72 ≡ 49 ≡ 9 (mod 10).

Εφαρμόζεται στους αλγόριθμους RSA.

Το θεώρημα του Όιλερ αποτελεί γενίκευση του μικρού θεωρήματος του Φερμά: Για , p πρώτος αριθμός, ισχύει . Η παραπάνω σχέση γράφεται τότε ως

,

που αποτελεί την έκφραση του μικρού θεωρήματος του Φερμά.

Το θεώρημα του Όιλερ στη Θεωρία Αριθμών ονομάζεται και Όιλερ-Φερμά ή Euler-totient για να ξεχωρίζει από θεώρημα του Όιλερ στη Γεωμετρία για τα στερεά.

Το θεώρημα του Όιλερ μπορεί να γενικευθεί με το θεώρημα του Κάρμαϊκλ.

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

  • Gauss, Carl Friedrich; Clarke, Arthur A. (translator into English) (1986), Disquisitiones Arithemeticae (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 Arithemeticae & other papers on number theory) (Second edition), New York: Chelsea, ISBN 0-8284-0191-8
  • Hardy, G. H.; Wright, E. M. (1980), An Introduction to the Theory of Numbers (Fifth edition), Oxford: Oxford University Press, ISBN 978-0-19-853171-5
  • Ireland, Kenneth; Rosen, Michael (1990), A Classical Introduction to Modern Number Theory (Second edition), New York: Springer, ISBN 0-387-97329-X
  • Landau, Edmund (1966), Elementary Number Theory, New York: Chelsea
Στο λήμμα αυτό έχει ενσωματωθεί κείμενο από το λήμμα Euler's theorem της Αγγλικής Βικιπαίδειας, η οποία διανέμεται υπό την GNU FDL και την CC-BY-SA 3.0. (ιστορικό/συντάκτες).