Αριθμός Φερμά: θετικός ακέραιος της μορφής (2^(2^n))+1

${\displaystyle F_{n}=2^{(2^{n})}+1}$

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

3, 5, 17, 257, 65.537, 4.294.967.297, 18.446.744.073.709.551.617, … (ακολουθία A000215 στην OEIS).

Αν ο 2^k + 1 είναι πρώτος, και το k > 0, μπορεί να αποδειχθεί ότι ο k πρέπει να είναι δύναμη του δύο. (Αν k = ab όπου 1 ≤ a, b ≤ k και b είναι περιττός, τότε 2^k + 1 = (2^a)^b + 1 ≡ (−1)^b + 1 = 0 (mod 2^a + 1). Βλέπε κατωτέρω την πλήρη απόδειξη.) Με άλλα λόγια, κάθε πρώτος της μορφής 2^k + 1 (εκτός του 2 = 2⁰ + 1) είναι ένας αριθμός Φερμά και αντί του πρώτος ονομάζεται πρώτος Φερμά. Από το 2015, οι μόνοι γνωστοί πρώτοι αριθμοί Φερμά είναι οι F₀, F₁, F₂, F₃ και F₄ (ακολουθία A019434 στην OEIS).

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

${\displaystyle F_{n}=(F_{n-1}-1)^{2}+1\!}$ 

για n ≥ 1,

${\displaystyle F_{n}=F_{n-1}+2^{2^{n-1}}F_{0}\cdots F_{n-2}\!}$ 

${\displaystyle F_{n}=F_{n-1}^{2}-2(F_{n-2}-1)^{2}\!}$ 

${\displaystyle F_{n}=F_{0}\cdots F_{n-1}+2\!}$ 

για n ≥ 2.

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

${\displaystyle F_{0}\cdots F_{j-1}}$ 

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

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

• Ένας πρώτος Φερμά δεν μπορεί να εκφραστεί ως διαφορά δύο p-οστών δυνάμεων, όταν ο p είναι πρώτος και περιττός.
• Με εξαίρεση τους F₀ και F₁, το τελευταίο ψηφίο ενός αριθμού Φερμά είναι 7.
• Το άθροισμα των αντίστροφων όλων των αριθμών Φερμά (ακολουθία A051158 στην OEIS) είναι άρρητος αριθμός.

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

${\displaystyle 2^{F_{n}-1}\equiv 1{\pmod {F_{n}}}\,\!}$ 

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

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

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

Λήμμα: Αν n είναι ένας θετικός ακέραιος αριθμός, τότε

${\displaystyle a^{n}-b^{n}=(a-b)\sum _{k=0}^{n-1}a^{k}b^{n-1-k}.}$ 

Απόδειξη:

${\displaystyle (a-b)\sum _{k=0}^{n-1}a^{k}b^{n-1-k}}$ 

${\displaystyle =\sum _{k=0}^{n-1}a^{k+1}b^{n-1-k}-\sum _{k=0}^{n-1}a^{k}b^{n-k}}$ 

${\displaystyle =a^{n}+\sum _{k=1}^{n-1}a^{k}b^{n-k}-\sum _{k=1}^{n-1}a^{k}b^{n-k}-b^{n}}$ 

${\displaystyle =a^{n}-b^{n}.}$ 

Θεώρημα: Αν ο ${\displaystyle 2^{k}+1}$  είναι περιττός πρώτος, τότε ο ${\displaystyle k}$  είναι δύναμη του 2.

Απόδειξη:

Αν ${\displaystyle k}$  είναι ένας θετικός ακέραιος αριθμός αλλά όχι δύναμη του 2, τότε ${\displaystyle k=rs}$  όπου ${\displaystyle 1\leq r$ , ${\displaystyle 1$  και οι r και s είναι σχετικά πρώτοι. Άνευ βλάβης της γενικότητας πρέπει ο ${\displaystyle s}$  να είναι περιττός.

Σύμφωνα με το προηγούμενο λήμμα, για θετικό ακέραιο ${\displaystyle m}$ ,

${\displaystyle (a-b)\mid (a^{m}-b^{m})}$ 

όπου το σύμβολο ${\displaystyle \mid }$  σημαίνει μια «άρτια διαίρεση».

Αντικαθιστώντας ${\displaystyle a=2^{r}}$ , ${\displaystyle b=-1}$  και ${\displaystyle m=s}$  κάνοντας χρήση του ${\displaystyle s}$  ως περιττό αριθμό,

${\displaystyle (2^{r}+1)\mid (2^{rs}+1),}$ 

και ετσι

${\displaystyle (2^{r}+1)\mid (2^{k}+1).}$ 

Δεδομένου του ${\displaystyle 1<2^{r}+1<2^{k}+1}$ , προκύπτει ότι ο ${\displaystyle 2^{k}+1}$  δεν είναι πρώτος. Ως εκ τούτου, με αντιδιαστολή ο ${\displaystyle k}$  πρέπει να είναι δύναμη του 2.

Ένα κανονικό πολύγωνο με n πλευρές μπορεί να κατασκευαστεί με κανόνα και διαβήτη αν και μόνον αν ο n είναι γινόμενο μιας δύναμης του 2 ή διακριτός πρώτος Φερμά. Με άλλα λόγια, αν και μόνο αν ο n είναι της μορφής n = 2^kp₁p₂…p_s, όπου ο k είναι ένας μη αρνητικός ακέραιος αριθμός και οι p_i είναι διακριτοί πρώτοι Φερμά.

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

Δημιουργία ψευδοτυχαίων αριθμών

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

${\displaystyle V_{j+1}=\left(A\times V_{j}\right){\bmod {P}}}$    (βλ. Γραμμική συμβατική γεννήτρια, RANDU)

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

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

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

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

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

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

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

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

Γενικευμένοι πρώτοι Φερμά

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

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

Στην παρακάτω λίστα, οι γενικευμένοι αριθμοί Φερμά F_n(a), για άρτιο a είναι a²ⁿ + 1, για περιττό a, είναι (a²ⁿ + 1) / 2. Εάν ο a είναι μια τέλεια δύναμη με περιττό εκθέτη (ακολουθία A070265 στην OEIS), τότε όλοι οι γενικευμένοι αριθμοί Φερμά μπορεί να είναι πεπερασμένοι αλγεβρικά και έτσι δεν μπορεί να είναι πρώτοι. Για τον μικρότερο αριθμό n τέτοιο ώστε ο F_n(a) να είναι πρώτος, βλ. (ακολουθία A253242 στην OEIS).

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

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

a	b	Αριθμοί n τέτοιοι ώστε ο ${\displaystyle F_{n}(a,b)={\frac {a^{2^{n}}+b^{2^{n}}}{gcd(a+b,2)}}}$  να είναι πρώτος
2	1	0, 1, 2, 3, 4, ...
3	1	0, 1, 2, 4, 5, 6, ...
3	2	0, 1, 2, ...
4	1	0, 1, 2, 3, ...
4	3	0, 2, 4, ...
5	1	0, 1, 2, ...
5	2	0, 1, 2, ...
5	3	1, 2, 3, ...
5	4	1, 2, ...
6	1	0, 1, 2, ...
6	5	0, 1, 3, 4, ...
7	1	2, ...
7	2	1, 2, ...
7	3	0, 1, 8, ...
7	4	0, 2, ...
7	5	1, 4, ...
7	6	0, 2, 4, ...
8	1	(κανείς)
8	3	0, 1, 2, ...
8	5	0, 1, 2, ...
8	7	1, 4, ...
9	1	0, 1, 3, 4, 5, ...
9	2	0, 2, ...
9	4	0, 1, ...
9	5	0, 1, 2, ...
9	7	2, ...
9	8	0, 2, 5, ...
10	1	0, 1, ...
10	3	0, 1, 3, ...
10	7	0, 1, 2, ...
10	9	0, 1, 2, ...
11	1	1, 2, ...
11	2	0, 2, ...
11	3	0, 3, ...
11	4	1, 2, ...
11	5	1, ...
11	6	0, 1, 2, ...
11	7	2, 4, 5, ...
11	8	0, 6, ...
11	9	1, 2, ...
11	10	5, ...
12	1	0, ...
12	5	0, 4, ...
12	7	0, 1, 3, ...
12	11	0, ...
13	1	0, 2, 3, ...
13	2	1, 3, 9, ...
13	3	1, 2, ...
13	4	0, 2, ...
13	5	1, 2, 4, ...
13	6	0, 6, ...
13	7	1, ...
13	8	1, 3, 4, ...
13	9	0, 3, ...
13	10	0, 1, 2, 4, ...
13	11	2, ...
13	12	1, 2, 5, ...
14	1	1, ...
14	3	0, 3, ...
14	5	0, 2, 4, 8, ...
14	9	0, 1, 8, ...
14	11	1, ...
14	13	2, ...
15	1	1, ...
15	2	0, 1, ...
15	4	0, 1, ...
15	7	0, 1, 2, ...
15	8	0, 2, 3, ...
15	11	0, 1, 2, ...
15	13	1, 4, ...
15	14	0, 1, 2, 4, ...
16	1	0, 1, 2, ...
16	3	0, 2, 8, ...
16	5	1, 2, ...
16	7	0, 6, ...
16	9	1, 3, ...
16	11	2, 4, ...
16	13	0, 3, ...
16	15	0, ...

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

Η μικρότερη βάση b τέτοια ώστε ο b²ⁿ + 1 να είναι πρώτος, δίνει:

2, 2, 2, 2, 2, 30, 102, 120, 278, 46, 824, 150, 1534, 30406, 67234, 70906, 48594, 62722, 24518, 75898, ... (ακολουθία A056993 στην OEIS)

Ο μικρότερος k τέτοιος ώστε ο (2n)^k + 1 να είναι πρώτος, δίνει:

1, 1, 1, 0, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 0, 4, 1, ... (ο επόμενος όρος δεν είναι γνωστός), βλέπε την (ακολουθία A079706 στην OEIS), επίσης την (ακολουθία A228101 στην OEIS) και την (ακολουθία A084712 στην OEIS).

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

Οι μεγαλύτεροι γνωστοί γενικευμένοι πρώτοι Φερμά

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

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

• Golomb, Solomon W. (January 1, 1963), «On the sum of the reciprocals of the Fermat numbers and related irrationalities», Canadian Journal of Mathematics (Canadian Mathematical Society) 15: 475–478, doi:10.4153/CJM-1963-051-0, ISSN 0008-414X, http://cms.math.ca/10.4153/CJM-1963-051-0, ανακτήθηκε στις 2015-09-08 
• Grytczuk, A.; Luca, F.; Wójtowicz, M. (2001), «Another note on the greatest prime factors of Fermat numbers», Southeast Asian Bulletin of Mathematics (Springer-Verlag) 25 (1): 111–115, doi:10.1007/s10012-001-0111-4, ISSN 0129-2021, http://link.springer.com/article/10.1007/s10012-001-0111-4 
• Guy, Richard K. (2004), Unsolved Problems in Number Theory, Problem Books in Mathematics, 1 (3η έκδοση), New York: Springer Verlag, σελ. A3, A12, B21, ISBN 0-387-20860-7, http://www.springer.com/mathematics/numbers/book/978-0-387-20860-2?otherVersion=978-0-387-26677-0 
• Křížek, Michal; Luca, Florian; Somer, Lawrence (2001), 17 Lectures on Fermat Numbers: From Number Theory to Geometry, CMS books in mathematics, 10, New York: Springer, ISBN 0-387-95332-9, http://www.springer.com/mathematics/numbers/book/978-0-387-95332-8  - This book contains an extensive list of references.
• Křížek, Michal; Luca, Florian; Somer, Lawrence (2002), «On the convergence of series of reciprocals of primes related to the Fermat numbers», Journal of Number Theory (Elsevier) 97 (1): 95–112, doi:10.1006/jnth.2002.2782, ISSN 0022-314X, http://www.sciencedirect.com/science/journal/0022314X/97/1 
• Luca, Florian (2000), «The anti-social Fermat number», American Mathematical Monthly (Mathematical Association of America) 107 (2): 171–173, doi:10.2307/2589441, ISSN 0002-9890, http://www.maa.org/publications/periodicals/american-mathematical-monthly/american-mathematical-monthly-february-2000 
• Ribenboim, Paulo (1996), The New Book of Prime Number Records (3η έκδοση), New York: Springer, ISBN 0-387-94457-5, http://www.springer.com/mathematics/numbers/book/978-0-387-94457-9 
• Robinson, Raphael M. (1954), «Mersenne and Fermat Numbers», Proceedings of the American Mathematical Society (American Mathematical Society) 5 (5): 842–846, doi:10.2307/2031878 
• Yabuta, M. (2001), «A simple proof of Carmichael's theorem on primitive divisors», Fibonacci Quarterly (Fibonacci Association) 39: 439–443, ISSN 0015-0517, http://www.fq.math.ca/Scanned/39-5/yabuta.pdf 

• «Fermat prime». Encyclopædia Britannica. 
• Weisstein, Eric W., "Fermat Number" από το MathWorld.
• Weisstein, Eric W., "Fermat Prime" από το MathWorld.
• Weisstein, Eric W., "Fermat Pseudoprime" από το MathWorld.
• Weisstein, Eric W., "Generalized Fermat Number" από το MathWorld.