Μικρό θεώρημα του Φερμά

Στην θεωρία αριθμών, τo **μικρό θεώρημα του Φερμά** αναφέρει πως αν ο  είναι πρώτος αριθμός, τότε για οποιονδήποτε ακέραιο  ο αριθμός  είναι ένα ακέραιο πολλαπλάσιο του . Με το συμβολισμό της αριθμητικής για τα ισοϋπόλοιπα, αυτό γράφεται ως:
:a^p \equiv a \pmod p.

Για παράδειγμα, αν  = 2 και  = 7, τότε 27-2 = 128−2 = 126 = 7 × 18, που είναι πολλαπλάσιο του 7.

Αν το  δεν διαιρείται από το , τότε το μικρό θεώρημα του Φερμά είναι ισοδύναμο με το ότι το  είναι ένα ακέραιο πολλαπλάσιο του , ή με σύμβολα:

:a^{p-1} \equiv 1 \pmod p.

Για παράδειγμα, αν  = 2 και  = 7, τότε 26-1 = 64−1 = 63 = 7 × 9, που είναι πολλαπλάσιο του 7. Το θεώρημα (ή παραλλαγές αυτού) χρησιμοποιείται σε αλγορίθμους για τον έλεγχο πρώτων αριθμών, καθώς και για την επιτάχυνση του υπολογισμού υπολοίπων που χρησιμοποιείται σε αρκετές εφαρμογές της θεωρίας αριθμών, όπως η κρυπτογραφία.

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

* Για τα στοιχεία του \Z_3 έχουμε ότι 
:
* Για τα στοιχεία του \Z_5 έχουμε ότι 
:
* Για τα στοιχεία του \Z_7 έχουμε ότι 
:

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

## Αντίστροφο θεωρήματος
Το αντίστροφο του θεωρήματος δεν ισχύει. Δηλαδή, υπάρχουν σύνθετοι αριθμοί q για τους οποίους έχουμε a^q \equiv a \pmod{q} για κάθε ακέραιο a. Οι αριθμοί αυτοί ονομάζονται αριθμοί Carmichael και ένας τέτοιος είναι το 561.

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

Ένα αντίστροφο είναι το θεώρημα Lucas που λέει ότι 

## Εφαρμογές

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

Το θεώρημα χρησιμοποιείται για να βρεθεί το υπόλοιπο μίας (μεγάλης) δύναμης με έναν πρώτο αριθμό. Για παράδειγμα, αν ψάχνουμε το υπόλοιπο της διαίρεσης του 3100.000 με τον πρώτο αριθμό 53, από το θεώρημα έχουμε 352=1. Παρατηρούμε ότι 3100.000    . 

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

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

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

Το μικρό θεώρημα του Φερμά χρησιμοποιείται στον έλεγχο πρώτων αριθμών του Φερμά, έναν πιθανοτικό αλγόριθμο που ελέγχει αν ένας φυσικός αριθμός n είναι πρώτος σε O(\log^2 n) χρόνο με μία (πολύ) μικρή πιθανότητα λάθους. Ο έλεγχος πρώτων αριθμών του Lucas και ο έλεγχος πρώτων των Miller–Rabin βασίζονται σε μικρές παραλλαγές του μικρού θεωρήματος του Φερμά.

## Ιστορία

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

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

## Παραπομπές


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