Μικρό θεώρημα του Φερμά
θεώρημα στην θεωρία αριθμών / From Wikipedia, the free encyclopedia
Στην θεωρία αριθμών, τo μικρό θεώρημα του Φερμά αναφέρει πως αν ο p είναι πρώτος αριθμός, τότε για οποιονδήποτε ακέραιο a ο αριθμός ap − a είναι ένα ακέραιο πολλαπλάσιο του p. Με το συμβολισμό της αριθμητικής για τα ισοϋπόλοιπα, αυτό γράφεται ως:[1]:87–88[2]:110–111[3]:62-81[4]:104-106[5]:142-143
Για παράδειγμα, αν a = 2 και p = 7, τότε 27-2 = 128−2 = 126 = 7 × 18, που είναι πολλαπλάσιο του 7.
Αν το a δεν διαιρείται από το p, τότε το μικρό θεώρημα του Φερμά είναι ισοδύναμο με το ότι το ap − 1 − 1 είναι ένα ακέραιο πολλαπλάσιο του p, ή με σύμβολα:
Για παράδειγμα, αν a = 2 και p = 7, τότε 26-1 = 64−1 = 63 = 7 × 9, που είναι πολλαπλάσιο του 7. Το θεώρημα (ή παραλλαγές αυτού) χρησιμοποιείται σε αλγορίθμους για τον έλεγχο πρώτων αριθμών, καθώς και για την επιτάχυνση του υπολογισμού υπολοίπων που χρησιμοποιείται σε αρκετές εφαρμογές της θεωρίας αριθμών, όπως η κρυπτογραφία.