Οι πρώτοι αριθμοί του Mersenne

Ο Martin Mersenne (Μερσέν) (1588-1648) ήταν ένας Γάλλος καλόγερος που τα ενδιαφέροντά του δεν περιορίζονταν μόνο σε θρησκευτικά θέματα!

Ήταν θεολόγος, φιλόσοφος, μαθηματικός και θεωρητικός της μουσικής.

Λάτρευε τη μουσική και ήταν ο πρώτος που ανέπτυξε μια ολοκληρωμένη θεωρία αρμονίας, έτσι συχνά αναφέρεται και ως ο «πατέρας της ακουστικής».

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

Ο Μερσέν έδειξε πολύ μεγάλο ενδιαφέρον για τους πρώτους αριθμούς (πρώτος είναι ένας αριθμός που διαιρείται μόνο από την μονάδα και τον εαυτό του) και έφτιαξε ένα μηχανισμό με τον οποίο προσπαθούσε να τους παράγει.

Η ιδέα του Μερσέν ήταν πάρα πολύ απλή. Προσπαθούσε να φτιάξει πρώτους αριθμούς πολλαπλασιάζοντας το 2 πολλές φορές με τον εαυτό του και αφαιρώντας την μονάδα (2^N–1) για παράδειγμα 2x2x2x2x2 – 1 = 31 που είναι πρώτος αριθμός.

Βέβαια ο μηχανισμός αυτός δεν έδινε πάντα πρώτους αριθμούς, ο αριθμός 2x2x2x2 – 1 = 15 δεν είναι πρώτος αριθμός.

Γρήγορα κατάλαβε πως για να είναι ο 2^N–1 πρώτος αριθμός έπρεπε και το N να είναι πρώτος αριθμός. Ο αριθμός 2^4–1 δεν είναι πρώτος αφού το 4 είναι σύνθετος αριθμός (όχι πρώτος).

Η κατάσταση έγινε ακόμα πιο πολύπλοκη όταν αντιλήφθηκε ότι ακόμα και αν ο εκθέτης N είναι πρώτος αριθμός, ο αριθμός 2^N–1 δεν είναι υποχρεωτικά πρώτος αριθμός. Ο αριθμός 2^11–1=2047=23∗89 είναι σύνθετος παρόλο που το 11 είναι πρώτος αριθμός.

Μέσα από την μελέτη αυτών των αριθμών ο Μερσέν κάνει μία πρόβλεψη:
Ο αριθμός 2^N–1 είναι πρώτος αριθμός για τις τιμές του N 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257
Ο αριθμός 2^257–1 είναι τόσο μεγάλος που πάρα πολύ δύσκολα κάποιος θα μπορούσε να αμφισβητήσει την πρόβλεψή του.

Το 1857 ο Γάλλος μαθηματικός Edouard Lucas (1842 – 1891) σε ηλικία 15 ετών άρχισε να ελέγχει τον αριθμό 2^127–1 για να δει αν είναι πρώτος, χρησιμοποιώντας μια μέθοδο που ο ίδιος είχε ανακαλύψει. Το 1876 μετά από 19 χρόνια δοκιμών και μάλιστα με το χέρι, ο Lucas απόδειξε ότι ο αριθμός 2^127–1 που έχει 39 ψηφία, είναι πρώτος. Χρησιμοποιώντας την ίδια μέθοδο, ο Lucas απέδειξε πως ο Mersenne είχε παραλείψει από τον κατάλογο των αριθμών N για τους οποίους ο 2^N–1 είναι πρώτος, τους 61, 89 και 107 ενώ είχε συμπεριλάβει λανθασμένα το 67.

Παρόλη τη σημαντική δουλειά του Lucas στους πρώτους αριθμούς του Mersenne, ο αριθμός 2^257–1 ήταν ακόμα ένα απόρθητο κάστρο, ώσπου το 1930 ένας Αμερικανός μαθηματικός ο Derrick Henry Lehmer σε ηλικία 25 ετών, βελτιώνοντας την μέθοδο του Lucas να ρίξει λίγη σκιά στη λαμπερή φήμη του Mersenne αποδεικνύοντας ότι ο αριθμός 2257–1 δεν είναι πρώτος αριθμός.

Η μέθοδος του Lehmer είναι απλή στην υλοποίηση αλλά καταπληκτική στη σύλληψή της. Ο Lehmer απέδειξε ότι ο αριθμός 2^N–1 με Ν πρώτο αριθμό, είναι πρώτος αριθμός αν διαιρεί έναν άλλο αριθμό που ονομάστηκε αριθμός Lucas – Lehmer και συμβολίζεται με L(N).

Οι αριθμοί Lucas – Lehmer ορίζονται με αναδρομικό τρόπο. Έτσι για να βρούμε τον L(N) υψώνουμε τον προηγούμενό του στο τετράγωνο και αφαιρούμε το 2, δηλαδή: L(N)=L(N–1)^2–2.

Για παράδειγμα για Ν = 3 θέτουμε σημείο εκκίνησης L(3) = 14 και συνεπώς:
$L(4) = 14^2 – 2 = 194, L(5) = 194^2 – 2 = 37634, L(6) = 37634^2 – 2 = 1416317955$,…
Ο αριθμός λοιπόν 2^5–1=31 διαιρεί τον L(5) = 37634 και συνεπώς είναι πρώτος.

Με αυτό τον τρόπο κλείνει ο κύκλος των προβλέψεων του Mersenne και ανοίγει ο δρόμος για την ανακάλυψη και άλλων πρώτων αριθμών του Mersenne που λόγω της μορφής τους φτάνουν σε απίστευτο αριθμό ψηφίων, μόνο που τώρα οι μαθηματικοί εκτός της μεθόδου Lucas – Lehmer ( Lucas – Lehmer primality test ) έχουν συμμάχους τους και τους υπολογιστές. Με την βοήθειά τους σήμερα είναι γνωστοί 48 αριθμοί του Mersenne εκ των οποίων ο τελευταίος είναι ο 2^57885161–1 που έχει 17.425.170 ψηφία!!