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

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

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

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

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

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

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

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

a^{p-1} \equiv 1\;\mathrm{mod}\,p,

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