Άρθρα

Ο μεγαλύτερος πρώτος αριθμός Μερσέν

Ο ΠΥΡΓΟΣ ΤΟΥ Β – ΜΙΑ ΜΑΘΗΜΑΤΙΚΗ ΠΕΡΙΠΕΤΕΙΑ, του Σάκη Ροδίτη

Απόσπασμα από το κεφάλαιο 4

«Η αίθουσα των αριθμών»

Εκδόσεις Ραδάμανθυς

Ο Σάκης Ροδίτης μιλάει στην παρουσίαση του βιβλίου του στην Πάτρα.

…Ο Ερατοσθένης ξεκίνησε την αγόρευσή του λύνοντάς μας την  απορία περί του λόγου του γιορτασμού. «Μόλις ανακαλύφθηκε από έναν οδοντίατρο στη Γερμανία που ασχολείται με τα Μαθηματικά, ο μεγαλύτερος πρώτος αριθμός με 9.152.052 ψηφία. Είναι ο 43ος αριθμός Mersenne[1]: 230.402.457 -1. Φυσικά υπάρχουν και άλλοι τέτοιοι αριθμοί με λιγότερα ψηφία, ας πούμε ο 225.964.951-1 με 7.816.230 ψηφία που ήταν ο 42ος αριθμός Mersenne. Για τον εντοπισμό πρώτων αριθμών συνεργάζονται 250.000 ηλεκτρονικοί υπολογιστές. Φυσικά, όταν με το καλό ολοκληρώσετε το ταξίδι σας θα μπορέσετε κι εσείς, αν βεβαίως το θέλετε, να πάρετε μέρος στο κυνήγι των πρώτων αριθμών Mersenne, μιας και το πρόγραμμα GIMPS παρέχει δωρεάν λογισμικό. Βλέπετε ακόμα δεν έχει βρεθεί αλγόριθμος για τον υπολογισμό πρώτων».

«Νομίζω… αν θυμάμαι καλά, πως αυτό ακριβώς το γεγονός της έλλειψης αλγόριθμου είναι που τους κάνει χρήσιμους στην κρυπτογραφία», διέκοψα για λίγο την αγόρευση του Ερατοσθένη βάζοντας συγχρόνως χυμό και παίρνοντας ένα σαντουιτσάκι.

roditis4«Φυσικά», συνέχισε ακάθεκτος ο γερο-σοφός, «αν βρισκόταν ένας αλγόριθμος για τον υπολογισμό πρώτων αριθμών, θα κατέρρεε το απόρρητο των τραπεζικών συναλλαγών, των καρτών, των e-mail κ.λ.π. γιατί όλα αυτά χρησιμοποιούν πρώτους αριθμούς, που έτσι κι αλλιώς παίζουν σημαντικό ρόλο στην κρυπτογραφία. Κι επειδή θα έχετε σίγουρα ακούσει για το κόσκινο του Ερατοσθένη, ακούστε κι αυτό: Ο Ερατοσθένης επινόησε μια μέθοδο για την εύρεση της ακολουθίας των πρώτων αριθμών που είναι μικρότεροι του ν  η οποία είναι πολύ απλή και περιγράφεται ως εξής: Κρατάμε τον πρώτο αριθμό 2 και διαγράφουμε όλα τα πολλαπλάσια του…» και λέγοντας έτσι μας έδειξε στον τοίχο το σχετικό πίνακα. Πάντως, αν θέλετε να δείτε, εδώ στον τοίχο πλάι στον πίνακα βρίσκονται οι πρώτοι αριθμοί μέχρι το 300:

2 3 5 7 11 13 17 19 23 29

31 37 41 43 47 53 59 61 67

71 73 79 83 89 97  101  103

107  109  113  127  131  137

139  149  151  157  163  167

173  179  181  191  193  197

199  211  223  227  229  233

239  241  251 257  263  269

271  277  281  283  293

Στη συνέχεια κρατάμε τον επόμενο πρώτο αριθμό 3 και διαγράφουμε όλα τα πολλαπλάσια του και συνεχίζουμε με τον ίδιο τρόπο για το 5, μετά κρατάμε το 7 και διαγράφουμε όλα τα πολλαπλάσια του και πάλι το ίδιο για το 11, συνεχίζουμε με τους 13 και 17. Όταν θέλουμε τους πρώτους αριθμούς που είναι μικρότεροι από το ν αρκεί να διαγράψουμε τα πολλαπλάσια όλων των πρώτων αριθμών p, για τους οποίους ισχύει p2 < ν. Ένα τελευταίο σχόλιο: Στην πρώτη εκατοντάδα υπάρχουν 25 πρώτοι αριθμοί. Στη δεύτερη εκατοντάδα υπάρχουν 21 πρώτοι αριθμοί. Στην τρίτη εκατοντάδα υπάρχουν 16 πρώτοι αριθμοί… στην εκατοντάδα από 901 μέχρι και το 1000 υπάρχουν μόνο 14. Στην πρώτη χιλιάδα υπάρχουν 168 πρώτοι αριθμοί. Στη χιλιάδα από 999.901 μέχρι το 1.000.000 υπάρχουν μόνο 8 πρώτοι αριθμοί. Ο κατάλογος των πρώτων αριθμών μας βοηθά να διαπιστώσουμε ότι καθώς οι αριθμοί μεγαλώνουν, οι πρώτοι αραιώνουν. Ποτέ όμως δεν τελειώνουν. Ποτέ η αραίωση δεν φτάνει στο μηδέν. Το ξεκαθάρισε ο Ευκλείδης  τον τρίτο π.Χ. αιώνα: ΔΕΝ υπάρχει  ο  μέγιστος  πρώτος  αριθμός.  Όμως, θα σας αφήσω να χαρείτε το πρωινό σας και τα ξαναλέμε».

Ο πύργος του Β Εκδόσεις Ραδάμανθυς

©Εκδόσεις Ραδάμανθυς & Σάκης Ροδίτης

[1] Οι πρώτοι αριθμοί της μορφής 2n−1 είναι γνωστοί ως πρώτοι του Μερσέν (Mersenne), από το όνομα του Μαρίν Μερσέν, που έζησε τον 17ο αιώνα και τους μελέτησε πρώτος. Ο Ευκλείδης ανακάλυψε ότι οι τέσσερις πρώτοι τέλειοι αριθμοί παράγονται από τον τύπο 2n−1(2n−1):

Για n =2: 21(22−1) =6

Για n =3: 22(23−1)=28

Για n = 5: 24(25−1) = 496

Για n =7: 26(27−1) =8128

Δύο χιλιάδες χρόνια μετά τον Ευκλείδη, ο Όιλερ (Euler) απέδειξε ότι ο τύπος 2n−1(2n − 1) μας δίνει όλους τους άρτιους τέλειους αριθμούς. Το αποτέλεσμα αυτό είναι γνωστό σαν Θεώρημα Ευκλείδη-Όιλερ. Είναι εύκολο να δειχθεί ότι ο 2n − 1 είναι πρώτος, όταν ο n είναι πρώτος, χωρίς όμως να ισχύει και το αντίστροφο. Μέχρι τον Μάιο του 2009, ο μεγαλύτερος γνωστός πρώτος αριθμός, που είναι και ο 46ος Μερσέν, είναι ο 243..112.609 − 1  με 12.978.189 ψηφία.


Για παραγγελίες του βιβλίου συμπληρώστε τη φόρμα επικοινωνίας ή καλέστε στο 6983 091058

Δωρεάν αποστολή σε όλη την Ελλάδα και στην Κύπρο

Αρχική τιμή: 23,50 €
Εξοικονομείτε: 4,50 € (Έκπτωση 19%)
Τιμή για εσάς: 19,00 €

Ο πύργος του β

 

Σχολιάστε

Εισάγετε τα παρακάτω στοιχεία ή επιλέξτε ένα εικονίδιο για να συνδεθείτε:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s