Αριθμός Φερμά

Στα μαθηματικά, αριθμός Φερμά είναι ένας φυσικός αριθμός της μορφής:

όπου n είναι επίσης φυσικός αριθμός. Οι αριθμοί Φερμά πήραν το όνομά τους από τον Πιερ ντε Φερμά, ο οποίος ήταν ο πρώτος που μελέτησε τους αριθμούς αυτούς. Οι αρχικοί αριθμοί Φερμά είναι:
 3, 5, 17, 257, 65.537, 4.294.967.297, 18.446.744.073.709.551.617, … .

Αν ο 2k + 1 είναι πρώτος, και το k > 0, μπορεί να αποδειχθεί ότι ο k πρέπει να είναι δύναμη του δύο. (Αν k = ab όπου 1 ≤ a, b ≤ k και b είναι περιττός, τότε 2k + 1 = (2a)b + 1 ≡ (−1)b + 1 = 0 (mod 2a + 1). Βλέπε κατωτέρω την πλήρη απόδειξη.) Με άλλα λόγια, κάθε πρώτος της μορφής 2k + 1 (εκτός του 2 = 20 + 1) είναι ένας αριθμός Φερμά και αντί του πρώτος ονομάζεται πρώτος Φερμά. Από το 2015, οι μόνοι γνωστοί πρώτοι αριθμοί Φερμά είναι οι F0, F1, F2, F3 και F4 .

Βασικές ιδιότητες 
Οι αριθμοί Φερμά πληρούν τις ακόλουθες αναδρομικές σχέσεις:

για n ≥ 1,

για n ≥ 2.

Κάθε μία από αυτές τις σχέσεις μπορεί να αποδειχθεί με μαθηματική επαγωγή. Από την τελευταία εξίσωση, μπορούμε να συμπεράνουμε το Θεώρημα του Γκόλντμπαχ (που πήρε το όνομά του από τον Κρίστιαν Γκόλντμπαχ), σύμφωνα με το οποίο δεν υπάρχουν δύο αριθμοί Φερμά που μοιράζονται έναν κοινό ακέραιο παράγοντα μεγαλύτερο από τον 1. Για να το δούμε αυτό, ας υποθέσουμε ότι 0 ≤ i < j ενώ οι Fi και Fj έχουν ένα κοινό παράγοντα a > 1. Τότε το a τους διαιρεί και τους δύο:

και Fj, ως εκ τούτου, ο a διαιρεί τη διαφορά τους, που είναι ίση με 2. Δεδομένου ότι το a > 1, πρέπει αναγκαστικά το a = 2 και αυτό είναι μια αντίφαση, διότι κάθε αριθμός Φερμά είναι σαφώς περιττός. Ως επιστέγασμα, παίρνουμε μια άλλη απόδειξη για το άπειρο πλήθος των πρώτων αριθμών, σύμφωνα με την οποία για κάθε Fn, επιλέγουμε έναν πρώτο παράγοντα pn, και τότε η ακολουθία {pn} είναι μια άπειρη ακολουθία διακριτών πρώτων αριθμών.

Περαιτέρω ιδιότητες:

 Ένας πρώτος Φερμά δεν μπορεί να εκφραστεί ως διαφορά δύο p-οστών δυνάμεων, όταν ο p είναι πρώτος και περιττός.
 Με εξαίρεση τους F0 και F1, το τελευταίο ψηφίο ενός αριθμού Φερμά είναι 7.
 Το άθροισμα των αντίστροφων όλων των αριθμών Φερμά  είναι άρρητος αριθμός.

Ψευδοπρώτοι και αριθμοί Φερμά 
Όπως και οι σύνθετοι αριθμοί της μορφής 2p − 1, έτσι και ο κάθε σύνθετος αριθμός Φερμά είναι ένας ισχυρός ψευδοπρώτος με βάση το 2. Αυτό συμβαίνει επειδή όλοι οι ισχυροί ψευδοπρώτοι με βάση το 2 είναι και ψευδοπρώτοι Φερμά, δηλαδή:

για όλους τους αριθμούς Φερμά.

Το 1964, ο Ρότκιεβιτς έδειξε ότι το γινόμενο τουλάχιστον δύο πρώτων αριθμών ή σύνθετων αριθμών Φερμά, θα είναι ένας ψευδοπρώτος Φερμά με βάση το 2.

Εικασία του Σέλφριτζ 
Ο Τζον Λ. Σέλφριτζ έκανε μια ενδιαφέρουσα εικασία. Έστω ότι g(n) είναι το πλήθος των διακριτών πρώτων παραγόντων του  . Τότε, η g(n) δεν είναι μονότονη (μη φθίνουσα) και αν υπάρχει κάποιος ακόμα πρώτος Φερμά, η εικασία θα συνεπάγεται.

Άλλα θεωρήματα σχετικά με τους αριθμούς Φερμά 
Λήμμα: Αν n είναι ένας θετικός ακέραιος αριθμός, τότε

Απόδειξη:

Θεώρημα: Αν ο  είναι περιττός πρώτος, τότε ο  είναι δύναμη του 2.

Απόδειξη:

Αν  είναι ένας θετικός ακέραιος αριθμός αλλά όχι δύναμη του 2, τότε  όπου
,  και οι r και s είναι σχετικά πρώτοι. Άνευ βλάβης της γενικότητας πρέπει ο  να είναι περιττός.

Σύμφωνα με το προηγούμενο λήμμα, για θετικό ακέραιο ,

όπου το σύμβολο  σημαίνει μια «άρτια διαίρεση».

Αντικαθιστώντας ,  και  κάνοντας χρήση του  ως περιττό αριθμό,

και ετσι

Δεδομένου του , προκύπτει ότι ο  δεν είναι πρώτος. Ως εκ τούτου, με αντιδιαστολή ο  πρέπει να είναι δύναμη του 2.

Σχέση με τα κατασκευάσιμα πολύγωνα 
Ένα κανονικό πολύγωνο με n πλευρές μπορεί να κατασκευαστεί με κανόνα και διαβήτη αν και μόνον αν ο n είναι γινόμενο μιας δύναμης του 2 ή διακριτός πρώτος Φερμά. Με άλλα λόγια, αν και μόνο αν ο n είναι της μορφής n = 2kp1p2…ps, όπου ο k είναι ένας μη αρνητικός ακέραιος αριθμός και οι pi είναι διακριτοί πρώτοι Φερμά.

Ένας θετικός ακέραιος n είναι της παραπάνω μορφής αν και μόνον αν η τιμή φ(n) είναι δύναμη του 2.

Εφαρμογές των αριθμών Φερμά

Δημιουργία ψευδοτυχαίων αριθμών 
Οι πρώτοι Φερμά είναι ιδιαίτερα χρήσιμοι στη δημιουργία ψευδοτυχαίων ακολουθιών αριθμών σε πεδία 1 ... Ν, όπου το N είναι μία δύναμη του 2. Η πιο κοινή μέθοδος που χρησιμοποιείται είναι να λάβει οποιαδήποτε αρχική τιμή μεταξύ 1 και P − 1, όπου το P είναι ένας πρώτος Φερμά, και στη συνέχεια πολλαπλασιάζοντας τον με έναν αριθμό A, ο οποίος είναι μεγαλύτερος από την τετραγωνική ρίζα του P και είναι μια πρωτογενής ρίζα του υπολοίπου του P (δηλαδή, δεν είναι υπόλοιπο τετραγώνου). Έτσι, παίρνουμε το αποτέλεσμα του υπολοίπου του P, το οποίο είναι η επόμενη τιμή του αλγορίθμου για τη δημιουργία ψευδοτυχαίων αριθμών.
   (βλ. Γραμμική συμβατική γεννήτρια, RANDU)

Αυτό είναι χρήσιμο στην επιστήμη των υπολογιστών δεδομένου ότι οι περισσότερες δομές δεδομένων έχουν μέλη με 2X δυνατές τιμές. Για παράδειγμα, ένα byte έχει 256 = 28 πιθανές τιμές (0–255). Ως εκ τούτου, για να γεμίσει ένα byte ή bytes με τυχαίες τιμές, μπορεί να χρησιμοποιηθεί μια γεννήτρια τυχαίων αριθμών που παράγει τιμές 1–256, και το byte θα λάβει τις αξίες αυτές − 1. Για το λόγο αυτό, παρουσιάζουν ιδιαίτερο ενδιαφέρον στην κρυπτογράφηση δεδομένων οι πολύ μεγάλοι πρώτοι αριθμοί Φερμά. Αυτή η μέθοδος παράγει μόνο ψευδοτυχαίες τιμές καθώς, μετά από P − 1 επαναλήψεις, η ακολουθία επαναλαμβάνεται. Μια κακή επιλογή πολλαπλασιαστή μπορεί να οδηγήσει στην επανάληψη της ακολουθίας νωρίτερα από τις P − 1 επαναλήψεις.

Άλλα ενδιαφέροντα στοιχεία 
Ένας αριθμός Φερμά δεν μπορεί να είναι τέλειος αριθμός ή μέρος ενός ζεύγους φιλικών αριθμών.

Η σειρά των αντίστροφων από όλους τους πρώτους διαιρέτες των αριθμών Φερμά είναι συγκλίνουσα.

Αν nn + 1 είναι πρώτος, τότε υπάρχει ακέραιος m τέτοιος ώστε n = 22m, και τότε ισχύει η εξίσωση nn + 1 = F(2m+m).

Έστω ότι ο μεγαλύτερος πρώτος παράγοντας του αριθμού Φερμά Fn είναι ο P(Fn). Τότε ισχύει P(Fn) ≥ 2n+2(4n + 9) + 1.

Γενικευμένοι αριθμοί Φερμά 
Οι αριθμοί της μορφής a2n + b2n όπου a, b είναι σχετικά πρώτοι ακέραιοι και a > b > 0, ονομάζονται γενικευμένοι αριθμοί Φερμά. Ένας περιττός πρώτος p είναι ένας γενικευμένος αριθμός Φερμά αν και μόνο αν ο p είναι σύμφωνος στο 1 (mod 4), εδώ θεωρούμε ότι το n > 0, για να μην είναι αντιπαράδειγμα το 3 = 220 + 1.

Κατ' αναλογία με τους απλούς αριθμούς Φερμά, είναι σύνηθες να γράψουμε τους γενικευμένους αριθμούς Φερμά της μορφής a2n + 1 ως Fn(a). Για παράδειγμα, με αυτή τη σημειογραφία ο αριθμός 100000001 θα γράφονταν ως F3(10). Ακολούθως θα πρέπει να περιοριστούμε σε πρώτους της μορφής a2n + 1.

Εάν απαιτήται το n > 0, τότε το τέταρτο πρόβλημα Λαντάου ρωτά εάν υπάρχουν απείρως πολλοί γενικευμένοι πρώτοι Φερμά Fn(a).

Γενικευμένοι πρώτοι Φερμά 
Λόγω της ευκολίας στην απόδειξη του ότι είναι πρώτοι, οι γενικευμένοι πρώτοι Φερμά έχουν γίνει τα τελευταία χρόνια ένα καυτό θέμα έρευνας στον κλάδο της θεωρίας αριθμών. Πολλοί από τους μεγαλύτερους γνωστούς πρώτους σήμερα είναι γενικευμένοι πρώτοι Φερμά.

Οι γενικευμένοι αριθμοί Φερμά μπορεί να είναι πρώτοι μόνο για άρτιο a, διότι αν ο a είναι περιττός τότε κάθε γενικευμένος αριθμός Φερμά θα διαιρείται με το 2. Ο μικρότερος πρώτος αριθμός Fn(a) όπου n > 4 είναι ο F5(30), ή 3032+1. Εκτός αυτού, μπορούμε να ορίσουμε και «ημιγενικευμένους αριθμούς Φερμά» σε μια περιττή βάση, ένας ημιγενικευμένος αριθμός Φερμά με βάση τον περιττό a είναι της μορφής , επίσης θα πρέπει να υπάρχει πεπερασμένο πλήθος ημιγενικευμένων πρώτων Φερμά για κάθε περιττή βάση.

Στην παρακάτω λίστα, οι γενικευμένοι αριθμοί Φερμά Fn(a), για άρτιο a είναι , για περιττό a, είναι . Εάν ο a είναι μια τέλεια δύναμη με περιττό εκθέτη , τότε όλοι οι γενικευμένοι αριθμοί Φερμά μπορεί να είναι πεπερασμένοι αλγεβρικά και έτσι δεν μπορεί να είναι πρώτοι. Για τον μικρότερο αριθμό n τέτοιο ώστε ο Fn(a) να είναι πρώτος, βλ. .

Για περισσότερες πληροφορίες σχετικά με άρτιες βάσεις έως το 1000, βλέπε jeppesn.dk, έως το 1030, βλέπε noprimeleftbehind.net.

Για τον μικρότερο πρώτο της μορφής Fn(a, b), όπου ο a + b είναι περττός, βλέπε την .

Για τη μικρότερη άρτια βάση του a τέτοιον ώστε ο Fn(a) να είναι πρώτος, βλέπε την .

Η μικρότερη βάση b τέτοια ώστε ο b2n + 1 να είναι πρώτος, δίνει:
2, 2, 2, 2, 2, 30, 102, 120, 278, 46, 824, 150, 1534, 30406, 67234, 70906, 48594, 62722, 24518, 75898, ... 

Ο μικρότερος k τέτοιος ώστε ο (2n)k + 1 να είναι πρώτος, δίνει:
1, 1, 1, 0, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 0, 4, 1, ... (ο επόμενος όρος δεν είναι γνωστός), βλέπε την , επίσης την  και την .

Μια πιο εμπεριστατωμένη θεωρία μπορεί να χρησιμοποιηθεί για να προβλεφθεί ο αριθμός των βάσεων για τις οποίες ο Fn(a) θα είναι πρώτος για πεπερασμένο αριθμό n. Ο αριθμός των γενικευμένων πρώτων αριθμών Φερμά χονδρικά αναμένεται να μειωθεί στο ήμισυ όταν ο n αυξηθεί κατά 1.

Οι μεγαλύτεροι γνωστοί γενικευμένοι πρώτοι Φερμά 
Η παρακάτω λίστα περιέχει τους 10 μεγαλύτερους γνωστούς γενικευμένους πρώτους αριθμούς Φερμά, οι οποίοι είναι όλοι μεγάλοι πρώτοι. Ανακαλύφθηκαν όλοι από τους συμμετέχοντες στην έρευνα του PrimeGrid και ισχύουν ως σήμερα.

Παραπομπές

Βιβλιογραφία 

 - This book contains an extensive list of references.

Εξωτερικοί σύνδεσμοι 
 
 
 
 
 

Ακολουθίες
Άλυτα προβλήματα στα μαθηματικά
Ευκλείδεια επιπεδομετρία
Θεωρία αριθμών
Μαθηματικές αποδείξεις