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

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

Ταξινόμηση
Dewey	511
MSC2010	11-XX

Το θεώρημα του Όιλερ ονόμαστηκε έτσι προς τιμή του γερμανόφωνου Ελβετού μαθηματικού Λέοναρντ Όιλερ (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