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

Πρότυπο:Επιστημονικό πεδίο

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

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

a^{\varphi (n)}\equiv 1\;\mathrm {mod} \,n

,

όπου οι α και n σχετικά πρώτοι (i.e. πρώτοι μεταξύ τους). Δηλώνει δηλαδή ότι το $a^{\varphi (n)}$ είναι ισοδύναμο της μονάδας ως προς modulo n ή αλλιώς ότι το n διαιρεί το $a^{\varphi (n)}-1$ .

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

Εξήγηση: στο Ζ₁₀ έχουμε 1⁴=1, 2⁴=6, 3⁴=1, 4⁴=6, 5⁴=5, 6⁴=6, 7⁴=1, 8⁴=6, 9⁴=1. Ο Όιλερ παρατήρησε ότι το α⁴=1 συμβαίνει για α=1, 3, 7, 9, δηλ. όποτε οι α, 10 είναι πρώτοι μεταξύ τους.

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

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

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

a^{p-1}\equiv 1\;\mathrm {mod} \,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

Αυτό το λήμμα μαθηματικό χρειάζεται επέκταση. Μπορείτε να βοηθήσετε την Βικιπαίδεια επεκτείνοντάς το.

This article "Θεώρημα του Όιλερ" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Θεώρημα του Όιλερ. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.