Θεώρημα του Όιλερ: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
μ Removing Link GA template (handled by wikidata) |
Χωρίς σύνοψη επεξεργασίας |
||
Γραμμή 9:
Δηλώνει ότι για κάθε [[φυσικός αριθμός|φυσικό αριθμό]] <math>n</math> ισχύει:
:<math>a^{\varphi(n)} \equiv 1\;\mathrm{mod}\,n</math>,
όπου οι α και n σχετικά πρώτοι (i.e. πρώτοι μεταξύ τους).
Δηλώνει δηλαδή ότι το <math>a^{\varphi(n)}</math> είναι [[σχέση ισοδυναμίας|ισοδύναμο]] της μονάδας ως προς [[modulo]] n
ή αλλιώς ότι το n διαιρεί το <math>a^{\varphi(n)}-1</math>.
Με <math>\varphi(n)</math> συμβολίζεται η [[συνάρτηση Όιλερ]] (totient function), που μας δίνει το πλήθος των φυσικών αριθμών
Εξήγηση: στο Ζ<sub>10</sub> έχουμε 1<sup>4</sup>=1, 2<sup>4</sup>=6, 3<sup>4</sup>=1, 4<sup>4</sup>=6, 5<sup>4</sup>=5, 6<sup>4</sup>=6, 7<sup>4</sup>=1, 8<sup>4</sup>=6, 9<sup>4</sup>=1. Ο Όιλερ παρατήρησε ότι το α<sup>4</sup>=1 συμβαίνει για α=1, 3, 7, 9, δηλ. όποτε οι α, 10 είναι πρώτοι μεταξύ τους.
Το θεώρημα του Όιλερ αποτελεί γενίκευση του [[μικρό θεώρημα του Φερμά|μικρού θεωρήματος του Φερμά]].▼
Το θεώρημα μπορεί να χρησιμοποιηθεί για να μειωθούν εύκολα μεγάλες δυνάμεις (modulo n). Για παράδειγμα στο 7<sup>222</sup> (mod 10), επειδή οι αριθμοί 7 και 10 είναι πρώτοι μεταξύ τους και {{nowrap|1=φ(10) = φ(2 x 5) = (2-1)(5-1) = 4}}, από το θεώρημα του Όιλερ ισχύει {{nowrap|7<sup>4</sup> ≡ 1 (mod 10)}}, έτσι έχουμε 7<sup>222</sup> {{nowrap|≡ 7<sup>4 × 55 + 2</sup>}} {{nowrap|≡ (7<sup>4</sup>)<sup>55</sup> × 7<sup>2</sup>}} {{nowrap|≡ 1<sup>55</sup> × 7<sup>2</sup>}} {{nowrap|≡ 49 ≡ 9 (mod 10)}}.
▲Το θεώρημα του Όιλερ αποτελεί γενίκευση του [[μικρό θεώρημα του Φερμά|μικρού θεωρήματος του Φερμά]]
Για <math>n=p</math>, p [[πρώτος αριθμός]], ισχύει <math>\varphi(p)=p-1</math>.
Η παραπάνω σχέση γράφεται τότε ως
:<math>a^{p-1} \equiv 1\;\mathrm{mod}\,p</math>,
που αποτελεί την έκφραση του μικρού θεωρήματος του [[Πιέρ ντε Φερμά|Φερμά]].
Το θεώρημα του Όιλερ μπορεί να γενικευθεί με το [[θεώρημα του Κάρμαϊκλ]].
{{Μαθηματικά-επέκταση}}
| |||