Προβολή πηγαίου κώδικα για τη σελίδα Μικρό θεώρημα του Φερμά

Στην [[θεωρία αριθμών]], τo '''μικρό θεώρημα του Φερμά''' αναφέρει πως αν ο {{mvar|p}} είναι [[πρώτος αριθμός]], τότε για οποιονδήποτε ακέραιο {{math|''a''}} ο αριθμός {{math|''a''<sup>''p''</sup> − ''a''}} είναι ένα ακέραιο [[Πολλαπλάσιο (μαθηματικά)|πολλαπλάσιο]] του {{mvar|p}}. Με το συμβολισμό της αριθμητικής για τα ισοϋπόλοιπα, αυτό γράφεται ως:<ref>{{cite book |last=Long |first=Calvin T. |title=Elementary introduction to number theory |year=1972 |url=https://archive.org/details/elementaryintrod0000long_m1z0_2ndedi |publisher=D. C. Heath |location=Lexington, Mass |isbn=978-0669627039 |edition=2η}}</ref>{{rp|87–88}}<ref>{{cite book |last=Pettofrezzo |first=Anthony J. |title=Elements of number theory |year=1970 |url=https://archive.org/details/elementsofnumber0000pett |publisher=Prentice-Hall |location=Englewood Cliffs, N.J |isbn=9780132683005 |author2=Byrkit, Donald R.}}</ref>{{rp|110–111}}<ref name="Hardy">{{cite book |last=Hardy |first=Godfrey H. |title=An introduction to the theory of numbers |publisher=Clarendon Press |location=Oxford |isbn=9780198531715 |edition=5η |author2=Wright, Edward Maitland}}</ref>{{rp|62-81}}<ref name="BRP">{{cite book |last1=Βλάμος |first1=Π. |last2=Ραππος |first2=Ε. |last3=Ψαρρακος |first3=Π. |title=Θεωρία αριθμών |year=2000 |publisher=Ελληνική Μαθηματική Εταιρεία |location=Αθήνα |isbn=960-7341-18-X }}</ref>{{rp|104-106}}<ref>{{cite book |author1=Ζάχος, Ε. |author2=Παγουρτζής, Α. |author3=Σούλιου, Θ. |year=2015 |title=Θεμελίωση επιστήμης υπολογιστών |publisher=Κάλλιπος, Ανοικτές Ακαδημαϊκές Εκδόσεις |url=https://hdl.handle.net/11419/5460 }}</ref>{{rp|142-143}}
:<math>a^p \equiv a \pmod p.</math>

Για παράδειγμα, αν {{mvar|a}} = 2 και {{mvar|p}} = 7, τότε 2<sup>7</sup>-2 = 128−2 = 126 = 7 × 18, που είναι πολλαπλάσιο του 7.

Αν το {{mvar|a}} δεν διαιρείται από το {{mvar|p}}, τότε το μικρό θεώρημα του Φερμά είναι ισοδύναμο με το ότι το {{math|''a''<sup>''p'' − 1</sup> − 1}} είναι ένα ακέραιο πολλαπλάσιο του {{mvar|p}}, ή με σύμβολα:

:<math>a^{p-1} \equiv 1 \pmod p.</math>

Για παράδειγμα, αν {{mvar|a}} = 2 και {{mvar|p}} = 7, τότε 2<sup>6</sup>-1 = 64−1 = 63 = 7 × 9, που είναι πολλαπλάσιο του 7. Το θεώρημα (ή παραλλαγές αυτού) χρησιμοποιείται σε [[αλγόριθμος|αλγορίθμους]] για τον [[έλεγχο πρώτων αριθμών]], καθώς και για την επιτάχυνση του υπολογισμού υπολοίπων που χρησιμοποιείται σε αρκετές εφαρμογές της θεωρίας αριθμών, όπως η [[κρυπτογραφία]].

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

* Για τα στοιχεία του <math>\Z_3</math> έχουμε ότι 
:{| class="wikitable"
! <math>1^2</math> !! <math>2^2</math>
|-
| <math>1 = 0 \times 3 + 1</math> || <math>4 = 1 \times 3 + 1</math>
|}
* Για τα στοιχεία του <math>\Z_5</math> έχουμε ότι 
:{| class="wikitable"
! <math>1^4</math> !! <math>2^4</math> !! <math>3^4</math> !! <math>4^4</math>
|-
| <math>1 = 0 \times 5 + 1</math> || <math>16 = 3 \times 5 + 1</math> || <math>81 = 16 \times 5 + 1</math> || <math>256 = 51 \times 5 + 1</math>
|}
* Για τα στοιχεία του <math>\Z_7</math> έχουμε ότι 
:{| class="wikitable"
! <math>1^6</math> !! <math>2^6</math> !! <math>3^6</math> !! <math>4^6</math> !! <math>5^6</math> !! <math>6^6</math>
|-
| <math>1 = 0 \times 7 + 1</math> || <math>64 = 9 \times 7 + 1</math> || <math>729 = 104 \times 7 + 1</math> || <math>4096 = 585 \times 7 + 1</math> || <math>15625 = 2232 \times 7 + 1</math> || <math>46656 = 6665 \times 7 + 1</math>
|}

== Αποδείξεις ==

=== Με διωνυμικό θεώρημα ===

Θα αποδείξουμε ότι <math>a^p \equiv a \pmod{p}</math> με την χρήση της [[μαθηματική επαγωγή|μαθηματικής επαγωγής]] για <math>a = 1, \ldots, p-1</math>.<ref>{{cite web |last=Fiore |first=Marcelo |title=Discrete mathematics: Fermat's Little Theorem |url=https://www.cl.cam.ac.uk/teaching/2223/DiscMath/Lecture04.pdf |publisher=Cambridge University |accessdate=1 Απριλίου 2023}}</ref> 

'''Βασική περίπτωση:''' Για <math>a = 1</math>, προφανώς <math>a^p = 1 \equiv a \pmod{p}</math>.

'''Επαγωγική περίπτωση:''' Ας υποθέσουμε ότι για τυχόν <math>a > 0</math> ισχύει ότι <math>a^p \equiv a \pmod{p}</math>. Τότε από το [[διωνυμικό θεώρημα]], ισχύει ότι
:<math>(a + 1)^p = \sum_{k = 0}^p \binom{a}{q} \cdot a^q</math>.
Από τον ορισμό των διωνυμικών συντελεστών, έχουμε ότι 
:<math>\binom{p}{k} = \frac{p!}{k!(p-k)!} = \frac{p \cdot (p-1) \cdot \ldots \cdot (p-k+1)}{k!}</math>.
Αφού ο <math>p</math> είναι πρώτος αριθμός, κανένας από τους <math>2, \ldots, k</math> δεν διαιρεί τον <math>p</math>, καθώς <math>k < p</math>. Επομένως, 
:<math>p \mid \binom{p}{k}</math>.
Επιστρέφοντας στο διωνυμικό ανάπτυγμα, έχουμε ότι μόνο δύο όροι δεν είναι πολλαπλάσια του <math>p</math>. Συνεπώς,
:<math>(a + 1)^p = \sum_{k = 0}^p \binom{a}{q} \cdot a^q \equiv \binom{a}{p} a^p + \binom{a}{0} a^0 \equiv a^p + 1 \pmod{p}</math>.
Χρησιμοποιώντας την επαγωγική υπόθεση, έχουμε ότι
:<math>(a + 1)^p \equiv a + 1 \pmod{p}.</math>
Επομένως, αυτό ολοκληρώνει την επαγωγή και συνεπώς ισχύει για όλα τα <math>a = 1, \ldots, p -1</math>. Για μεγαλύτερα <math>a</math>, προκύπτει από την πολλαπλασιαστική ιδιότητα των υπολοίπων.

===Με πολλαπλασιαστικό αντίστροφο===

Για κάθε <math>a = 1, \ldots, p-1</math> ισχύει ότι <math>(a, p) = 1</math>, δηλαδή ο <math>a</math> και ο <math>p</math> είναι [[Σχετικά πρώτοι|αριθμοί πρώτοι μεταξύ τους]]. Επομένως προκύπτει ότι υπάρχει μοναδικός αριθμός <math>a^{-1} \in \{1, \ldots, p-1\}</math> ώστε <math>a \cdot a^{-1} \equiv 1 \pmod{p}</math>, ο [[πολλαπλασιαστικός αντίστροφος]] του <math>a</math>. 

Θεωρούμε την συνάρτηση <math>f_a : \{1, \ldots, p-1\} \to \{1, \ldots , p-1\}</math> που ορίζουμε ως εξής
:<math>f_a(x) = (a \cdot x) \mod p</math>.
Από την ιδιότητα του πολλαπλασιαστικού αντιστρόφου ισχύει ότι η <math>f</math> είναι [[ένα προς ένα]]. Επομένως, το γινόμενο
:<math>
f_a(1) \cdot \ldots \cdot f_a(p-1) \equiv a \cdot (2a) \cdot \ldots \cdot ( (p-1) \cdot a) 
  \equiv 1 \cdot 2 \cdot \ldots \cdot (p-1) \pmod{p}</math>.
Συνεπώς, αναδιατάσσοντας τους όρους του αριστερού μέλους (χρησιμοποιώντας την [[αντιμεταθετική ιδιότητα]] του πολλαπλασιασμού), προκύπτει ότι
:{{NumBlk|:|<math>
a^{p-1} \cdot (1 \cdot \ldots \cdot (p-1)) \equiv (1 \cdot \ldots \cdot (p-1)) \pmod{p}.
</math>|{{EquationRef|1}}}}
Αφού οι αριθμοί <math>1, \ldots, p-1</math> είναι σχετικά πρώτοι με τον <math>p</math>, το γινόμενό τους είναι σχετικά πρώτος με τον <math>p</math> και συνεπώς έχει πολλαπλασιαστικό αντίστροφο κάποιον αριθμό <math>(1 \cdot \ldots \cdot (p-1))^{-1}</math>. 

Επομένως, πολλαπλασιάζοντας και τα δύο μέλη της ({{EquationNote|1}}) με <math>(1 \cdot \ldots \cdot (p-1))^{-1}</math>, έχουμε ότι
:<math>
a^{p-1} \cdot (1 \cdot \ldots \cdot (p-1)) \cdot (1 \cdot \ldots \cdot (p-1))^{-1} \equiv (1 \cdot \ldots \cdot (p-1)) \cdot (1 \cdot \ldots \cdot (p-1))^{-1} \pmod{p},
</math>
που συνεπάγεται το ζητούμενο
:<math>a^{p-1} \equiv 1 \pmod{p}.</math>

== Αντίστροφο θεωρήματος ==
Το αντίστροφο του θεωρήματος δεν ισχύει. Δηλαδή, υπάρχουν [[σύνθετος αριθμός|σύνθετοι αριθμοί]] <math>q</math> για τους οποίους έχουμε <math>a^q \equiv a \pmod{q}</math> για κάθε ακέραιο <math>a</math>. Οι αριθμοί αυτοί ονομάζονται [[αριθμός Carmichael|αριθμοί Carmichael]] και ένας τέτοιος είναι το <math>561</math>.{{r|Hardy|p=72}}

Ο σύνθετος αριθμός <math>m</math> λέγεται [[ψευδοπρώτος]] σε σχέση με το <math>a</math>, αν ισχύει ότι <math>a^{m-1} \equiv 1 \pmod{m}</math>. Ένας αριθμός Carmichael <math>m</math> είναι ψευδοπρώτος για κάθε <math>a</math> σχετικά πρώτο με το <math>m</math>.

Ένα αντίστροφο είναι το θεώρημα Lucas{{r|BRP|p=106}} που λέει ότι 
{{Μαθηματικό θεώρημα
| τύπος = Θεώρημα
| όνομα = Θεώρημα Lucas
| διατύπωση = Αν <math>p \mid a^{x} - 1</math> για <math>x = p -1</math> και <math>p \nmid a^x - 1</math> για <math>x < p - 1</math>, τότε ο <math>p</math> είναι πρώτος.
}}

== Εφαρμογές ==

=== Γρήγορος υπολογισμός υπολοίπων ===

Το θεώρημα χρησιμοποιείται για να βρεθεί το υπόλοιπο μίας (μεγάλης) δύναμης με έναν [[πρώτος αριθμός|πρώτο αριθμό]]. Για παράδειγμα, αν ψάχνουμε το υπόλοιπο της διαίρεσης του 3<sup>100.000</sup> με τον πρώτο αριθμό 53, από το θεώρημα έχουμε 3<sup>52</sup>=1. Παρατηρούμε ότι 3<sup>100.000</sup> {{nowrap|≡ 3<sup>52 × 1923 + 4</sup>}} {{nowrap|≡ (3<sup>52</sup>)<sup>1923</sup> × 3<sup>4</sup>}} {{nowrap|≡ 1<sup>1923</sup> × 3<sup>4</sup>}} {{nowrap|≡ 81 ≡ 28 (mod 53)}}. 

Πιο γενικά, για να υπολογίσουμε το υπόλοιπο του <math>a^n</math> με έναν πρώτο αριθμό <math>p</math>, ο υπολογισμός του <math>a^n</math> θα χρειαζόταν πράξεις σε αριθμούς με <math>O(n)</math> ψηφία. Το θεώρημα του Φερμά επιτρέπει να γίνουν αυτές οι πράξεις σε αριθμούς με <math>O(\log n + \log p)</math> ψηφία, που είναι εκθετικά πιο γρήγορο.

Αν θέλουμε να βρούμε το υπόλοιπο μίας (μεγάλης) δύναμης με ''οποιονδήποτε'' αριθμό, τότε θα χρησιμοποιήσουμε το [[θεώρημα του Όιλερ]], το οποίο είναι γενίκευση αυτού εδώ του θεωρήματος.

=== Έλεγχος πρώτων αριθμών ===

Το μικρό θεώρημα του Φερμά χρησιμοποιείται στον [[έλεγχος πρώτων αριθμών του Φερμά|έλεγχο πρώτων αριθμών του Φερμά]], έναν [[πιθανοτικός αλγόριθμος|πιθανοτικό αλγόριθμο]] που ελέγχει αν ένας [[φυσικός αριθμός]] <math>n</math> είναι πρώτος σε <math>O(\log^2 n)</math> χρόνο με μία (πολύ) μικρή πιθανότητα λάθους.<ref>{{cite book |author1=Τσίχλας, Κ. |author2=Γούναρης, Α. |author3=Μανωλόπουλος, Ι. |year=2015 |title=Σχεδίαση και ανάλυση αλγορίθμων |publisher=Κάλλιπος, Ανοικτές Ακαδημαϊκές Εκδόσεις |url=https://hdl.handle.net/11419/4005 }}</ref>{{rp|390-394}}<ref>{{cite book |author1=Παγουρτζής, Α. |author2=Ζάχος, Ε. |year=2015 |title=Υπολογιστική κρυπτογραφία |publisher=Κάλλιπος, Ανοικτές Ακαδημαϊκές Εκδόσεις |url=https://hdl.handle.net/11419/5439 }}</ref>{{rp|56-57}} Ο [[έλεγχος πρώτων αριθμών του Lucas]] και ο [[έλεγχος πρώτων των Miller–Rabin]] βασίζονται σε μικρές παραλλαγές του μικρού θεωρήματος του Φερμά.

==Ιστορία==

Το μικρό θεώρημα του Φερμά είναι η βάση για τη "δοκιμή του Φερμά για το αν ένας αριθμός είναι πρώτος" και ένα από τα θεμελιώδη αποτελέσματα της στοιχειώδους [[Θεωρία των Αριθμών|Θεωρίας Αριθμών]]. Το θεώρημα ονομάστηκε από τον [[Πιέρ ντε Φερμά]], που το διατύπωσε το 1640 και έλαβε το όνομα "μικρό θεώρημα" για να το ξεχωρίσουμε από το [[Τελευταίο θεώρημα του Φερμά|"τελευταίο θεώρημα" του Φερμά]]. Το απέδειξε ο [[Λέοναρντ Όιλερ]] το 1736, ο οποίος και το γενίκευσε με το [[θεώρημα του Όιλερ]]. Το όνομα "μικρό θεώρημα του Φερμά" το έδωσε το 1913 ο [[Κουρτ Χένσελ]].

==Δείτε επίσης==
* [[Τελευταίο θεώρημα του Φερμά]]
* [[Θεώρημα του Όιλερ]]

==Παραπομπές==
<references />

[[Κατηγορία:Μαθηματικά θεωρήματα]]
[[Κατηγορία:Θεωρία αριθμών]]