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

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

όπου 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.
 Το άθροισμα των αντίστροφων όλων των αριθμών Φερμά  είναι άρρητος αριθμός.Solomon W. Golomb (1963), σσ. 475–478

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

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

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

 Εικασία του Σέλφριτζ 
Ο Τζον Λ. Σέλφριτζ έκανε μια ενδιαφέρουσα εικασία. Έστω ότι g(n) είναι το πλήθος των διακριτών πρώτων παραγόντων του  . Τότε, η g(n) δεν είναι μονότονη (μη φθίνουσα) και αν υπάρχει κάποιος ακόμα πρώτος Φερμά, η εικασία θα συνεπάγεται.Prime Numbers: A Computational Perspective, Richard Crandall and Carl Pomerance, Second edition, Springer, 2011 Look up Selfridge's Conjecture in the Index.

 Άλλα θεωρήματα σχετικά με τους αριθμούς Φερμά 
Λήμμα: Αν 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 επαναλήψεις.

 Άλλα ενδιαφέροντα στοιχεία 
Ένας αριθμός Φερμά δεν μπορεί να είναι τέλειος αριθμός ή μέρος ενός ζεύγους φιλικών αριθμών.Luca (2000), σελ. 171–173

Η σειρά των αντίστροφων από όλους τους πρώτους διαιρέτες των αριθμών Φερμά είναι συγκλίνουσα.Křížek-Luca-Somer (2002), σελ. 95–112

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

Έστω ότι ο μεγαλύτερος πρώτος παράγοντας του αριθμού Φερμά Fn είναι ο P(Fn). Τότε ισχύει P(Fn) ≥ 2n+2(4n + 9) + 1.Grytczuk / Luca / Wójtowicz (2001), σελ. 111–115

 Γενικευμένοι αριθμοί Φερμά 
Οι αριθμοί της μορφής 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) να είναι πρώτος, βλ. .

aΑριθμοί n τέτοιοι ώστε ο Fn(a) να είναι πρώτος
|aΑριθμοί n τέτοιοι ώστε ο Fn(a) να είναι πρώτος
|aΑριθμοί n τέτοιοι ώστε ο Fn(a) να είναι πρώτος
|aΑριθμοί n τέτοιοι ώστε ο Fn(a) να είναι πρώτος20, 1, 2, 3, 4, ...180, ...342, ...50...30, 1, 2, 4, 5, 6, ...191, ...351, 2, 6, ...511, 3, 6, ...40, 1, 2, 3, ...201, 2, ...360, 1, ...520, ...50, 1, 2, ...210, 2, 5, ...370, ...533, ...60, 1, 2, ...220, ...38...541, 2, 5, ...72, ...232, ...391, 2, ...55...8(κανείς)241, 2, ...400, 1, ...561, 2, ...90, 1, 3, 4, 5, ...250, 1, ...414, ...570, 2, ...100, 1, ...261, ...420, ...580, ...111, 2, ...27(κανείς)433, ...591, ...120, ...280, 2, ...444, ...600, ...130, 2, 3, ...291, 2, 4, ...450, 1, ...610, 1, 2, ...141, ...300, 5, ...460, 2, 9, ...62...151, ...31...473, ...63...160, 1, 2, ...32(κανείς)482, ...64(κανείς)172, ...330, 3, ...491, ...651, 2, 5, ...

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

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

abΑριθμοί n τέτοιοι ώστε ο  να είναι πρώτος210, 1, 2, 3, 4, ...310, 1, 2, 4, 5, 6, ...320, 1, 2, ...410, 1, 2, 3, ...430, 2, 4, ...510, 1, 2, ...520, 1, 2, ...531, 2, 3, ...541, 2, ...610, 1, 2, ...650, 1, 3, 4, ...712, ...721, 2, ...730, 1, 8, ...740, 2, ...751, 4, ...760, 2, 4, ...81(κανείς)830, 1, 2, ...850, 1, 2, ...871, 4, ...910, 1, 3, 4, 5, ...920, 2, ...940, 1, ...950, 1, 2, ...972, ...980, 2, 5, ...1010, 1, ...1030, 1, 3, ...1070, 1, 2, ...1090, 1, 2, ...1111, 2, ...1120, 2, ...1130, 3, ...1141, 2, ...1151, ...1160, 1, 2, ...1172, 4, 5, ...1180, 6, ...1191, 2, ...11105, ...1210, ...1250, 4, ...1270, 1, 3, ...12110, ...1310, 2, 3, ...1321, 3, 9, ...1331, 2, ...1340, 2, ...1351, 2, 4, ...1360, 6, ...1371, ...1381, 3, 4, ...1390, 3, ...13100, 1, 2, 4, ...13112, ...13121, 2, 5, ...1411, ...1430, 3, ...1450, 2, 4, 8, ...1490, 1, 8, ...14111, ...14132, ...1511, ...1520, 1, ...1540, 1, ...1570, 1, 2, ...1580, 2, 3, ...15110, 1, 2, ...15131, 4, ...15140, 1, 2, 4, ...1610, 1, 2, ...1630, 2, 8, ...1651, 2, ...1670, 6, ...1691, 3, ...16112, 4, ...16130, 3, ...16150, ...

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

nΒάσεις με a τέτοιον ώστε ο Fn(a) να είναι πρώτος (εξετάζονται μόνο οι άρτιοι a)Ακολουθία OEIS02, 4, 6, 10, 12, 16, 18, 22, 28, 30, 36, 40, 42, 46, 52, 58, 60, 66, 70, 72, 78, 82, 88, 96, 100, 102, 106, 108, 112, 126, 130, 136, 138, 148, 150, ...A00609312, 4, 6, 10, 14, 16, 20, 24, 26, 36, 40, 54, 56, 66, 74, 84, 90, 94, 110, 116, 120, 124, 126, 130, 134, 146, 150, 156, 160, 170, 176, 180, 184, ...A00557422, 4, 6, 16, 20, 24, 28, 34, 46, 48, 54, 56, 74, 80, 82, 88, 90, 106, 118, 132, 140, 142, 154, 160, 164, 174, 180, 194, 198, 204, 210, 220, 228, ...A00006832, 4, 118, 132, 140, 152, 208, 240, 242, 288, 290, 306, 378, 392, 426, 434, 442, 508, 510, 540, 542, 562, 596, 610, 664, 680, 682, 732, 782, ...A00631442, 44, 74, 76, 94, 156, 158, 176, 188, 198, 248, 288, 306, 318, 330, 348, 370, 382, 396, 452, 456, 470, 474, 476, 478, 560, 568, 598, 642, ...A006313530, 54, 96, 112, 114, 132, 156, 332, 342, 360, 376, 428, 430, 432, 448, 562, 588, 726, 738, 804, 850, 884, 1068, 1142, 1198, 1306, 1540, 1568, ...A0063156102, 162, 274, 300, 412, 562, 592, 728, 1084, 1094, 1108, 1120, 1200, 1558, 1566, 1630, 1804, 1876, 2094, 2162, 2164, 2238, 2336, 2388, ...A0063167120, 190, 234, 506, 532, 548, 960, 1738, 1786, 2884, 3000, 3420, 3476, 3658, 4258, 5788, 6080, 6562, 6750, 7692, 8296, 9108, 9356, 9582, ...A0569948278, 614, 892, 898, 1348, 1494, 1574, 1938, 2116, 2122, 2278, 2762, 3434, 4094, 4204, 4728, 5712, 5744, 6066, 6508, 6930, 7022, 7332, ...A056995946, 1036, 1318, 1342, 2472, 2926, 3154, 3878, 4386, 4464, 4474, 4482, 4616, 4688, 5374, 5698, 5716, 5770, 6268, 6386, 6682, 7388, 7992, ...A05746510824, 1476, 1632, 2462, 2484, 2520, 3064, 3402, 3820, 4026, 6640, 7026, 7158, 9070, 12202, 12548, 12994, 13042, 15358, 17646, 17670, ...A05700211150, 2558, 4650, 4772, 11272, 13236, 15048, 23302, 26946, 29504, 31614, 33308, 35054, 36702, 37062, 39020, 39056, 43738, 44174, 45654, ...A088361121534, 7316, 17582, 18224, 28234, 34954, 41336, 48824, 51558, 51914, 57394, 61686, 62060, 89762, 96632, 98242, 100540, 101578, 109696, ...A0883621330406, 71852, 85654, 111850, 126308, 134492, 144642, 147942, 150152, 165894, 176206, 180924, 201170, 212724, 222764, 225174, 241600, ...A2265281467234, 101830, 114024, 133858, 162192, 165306, 210714, 216968, 229310, 232798, 422666, 426690, 449732, 462470, 468144, 498904, 506664, ...A2265291570906, 167176, 204462, 249830, 321164, 330716, 332554, 429370, 499310, 524552, 553602, 743788, 825324, 831648, 855124, 999236, 1041870, ...A2265301648594, 108368, 141146, 189590, 255694, 291726, 292550, 357868, 440846, 544118, 549868, 671600, 843832, 857678, 1024390, 1057476, 1087540, ...A2515971762722, 130816, 228188, 386892, 572186, 689186, 909548, 1063730, 1176694, 1361244, 1372930, ...A2538541824518, 40734, 145310, 361658, 525094, 676754, 773620, ...A2441501975898, 341112, 356926, 475856, ...A243959

Η μικρότερη βάση 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 και ισχύουν ως σήμερα.Ο τελευταίος έλεγχος έγινε τον Σεπτέμβριου του 2015.

 Θέση Θέση πρώτων Πρώτος αριθμός Γενικευμένος Φερμά Ψηφία Ανακάλυψη Πηγή 1  16  475856524288 + 1  F19(475856) 2,976,633 8 Αυγούστου 2012  2  17  356926524288 + 1  F19(356926) 2,911,151 20 Ιουνίου 2012 3  18  341112524288 + 1  F19(341112) 2,900,832 15 Ιουνίου 2012 4  21  75898524288 + 1  F19(75898) 2,558,647 19 Νοεμβρίου 2011  5  42  773620262144 + 1  F18(773620) 1,543,643 19 Απριλίου 2012  6  45  676754262144 + 1  F18(676754) 1,528,413 12 Φεβρουαρίου 2012  7  48  525094262144 + 1  F18(525094) 1,499,526 18 Ιανουαρίου 2012  8  52  361658262144 + 1  F18(361658) 1,457,075 29 Οκτωβρίου 2011  9  62  145310262144 + 1  F18(145310) 1,353,265 8 Φεβρουαρίου 2011  10  74  40734262144 + 1  F18(40734) 1,208,473 8 Μαρτίου 2011 

 Παραπομπές 

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

 - This book contains an extensive list of references.

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






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