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

Στην θεωρία αριθμών, το θεώρημα του Όιλερ (γνωστό και ως θεώρημα Φερμά-Όιλερ) δηλώνει ότι για κάθε σχετικά πρώτους ακεραίους αριθμούς  και  (δηλαδή ο μέγιστος κοινός διαιρέτης του  και του  είναι το ), ισχύει ότι
, 
όπου  είναι η συνάρτηση του Όιλερ, όπου  είναι το πλήθος των ακεραίων μικρότερων του  που είναι σχετικά πρώτοι με το . Ισοδύναμα το  διαιρεί το .

Για την περίπτωση που ο  είναι πρώτος αριθμός, δηλαδή όλοι οι μικρότεροι αριθμοί  είναι σχετικά πρώτοι με το , έχουμε ότι  και έτσι
, 
που είναι το μικρό θεώρημα του Φερμά.

Το θεώρημα παίρνει το όνομά του από τον μαθηματικό Λέοναρντ Όιλερ και βρίσκει εφαρμογές σε διάφορους τομείς της κρυπτογραφίας και συγκεκριμένα στο κρυπτοσύστημα RSA. Το θεώρημα του Όιλερ γενικεύεται από την συνάρτηση του Κάρμαϊκλ.

Παραδείγματα 

 Για  οι σχετικά πρώτοι αριθμοί μικρότεροι του  είναι οι  και άρα . Το θεώρημα του Όιλερ λέει ότι .
 Για  οι σχετικά πρώτοι αριθμοί μικρότεροι του  είναι οι  και άρα . Το θεώρημα του Όιλερ λέει ότι .
 Για  οι σχετικά πρώτοι αριθμοί μικρότεροι του  είναι οι  και άρα . Το θεώρημα του Όιλερ λέει ότι .

Απόδειξη 

Έστω  τα στοιχεία του  που είναι σχετικά πρώτα με το . Τότε θεωρούμε τα γινόμενα , για τα οποία ισχύουν τα εξής:
 Για κάθε ένα από αυτά τα γινόμενα έχουμε ότι , καθώς το γινόμενο δύο σχετικά πρώτων με το  είναι σχετικά πρώτος με το , δηλαδή . 
 Κάθε ένα από αυτά τα γινόμενα είναι μοναδικά, δηλαδή αν  τότε . Αυτό προκύπτει από την ύπαρξη πολλαπλασιαστικού αντιστρόφου του , δηλαδή ενός αριθμού  τέτοιου ώστε  (και επομένως ).
 Το γινόμενο  είναι σχετικά πρώτο με το  και άρα έχει και αντίστροφο  τέτοιον ώστε .
Από αυτά προκύπτει ότι τα γινόμενα  είναι μία μετάθεση των στοιχείων . Συνεπώς, χρησιμοποιώντας την αντιμεταθετική ιδιότητα του πολλαπλασιασμού έχουμε ότι

Εφαρμογές

Υπολογισμός υπολοίπων για δυνάμεις 
Το θεώρημα χρησιμοποιείται για να επιταχυνθεί ο υπολογισμός μεγάλων δυνάμεων (modulo n). Για παράδειγμα για να υπολογίσουμε το 7222 (mod 10), επειδή οι αριθμοί 7 και 10 είναι πρώτοι μεταξύ τους και , από το θεώρημα του Όιλερ ισχύει , έτσι έχουμε 7222    .

Αλγόριθμος RSA 
Ο αλγόριθμος RSA περιλαμβάνει την επιλογή δύο πρώτων αριθμών  και , και θέτει την παράμετρο . Έπειτα επιλέγεται ένα  που είναι σχετικά πρώτο με το . Το μήνυμα  κωδικοποιείται ως  και έπειτα αποκωδικοποιείται με τον αντίστροφο  του  στο , ως . Στο τελευταίο βήμα χρησιμοποιούμε ότι , δηλαδή το θεώρημα του Όιλερ. Αντίστοιχα, χρησιμοποιείται στο να επιταχύνουμε τον υπολογισμό του .

Δείτε επίσης 
 Μικρό θεώρημα του Φερμά
 Συνάρτηση του Όιλερ
 Συνάρτηση του Κάρμαϊκλ

Περαιτέρω ανάγνωση

Ελληνικά άρθρα

Ξενόγλωσσα άρθρα

Παραπομπές 

Θεωρία αριθμών