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

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

$a^{\phi (n)}\equiv 1{\pmod {n}}$,

όπου $\phi$ είναι η συνάρτηση του Όιλερ, όπου $\phi (n)$ είναι το πλήθος των ακεραίων μικρότερων του $n$ που είναι σχετικά πρώτοι με το $n$. Ισοδύναμα το $n$ διαιρεί το $a^{\phi (n)}-1$.

Για την περίπτωση που ο $n$ είναι πρώτος αριθμός, δηλαδή όλοι οι μικρότεροι αριθμοί $1,2,3,\ldots ,n-1$ είναι σχετικά πρώτοι με το $n$, έχουμε ότι $\phi (n)=n-1$ και έτσι

$a^{n-1}\equiv 1{\pmod {n}}$,

που είναι το μικρό θεώρημα του Φερμά.

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

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

• Για $n=5$ οι σχετικά πρώτοι αριθμοί μικρότεροι του $n$ είναι οι $a=1,2,3,4$ και άρα $\phi (n)=4$. Το θεώρημα του Όιλερ λέει ότι $1^{4}\equiv 2^{4}\equiv 3^{4}\equiv 4^{4}\equiv 1{\pmod {5}}$.
• Για $n=6$ οι σχετικά πρώτοι αριθμοί μικρότεροι του $n$ είναι οι $a=1,5$ και άρα $\phi (n)=2$. Το θεώρημα του Όιλερ λέει ότι $1^{5}\equiv 5^{2}\equiv 1{\pmod {6}}$.
• Για $n=10$ οι σχετικά πρώτοι αριθμοί μικρότεροι του $n$ είναι οι $a=1,3,7,9$ και άρα $\phi (n)=4$. Το θεώρημα του Όιλερ λέει ότι $1^{4}\equiv 3^{4}\equiv 7^{4}\equiv 9^{4}\equiv 1{\pmod {10}}$.

Απόδειξη

Έστω $x_{1},\ldots ,x_{\phi (n)}$ τα στοιχεία του $\mathbb {Z} _{n}$ που είναι σχετικά πρώτα με το $n$. Τότε θεωρούμε τα γινόμενα $a\cdot x_{1},\ldots ,a\cdot x_{\phi (n)}$, για τα οποία ισχύουν τα εξής:

• Για κάθε ένα από αυτά τα γινόμενα έχουμε ότι $a\cdot x_{i}=x_{j}$, καθώς το γινόμενο δύο σχετικά πρώτων με το $n$ είναι σχετικά πρώτος με το $n$, δηλαδή $\mathrm {gcd} (a\cdot x_{i},n)=1$.
• Κάθε ένα από αυτά τα γινόμενα είναι μοναδικά, δηλαδή αν $a\cdot x_{i}=a\cdot x_{j}$ τότε $x_{i}=x_{j}$. Αυτό προκύπτει από την ύπαρξη πολλαπλασιαστικού αντιστρόφου του $a$, δηλαδή ενός αριθμού $a^{-1}$ τέτοιου ώστε $a\cdot a^{-1}\equiv 1{\pmod {n}}$ (και επομένως $ax_{i}=ax_{j}\Rightarrow a^{-1}ax_{i}\equiv a^{-1}ax_{j}\Rightarrow x_{i}\equiv x_{j}{\pmod {n}}$).
• Το γινόμενο $p=x_{1}\cdot x_{2}\cdot \ldots \cdot x_{\phi (n)}$ είναι σχετικά πρώτο με το $n$ και άρα έχει και αντίστροφο $p^{-1}$ τέτοιον ώστε $p\cdot p^{-1}\equiv 1{\pmod {n}}$.

Από αυτά προκύπτει ότι τα γινόμενα $a\cdot x_{1},\ldots ,a\cdot x_{\phi (n)}$ είναι μία μετάθεση των στοιχείων $x_{1},\ldots ,x_{\phi (n)}$. Συνεπώς, χρησιμοποιώντας την αντιμεταθετική ιδιότητα του πολλαπλασιασμού έχουμε ότι

${\begin{aligned}(ax_{1})\cdot (ax_{2})\cdot \ldots \cdot (ax_{n})&\equiv x_{1}\cdot \ldots x_{n}{\pmod {n}}\Rightarrow \\(a\cdot a\cdot \ldots \cdot a)\cdot x_{1}\cdot x_{2}\ldots \cdot x_{n}&\equiv x_{1}\cdot \ldots x_{n}{\pmod {n}}\Rightarrow \\(a\cdot a\cdot \ldots \cdot a)\cdot p&\equiv p{\pmod {n}}\Rightarrow \\a^{\phi (n)}&\equiv 1{\pmod {n}}.\end{aligned}}$

Εφαρμογές

Υπολογισμός υπολοίπων για δυνάμεις

Το θεώρημα χρησιμοποιείται για να επιταχυνθεί ο υπολογισμός μεγάλων δυνάμεων (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

Ο αλγόριθμος RSA περιλαμβάνει την επιλογή δύο πρώτων αριθμών $p$ και $q$, και θέτει την παράμετρο $n=p\cdot q$. Έπειτα επιλέγεται ένα $e$ που είναι σχετικά πρώτο με το $n$. Το μήνυμα $m$ κωδικοποιείται ως $m^{e}\,\mathrm {mod} \,n$ και έπειτα αποκωδικοποιείται με τον αντίστροφο $d$ του $m$ στο $\mathbb {Z} _{\phi (n)}$, ως $(m^{e})^{d}\equiv m^{ed}\equiv m{\pmod {n}}$. Στο τελευταίο βήμα χρησιμοποιούμε ότι $m^{\phi (n)}\equiv 1{\pmod {n}}$, δηλαδή το θεώρημα του Όιλερ. Αντίστοιχα, χρησιμοποιείται στο να επιταχύνουμε τον υπολογισμό του $m^{e}\,\mathrm {mod} \,n$.

Δείτε επίσης

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

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

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

• Π.Μαρουσάκης (1979). «Θεώρημα του Euler και Θεώρημα του Fermat». Ευκλείδης Β΄ (2): 51-53. http://www.hms.gr/apothema/?s=sa&i=3748. 

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

• Heinrich, Katherine; Horak, Peter (Μαρτίου 1994). «Euler's Theorem». The American Mathematical Monthly 101 (3): 260–261. doi:10.1080/00029890.1994.11996939. https://archive.org/details/sim_american-mathematical-monthly_1994-03_101_3/page/260. 
• Duncan, D. G. (Απριλίου 1955). «A Generalization of the Euler-Fermat Theorem». The American Mathematical Monthly 62 (4): 241. doi:10.2307/2306694. https://archive.org/details/sim_american-mathematical-monthly_1955-04_62_4/page/241. 
• Koshy, Thomas (Ιουλίου 1998). «82.6 A generalisation of Euler’s theorem». The Mathematical Gazette 82 (493): 80–80. doi:10.2307/3620158.