Θεώρημα του Όιλερ
θεώρημα στην θεωρία αριθμών που γενικεύει το μικρό θεώρημα του Φερμά / From Wikipedia, the free encyclopedia
Στην θεωρία αριθμών, το θεώρημα του Όιλερ (γνωστό και ως θεώρημα Φερμά-Όιλερ) δηλώνει ότι για κάθε σχετικά πρώτους ακεραίους αριθμούς και (δηλαδή ο μέγιστος κοινός διαιρέτης του και του είναι το ), ισχύει ότι[1]:62-81[2]:104-106[3]:142-143[4]:35-36
- ,
όπου είναι η συνάρτηση του Όιλερ, όπου είναι το πλήθος των ακεραίων μικρότερων του που είναι σχετικά πρώτοι με το . Ισοδύναμα το διαιρεί το .
Για την περίπτωση που ο είναι πρώτος αριθμός, δηλαδή όλοι οι μικρότεροι αριθμοί είναι σχετικά πρώτοι με το , έχουμε ότι και έτσι
- ,
που είναι το μικρό θεώρημα του Φερμά.
Το θεώρημα παίρνει το όνομά του από τον μαθηματικό Λέοναρντ Όιλερ και βρίσκει εφαρμογές σε διάφορους τομείς της κρυπτογραφίας και συγκεκριμένα στο κρυπτοσύστημα RSA. Το θεώρημα του Όιλερ γενικεύεται από την συνάρτηση του Κάρμαϊκλ.