Πρώτοι αριθμοί

Οι πρώτοι αριθμοί είναι αρκετά απλοί. Ακόμη κι ένα μικρό παιδί μπορεί να κατανοήσει τη φύση τους, αρκεί να γνωρίζει διαίρεση. Γιατί τότε υπάρχουν προβλήματα γύρω από τους πρώτους, που ταλαιπωρούν τις μεγαλύτερες διάνοιες στο χώρο των μαθηματικών για περισσότερο από έναν αιώνα τώρα; Τι δουλειά έχουν οι πρώτοι αριθμοί με τον κβαντικό μικρόκοσμο; Πώς εμπλέκονται οι μιγαδικοί αριθμοί στην όλη ιστορία; Θα αλλάξει η ζωή μας αν κι όποτε αποδειχθεί, επιτέλους, η εικασία του Riemann, το ιερό δισκοπότηρο των μαθηματικών;

Οι πρώτοι αριθμοί είναι κάτοικοι του συνόλου των λεγόμενων φυσικών αριθμών, τους οποίους χρησιμοποιούμε, μεταξύ άλλων, για να μετράμε. Ανάλογα με το κείμενο που διαβάζετε, άλλοτε θα βλέπετε πως οι φυσικοί αριθμοί ξεκινάνε από το 0 κι άλλοτε από το 1. Η συμπερίληψη του μηδενός στους φυσικούς βολεύει τους μαθηματικούς που ασχολούνται με τη Θεωρία Συνόλων, ενώ η απουσία του εκείνους που δουλεύουν στη Θεωρία Αριθμών. Αλλά ας μην παρασυρόμαστε με λεπτομέρειες και τεχνικά ζητήματα -- τουλάχιστον όχι από τόσο νωρίς. Ποιοι είναι, λοιπόν, οι πρώτοι αριθμοί; Πολύ απλά, είναι όλοι εκείνοι οι φυσικοί αριθμοί που είναι μεγαλύτεροι από το μηδέν και διαιρούνται μόνο με το 1 και τον εαυτό τους. Εδώ ίσως πρέπει να ξεκαθαρίσουμε ότι όταν λέμε πως ένας φυσικός a διαιρείται από έναν φυσικό b , εννοούμε πώς το υπόλοιπο της διαίρεσης a/b είναι μηδέν. Είναι προφανές πως οποιοσδήποτε αριθμός που δεν είναι μηδέν διαιρείται με τη μονάδα και τον ίδιο του τον εαυτό -- έχει, δηλαδή, τουλάχιστον δύο διαιρέτες. Κάποιοι φυσικοί αριθμοί έχουν ακριβώς δύο διαιρέτες, π.χ., οι 2, 3 και 7, ενώ κάποιοι άλλοι έχουν περισσότερους από δύο, π.χ., οι 9, 12 και 18. Ένας εναλλακτικός ορισμός των πρώτων, λοιπόν, είναι να πούμε πως πρόκειται για τους φυσικούς που είναι μεγαλύτεροι από το μηδέν κι έχουν ακριβώς δύο διαιρέτες. Η λίστα των πρώτων αριθμών ξεκινά έτσι:
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, ...
Θα παρατηρήσατε πως απουσιάζει το 1, ένας αριθμός που από τον προηγούμενο ορισμό είναι ξεκάθαρα πρώτος. Οι μαθηματικοί όμως δεν θέλουν το 1 στη λίστα με τους πρώτους αριθμούς, αφενός επειδή αποτελεί "τετριμμένη περίπτωση", όπως συνηθίζουν να λένε, αφετέρου διότι δημιουργεί προβλήματα στην περαιτέρω ανάπτυξη σχετικών θεωριών. Παρατηρήστε, επίσης, ότι το 2 είναι ο μοναδικός πρώτος που ταυτόχρονα είναι ζυγός. Είναι προφανές πως δεν υπάρχει ζυγός πρώτος μεγαλύτερος του 2. Πράγματι, κάθε ζυγός μεγαλύτερος από το δύο έχει τουλάχιστον τρεις διαιρέτες --τη μονάδα, το 2 και τον εαυτό του--, επομένως δεν είναι πρώτος.

Δομικοί λίθοι
Θα μπορούσαμε να πούμε πως οι πρώτοι είναι για τους αριθμούς ό,τι είναι τα άτομα για την ύλη: έχουν το ρόλο δομικών λίθων! Πράγματι, το Θεμελιώδες Θεώρημα της Αριθμητικής μας βεβαιώνει πως κάθε φυσικός μεγαλύτερος της μονάδας είτε είναι πρώτος είτε εκφράζεται ως γινόμενο πρώτων παραγόντων. Επιπρόσθετα, η ανάλυση ενός οποιουδήποτε αριθμού σε γινόμενο πρώτων παραγόντων είναι μοναδική, εκτός ίσως από τη σειρά που γράφονται οι παράγοντες αυτοί. Έτσι, ο αριθμός 30 μπορεί να γραφτεί μοναδικά ως 2⋅3⋅5     , ο 6936 ως 23⋅3⋅17    2, 

Μια πρώτη έκπληξη
Μια πρακτική εφαρμογή που βρίσκουν οι πρώτοι αριθμοί είναι στην κρυπτογραφία, που ως τεχνική χρησιμοποιείται π.χ. στη διασφάλιση του απορρήτου των τηλεπικοινωνιών ή σε εμπορικές εφαρμογές. Για παράδειγμα, όποτε κάνουμε μια αγορά από το ίντερνετ με την πιστωτική μας κάρτα, η συναλλαγή με το ηλεκτρονικό κατάστημα κρυπτογραφείται. Απουσία των πρώτων αριθμών --και με δεδομένη την ισχύ των σύγχρονων υπολογιστών--, η όποια μέθοδος κρυπτογράφησης είναι πολύ πιθανό πως θα έσπαζε εύκολα κι επομένως τα στοιχεία της πιστωτικής μας θα γίνονταν γνωστά σε τρίτους. Τώρα, σε μια ισχυρή μέθοδο κρυπτογράφησης είναι απαραίτητο να υπεισέρχονται πολύ μεγάλοι πρώτοι αριθμοί (μεγαλύτεροι από 10100 ), επομένως χρειάζονται μέθοδοι ή αλγόριθμοι ευρέσεως πρώτων. Χρειάζονται, επίσης, αλγόριθμοι που θα αποφασίζουν εάν ένας αριθμός είναι πρώτος ή όχι. Μπορείτε π.χ. να βρείτε αν ο αριθμός 2047 είναι πρώτος; Με μια πρώτη ματιά μάλλον όχι, εκτός κι αν έχετε κάποιο ιδιαίτερο χάρισμα στη διαίρεση. Όπως και να 'χει, με λίγο ή πολύ κόπο θα διαπιστώσετε ότι το 2047 διαιρείται με το 89 αλλά και με το 23, επομένως δεν είναι πρώτος. Καλώς. Τι μπορείτε όμως να πείτε για τον αριθμό 2147483647; Για τον 2305843009213693951; (Είναι και οι δύο πρώτοι, μάλιστα ανήκουν στους λεγόμενους πρώτους του Mersenne.)
Ένα φυσικό ερώτημα που αργά ή γρήγορα προκύπτει αφορά στο πλήθος των πρώτων αριθμών. Είναι άραγε πεπερασμένο ή άπειρο; Μπορεί να υπάρχουν αλγόριθμοι --μάλιστα από την αρχαιότητα-- που εντοπίζουν πρώτους, όμως το γεγονός αυτό δεν μας λέει τίποτε για το πλήθος τους. Στις σύγχρονες εφαρμογές χρησιμοποιούνται τεράστιοι πρώτοι, όμως ούτε αυτό το γεγονός διασφαλίζει ότι μετά τον μεγαλύτερο γνωστό πρώτο περιμένει άλλος ένας. Πέρα από τις όποιες πρακτικές εφαρμογές, οι μαθηματικοί θέλουν να γνωρίζουν -- και σ' αυτή την περίπτωση τουλάχιστον γνωρίζουν! Πριν όμως τους ρωτήσουμε για το πλήθος των πρώτων, έχει πολύ ενδιαφέρον να κάνουμε μόνοι μας ένα πείραμα. Με τη βοήθεια ενός προγράμματος όπως είναι το Mathematica, μπορούμε να διεξάγουμε μια προσωπική, προκαταρκτική έρευνα για την κατανομή των πρώτων. Ο ακόλουθος πίνακας είναι το αποτέλεσμα μιας τέτοιας απόπειρας.

φυσικός m               πρώτοι αριθμοί          ποσοστό πρώτων                         μικρότεροι από το m     μεταξύ 0 και m ------------------------------------------------------------------------- 1000                    168                     16,8 1000000                 78498                   7,8498 1000000000              50847534                5,0847534 1000000000000           37607912018             3,7607912 1000000000000000        29844570422669          2,98445704 1000000000000000000     24739954287740800       2,47399543

Παρατηρούμε ότι όσο το m μεγαλώνει, το ποσοστό των πρώτων που είναι μικρότεροι από το m μικραίνει. Οι πρώτοι αριθμοί είναι μάλλον "αραιοί" μέσα στους φυσικούς. Μάλιστα, εξετάζοντας ολοένα κι ευρύτερα διαστήματα αριθμών βλέπουμε ότι οι πρώτοι αραιώνουν ολοένα και περισσότερο! Είναι εύλογο να σκεφτούμε πως, κάποια στιγμή, για αρκετά μεγάλο m , το ποσοστό των πρώτων θα πέσει στο μηδέν και δεν θα ανακάμψει ποτέ ξανά: Οι πρώτοι θα έχουν τελειώσει!
Η προηγούμενη έρευνα είναι σίγουρα ενδιαφέρουσα --τουλάχιστον για όσους έχουν μέσα τους έστω κι ένα ελάχιστο ίχνος του μαθηματικού μικροβίου--, σίγουρα όμως δεν αποτελεί απόδειξη για το πλήθος των πρώτων. Για να δώσει ένας μαθηματικός τελεσίδικη απάντηση σε ένα οποιοδήποτε ερώτημα, οσοδήποτε απλό ή σύνθετο, δεν δικαιούται να αρκεστεί σε ενδείξεις. Χρειάζεται μια αυστηρή απόδειξη, που θα ξεκαθαρίζει τα πράγματα πέρα από κάθε αμφιβολία. Αναφορικά με το πλήθος των πρώτων, λοιπόν, ήδη από την αρχαιότητα ο Ευκλείδης απέδειξε ότι είναι άπειρο. Ο προηγούμενος πίνακας έχει συμπληρωθεί σωστά, είναι όμως παραπλανητικός!
Εκφράζοντας την απόδειξη του Ευκλείδη στη σύγχρονη μαθηματική γλώσσα, ας ονομάσουμε p τον μεγαλύτερο πρώτο κι ας σχηματίσουμε τον αριθμό
q=2×3×5×7×⋯×p+1
Με άλλα λόγια, ο q προκύπτει αν πολλαπλασιάσουμε τους πρώτους αριθμούς μεταξύ 2 και p συμπεριλαμβανομένων, και στο γινόμενο προσθέσουμε μία μονάδα. Ο q δεν διαιρείται με κανέναν αριθμό μεταξύ 2 και p , αφού πάντα μένει υπόλοιπο η μονάδα. Επομένως, είτε ο q είναι πρώτος αριθμός, προφανώς μεγαλύτερος από τον p , είτε διαιρείται με κάποιον αριθμό μεγαλύτερο από τον p . Αν υποθέσουμε ότι ισχύει το τελευταίο κι ονομάσουμε r τον μικρότερο αριθμό που είναι μεγαλύτερος από τον p και ταυτόχρονα διαιρεί τον q , διαπιστώνουμε πως και ο r , αναγκαστικά, είναι πρώτος! Πράγματι, εάν ο r δεν ήταν πρώτος, τότε οποιοσδήποτε από τους πρώτους παράγοντές του θα ήταν μικρότερος από τον p και θα διαιρούσε τον q , γεγονός που αντιβαίνει στην υπόθεσή μας (ότι, δηλαδή, ο q διαιρείται με κάποιον αριθμό μεγαλύτερο από τον p ).
Συνοψίζοντας, βλέπουμε ότι για έναν οποιονδήποτε αριθμό, ασχέτως αν είναι πρώτος ή όχι, υπάρχει πάντοτε ένας μεγαλύτερος πρώτος. Επομένως, το πλήθος των πρώτων αριθμών είναι άπειρο.
Εκπληκτικές ιδιότητες, ατίθασα προβλήματα
Οι πρώτοι αριθμοί παρουσιάζονται ως "ταπεινά" μαθηματικά όντα: Το ειδοποιό χαρακτηριστικό που τους ξεχωρίζει από τους υπόλοιπους φυσικούς αριθμούς είναι ιδιαίτερα απλό. Την ίδια στιγμή, όμως, έχουν αρκετές θαυμαστές ιδιότητες. Ακολουθούν ορισμένες από αυτές.

• Εάν ο πρώτος p διαιρεί το γινόμενο a⋅b , τότε διαιρεί τουλάχιστον έναν από τους φυσικούς a , b (Λήμμα του Ευκλείδη).
• Εάν ο p είναι ένας οποιοσδήποτε πρώτος κι a ένας οποιοσδήποτε φυσικός αριθμός μεγαλύτερος από τη μονάδα, τότε ο αριθμός ap - a διαιρείται από τον p (Μικρό Θεώρημα του Fermat). Για παράδειγμα, αν p=11 κι a=8 , τότε ο αριθμός 811 – 8=8589934584 διαιρείται ακριβώς με το 11 (το αποτέλεσμα είναι 780903144).
• Εάν m είναι ένας φυσικός μεγαλύτερος του 1, τότε υπάρχει τουλάχιστον ένας πρώτος μεταξύ των αριθμών m και 2m . Πρόκειται για την υπόθεση του Joseph Bertrand (1822-1900), ο οποίος την επαλήθευσε για τους φυσικούς που είναι μικρότεροι ή ίσοι από το 3000000. Η υπόθεση αποδείχτηκε πλήρως το 1850 από τον Pafnuty Chebyshev (1821-1894).
• Το (άπειρο) άθροισμα των αντίστροφων όλων των πρώτων αριθμών τείνει στο άπειρο (αποκλίνει). Συμβολικά, ισχύει ∑1p=∞ , όπου το p διατρέχει όλους τους πρώτους.
• Ένας φυσικός p>1 είναι πρώτος, εάν και μόνον εάν η ποσότητα (p – 1)!+1 διαιρείται με το p (θεώρημα Wilson). Το σύμβολο του θαυμαστικού διαβάζεται "παραγοντικό" κι εξ' ορισμού ισχύει m!=1⋅2⋯m (π.χ., 5!=1⋅2⋅3⋅4⋅5=120 ). Επειδή το παραγοντικό μεγαλώνει πολύ γρήγορα, το θεώρημα του Wilson δεν μπορεί να αποτελέσει ένα πρακτικό τεστ, ώστε να διαπιστώνουμε αν ένας αριθμός είναι πρώτος ή όχι. Για παράδειγμα, αν p=13 τότε (13 - 1)!+1=479001601(=13⋅36846277) . Βέβαια στο συγκεκριμένο παράδειγμα γνωρίζαμε εξ' αρχής ότι το 13 είναι πρώτος. Δείτε ωστόσο πόσο μεγάλους αριθμούς εμπλέκει το θεώρημα του Wilson, ακόμα και για μικρούς φυσικούς...
• Κάθε αριθμητική πρόοδος a , a+b , a+2b , a+3b , ..., όπου οι φυσικοί a και b≥1 είναι σχετικά πρώτοι, περιλαμβάνει άπειρους πρώτους αριθμούς (Θεώρημα Dirichlet). Δύο φυσικοί αριθμοί a και b ονομάζονται σχετικά πρώτοι, αν εκτός από τη μονάδα δεν έχουν άλλον κοινό διαιρέτη (ισοδύναμα: όταν ο μέγιστος κοινός διαιρέτης τους είναι η μονάδα). Για παράδειγμα, οι αριθμοί 8 και 35 είναι σχετικά πρώτοι, αφού μοναδικός κοινός διαιρέτης τους είναι το 1. Από την άλλη οι 8 και 12 δεν είναι, αφού και οι δύο διαιρούνται με το 2. Παρατηρήστε ότι δύο σχετικά πρώτοι αριθμοί δεν είναι κατ' ανάγκη πρώτοι. Επιστρέφοντας στο θεώρημα του Dirichlet, για a=2 και b=9 παίρνουμε την αριθμητική πρόοδο (ακολουθία)
  
  
  2,11,20,29,…,119,128,… Με μια πρώτη ματιά παρατηρούμε ότι περιλαμβάνει ορισμένους σύνθετους αριθμούς, όπως τους 20, 29, 119 (= 17⋅7 ) και 128, καθώς και κάποιους πρώτους, όπως τους 2 και 11. Το θέμα είναι ότι το θεώρημα του Dirichlet μας απαλλάσσει από κάθε αγωνία αναζήτησης, διαβεβαιώνοντάς μας πως η παραπάνω ακολουθία περιλαμβάνει άπειρους πρώτους.

Συνδεδεμένες με τους πρώτους αριθμούς είναι ορισμένες απλές στη διατύπωση μαθηματικές εικασίες, η αλήθεια ή το ψεύδος των οποίων δεν έχει ξεκαθαρίσει έως σήμερα. Θαυμάστε την απλότητα ορισμένων εξ' αυτών.

• Κάθε ζυγός φυσικός αριθμός μεγαλύτερος του 2 μπορεί να γραφτεί ως άθροισμα δύο πρώτων (εικασία του Goldbach). Έχουμε, π.χ., 8 = 3 + 5, 22 = 5 + 17 κ.ο.κ.
• Υπάρχουν άπειρα ζεύγη διδύμων πρώτων (εικασία των διδύμων). Δύο πρώτοι ονομάζονται δίδυμοι, όταν η διαφορά τους είναι 2. Για παράδειγμα, οι πρώτοι 11 και 13 είναι δίδυμοι, όπως επίσης και οι 347, 349 κ.ά.
• Γενίκευση της προηγούμενης αποτελεί η εικασία του Polignac: Για κάθε φυσικό αριθμό υπάρχουν άπειρα ζεύγη διαδοχικών πρώτων, με διαφορά 2m . Παίρνοντας, π.χ., m=3 , η εικασία του Polignac μάς λέει ότι υπάρχουν άπειρα ζεύγη διαδοχικών πρώτων με διαφορά 6 (π.χ., οι 61, 67 είναι διαδοχικοί πρώτοι που διαφέρουν κατά 6).
• Υπάρχουν άπειροι πρώτοι της μορφής m2+1 . Για παράδειγμα, οι πρώτοι 5, 17, 37 και 101 έχουν την προηγούμενη μορφή ( 5=22+1 , 17=42+1 και 101=102+1 ).
• Υπάρχουν τουλάχιστον τέσσερις πρώτοι, μεταξύ των τετραγώνων δύο διαδοχικών πρώτων μεγαλύτερων του 2 (εικασία Brocard). Για παράδειγμα, μεταξύ των αριθμών 9 και 25 (τετράγωνα των διαδοχικών πρώτων 3 και 5) υπάρχουν πέντε πρώτοι (οι 11, 13, 17, 19 και 23), μεταξύ των 25 και 49 (τετράγωνα των 5 και 7) υπάρχουν έξι πρώτοι (οι 29, 31, 37, 41, 43 και 47) κ.ο.κ.
• Υπάρχει πάντα ένας πρώτος μεταξύ των m2 και (m+1)2 , για κάθε φυσικό αριθμό m (εικασία Legendre). Αν, π.χ., m=3 , τότε μεταξύ των φυσικών 9 και 16 υπάρχουν οι πρώτοι 11 και 13.
• Η ακολουθία Fibonacci περιέχει άπειρο πλήθος πρώτων. Η εν λόγω ακολουθία ξεκινά με τους αριθμούς 0 και 1 και κάθε όρος της είναι το άθροισμα των δύο προηγουμένων. Ιδού οι αρχικοί της όροι: 0, 1, 1, 2, 3, 5, 8, 13, 21, 23, 55, 89, 144, 233, 377, 610, ... Οι αριθμοί της ακολουθίας Fibonacci βρίσκουν πολλές εφαρμογές (χρησιμοποιούνται, π.χ., στις γεννήτριες ψευδοτυχαίων αριθμών). Εξάλλου, οι αριθμοί αυτοί παρατηρούνται συχνά και στη φύση, όπως, π.χ., στα σπειροειδή μοτίβα κελυφών και στις διακλαδώσεις δέντρων.
• Υπάρχουν άπειροι πρώτοι του Mersenne. Πρόκειται για πρώτους αριθμούς που μπορούν να γραφτούν με τη μορφή 2p – 1 , όπου το p είναι πρώτος αριθμός. Για παράδειγμα, ο πρώτος αριθμός 31 είναι του Mersenne, επειδή μπορεί να γραφτεί ως 25 – 1 και το 5 είναι πρώτος. Από την άλλη, ο αριθμός 211 – 1=2047 μοιάζει υποψήφιος για πρώτος του Mersenne (ο 11 είναι πρώτος) ωστόσο δεν είναι, επειδή το 2047 διαιρείται από τους 89 και 23.

Κυνηγώντας πρώτους
Το ζήτημα του πλήθους των πρώτων έκλεισε πολύ νωρίς, γύρω στο 300 π.Χ. Οι μαθηματικοί όμως δεν μένουν εύκολα ευχαριστημένοι. Θέλουν, επιπρόσθετα, μεθόδους εύρεσης --ή εντοπισμού, αν προτιμάτε--, πρώτων αριθμών. Την αρχαιότερη μέθοδο εντοπισμού πρώτων τη χρωστάμε στον Ερατοσθένη (276 π.Χ. – 194 π.Χ.). Πρόκειται για το λεγόμενο Κόσκινο του Ερατοσθένη, έναν εκπληκτικά απλό αλγόριθμο που μπορεί και βρίσκει όλους τους πρώτους που είναι μικρότεροι ή ίσοι προς έναν δοσμένο φυσικό αριθμό. Δυστυχώς, το κόσκινο αποδεικνύεται ακατάλληλο για τις σημερινές εφαρμογές κι ανάγκες. Μια σύγχρονη, αποδοτική εκδοχή του αποτελεί το κόσκινο του Atkin, που ανέπτυξαν πρόσφατα οι Atkin και Bernstein. Ο σχετικός αλγόριθμος επιτρέπει την ταχύτατη εύρεση όλων των πρώτων που είναι μικρότεροι από έναν δοσμένο αριθμό. Μια υλοποίηση του αλγορίθμου και τον πηγαίο κώδικα σε γλώσσα C θα βρείτε στο δικτυακό τόπο http://cr.yp.to/primegen.html.
Σε άλλες εφαρμογές είναι συχνά επιθυμητό να γνωρίζουμε αν ένας συγκεκριμένος φυσικός είναι πρώτος ή όχι. Επειδή οι αριθμοί που συζητάμε ενδέχεται να έχουν χιλιάδες ή εκατομμύρια ψηφία, ακόμη και ένας αποδοτικός αλγόριθμος σε υπολογιστή είναι πιθανό να απαιτεί απαγορευτικά μεγάλο χρόνο, πριν δώσει τελεσίδικη απάντηση. Για το σκοπό αυτό έχουν αναπτυχθεί πιθανοκρατικοί αλγόριθμοι, οι οποίοι αφού εξετάσουν έναν αριθμό τον ανακηρύσσουν πιθανώς πρώτο ή οπωσδήποτε σύνθετο (σύνθετος, είναι άλλη μια ονομασία για τους αριθμούς που δεν είναι πρώτοι).
Το καλοκαίρι του 2002, τρεις Ινδοί ερευνητές, οι Manindra Agrawal, Neeraj Kayal και Nitin Saxena, επινόησαν έναν αλγόριθμο ελέγχου πρώτων (AKS primality test), ο οποίος διακρίνεται από τρεις εξαιρετικά επιθυμητές ιδιότητες. Καταρχάς, ο αλγόριθμος AKS είναι πολυωνυμικός. Αυτό σημαίνει ότι ο χρόνος που απαιτεί πριν δώσει απάντηση αυξάνει σχετικά "ομαλά" και πάντα ανάλογα με το πλήθος των ψηφίων του υπό εξέταση αριθμού. Άλλοι αλγόριθμοι του είδους είναι εκθετικοί, που σημαίνει ότι αν τους δώσουμε έναν αριθμό προς εξέταση και μετά έναν άλλον, με ένα μόλις παραπάνω ψηφίο, ο χρόνος που θα δαπανήσουν για την εξέταση του δευτέρου θα είναι δυσανάλογα μεγαλύτερος, σε σχέση με το χρόνο που δαπάνησαν για την εξέταση του πρώτου. Η άλλη χρήσιμη ιδιότητα του αλγορίθμου AKS αφορά στον ντετερμινιστικό του χαρακτήρα: Οι απαντήσεις που δίνει είναι τελεσίδικες, χωρίς να εμπλέκουν πιθανότητες. Όσα και να είναι τα ψηφία του υπό εξέταση αριθμού, ο αλγόριθμος τελικά θα βρει, με απόλυτη βεβαιότητα, αν είναι πρώτος ή όχι. Η τρίτη ιδιότητα του AKS, αυτή που τον ξεχωρίζει από τον "σωρό", αφορά στην ανεξαρτησία του από αναπόδεικτες μαθηματικές εικασίες. Αντίθετα, πολλοί άλλοι αλγόριθμοι που εξετάζουν αν ένας αριθμός είναι πρώτος ή όχι είναι έτσι σχεδιασμένοι, ώστε να προϋποθέτουν την αλήθεια της υπόθεσης του Riemann. Τι είναι όμως αυτή η υπόθεση; Σύντομα θα δούμε, προς το παρόν όμως αρκεί να πούμε ότι πρόκειται για ένα απίστευτα δύσκολο μαθηματικό πρόβλημα, η λύση του οποίου διαφεύγει από τους μαθηματικούς εδώ και 150 χρόνια. Η υπόθεση του Riemann συνδέεται με την κατανομή των πρώτων αριθμών, ξεφεύγει όμως από το σύμπαν των μαθηματικών και δείχνει να αγγίζει τον κβαντικό μικρόκοσμο, που αποτελεί τη βάση του κόσμου γύρω μας.

Πρώτο τέρας
Ο μεγαλύτερος γνωστός πρώτος αριθμός βρέθηκε στις 25 Ιανουαρίου του 2013, στις 23:30:26 UTC. Είναι ο 257885161−1 και πρόκειται για τον 48ο αριθμό του Mersenne (βλ. και τελευταία εικασία στην ενότητα "Εκπληκτικές ιδιότητες, ατίθασα προβλήματα"). Συμβολίζεται M(57885161) , έχει 17425170 ψηφία και είναι ένας εξωφρενικά μεγάλος αριθμός. Υπολογίζεται, για παράδειγμα, ότι το πλήθος των ατόμων ολόκληρου του σύμπαντος εκφράζεται από έναν αριθμό με μόλις 80 περίπου ψηφία! Η ανακάλυψη του M(57885161) οφείλεται στον Curtis Cooper, καθηγητή στο Central Missouri State University. Ο καθηγητής είναι μέλος μιας συλλογικής, διαδικτυακής προσπάθειας ευρέσεως πρώτων αριθμών του Mersenne, γνωστής και ως GIMPS (Great Internet Mersenne Prime Search). Αν τώρα σας έπιασε μια ακαταμάχητη επιθυμία να βρείτε τον 49ο πρώτο του Mersenne, δεν έχετε παρά να πάτε μια βόλτα από το δικτυακό τόπο www.mersenne.org και να κατεβάσετε το σχετικό λογισμικό.

Πόσοι είναι;
Εκτός από τον έλεγχο ή τον εντοπισμό πρώτων, οι μαθηματικοί μερικές φορές επιθυμούν να γνωρίζουν απλά πόσοι είναι οι πρώτοι που βρίσκονται "κάτω" από ένα συγκεκριμένο φυσικό αριθμό. Πόσοι πρώτοι είναι μικρότεροι από το 1000; Πόσοι μικρότεροι από το 1000000; Πόσοι από το 10100 ; Όπως κάθε σώφρων άνθρωπος, έτσι και οι μαθηματικοί δεν θέλουν να δίνουν απάντηση σε τέτοια ερωτήματα, εντοπίζοντας τους πρώτους έναν προς έναν και μετρώντας τους. Αυτό που πραγματικά θέλουν είναι έναν τύπο, που θα του δίνουν έναν οποιονδήποτε αριθμό x κι εκείνος θα επιστρέφει το πλήθος των πρώτων που είναι μικρότεροι ή ίσοι του x . Εάν υπήρχε ένας τέτοιος μαγικός τύπος, τότε σίγουρα θα γλίτωνε από φοβερή δουλειά πολλούς ερευνητές. Όπως ίσως μαντέψατε, πράγματι υπάρχει αυτή η μαθηματική "συνταγή" και μάλιστα περιγράφεται από το Θεώρημα των Πρώτων Αριθμών (καθόλου πρωτότυπο όνομα, όμως δεν αφήνει το παραμικρό περιθώριο για παρερμηνείες). Εάν συμβολίσουμε με π(x) το πλήθος των πρώτων που είναι μικρότεροι από το x , τότε αποδεικνύεται ότι
π(x)≈xlnx
Ο Adrien-Marie Legendre ήταν ο πρώτος που υποψιάστηκε ότι ισχύει ο παραπάνω τύπος, το 1798. Περισσότερο από έναν αιώνα αργότερα, το 1896, οι Jacques Hadamard και de la Vallée Poussin απέδειξαν την ισχύ του, εργαζόμενοι ανεξάρτητα. Πριν δούμε με συγκεκριμένα παραδείγματα ότι ο τύπος πράγματι δουλεύει, οφείλουμε να κάνουμε μερικές παρατηρήσεις. Καταρχάς, το σύμβολο π εδώ δεν έχει καμία σχέση με τον γνωστό άρρητο αριθμό, που είναι ο λόγος της περιφέρειας ενός κύκλου προς τη διάμετρό του. Το δε σύμβολο ≈ σημαίνει "περίπου ίσο". Με απλά λόγια, δεν υπονοεί αυστηρή αλλά χαλαρή --ή προσεγγιστική, αν θέλετε-- ισότητα. Τέλος, το lnx είναι ο νεπέριος λογάριθμος του x . Πρόκειται για μια εξαιρετικά δημοφιλή συνάρτηση των μαθηματικών. Εάν δεν την έχετε συναντήσει ή δεν τη θυμόσαστε από τα Λυκειακά χρόνια, θα τη βρείτε σε αρκετά κομπιουτεράκια τσέπης: Αρκεί να δώσετε ένα θετικό αριθμό x , να πατήσετε το κουμπάκι " lnx " κι αμέσως θα σας επιστραφεί το αποτέλεσμα.
Το Θεώρημα των Πρώτων Αριθμών, λοιπόν, μας δίνει έναν προσεγγιστικό τύπο για το μέτρημα των πρώτων που είναι μικρότεροι από έναν δοσμένο αριθμό x . Σημειώστε ότι έως σήμερα δεν έχει βρεθεί ένας ακριβής τύπος για τον ίδιο σκοπό. Μολαταύτα, ο υπάρχων προσεγγιστικός τύπος δουλεύει με εκπληκτική (ποτέ όμως με απόλυτη) ακρίβεια, ιδιαίτερα για μεγάλες τιμές του x . Για παράδειγμα, αν x=1000 τότε π(1000)≈1000ln1000≈144,765 . Από τον πίνακα που παραθέσαμε προηγουμένως ή με τη βοήθεια ενός προγράμματος σαν το Mathematica, βλέπουμε ότι η ακριβής τιμή του π(x) είναι 168. Το λάθος που υπεισέρχεται από τον προσεγγιστικό τύπο είναι γύρω στο 13,8%. Για x=1000000 , η ακριβής τιμή του π(x) είναι 78498 και η προσεγγιστική 72382,4, γεγονός που μεταφράζεται σε ένα σφάλμα περίπου 7,8%. Για ακόμα μεγαλύτερη τιμή του x , ας πούμε 1000000000, το σφάλμα περιορίζεται στο 5,1%. Έχετε υπόψη, πάντως, ότι το σφάλμα είναι πάντοτε μεγαλύτερο από το 0, οσοδήποτε μεγάλη τιμή του x και αν πάρουμε: Ο τύπος για το π(x) είναι προσεγγιστικός κι αυτό ποτέ δεν αλλάζει!

Κατοπτρικοί πρώτοι
Ένας αριθμός ονομάζεται παλινδρομικός όταν παραμένει ίδιος ανεξάρτητα από τη φορά γραφής (αριστερά προς δεξιά ή δεξιά προς αριστερά). Παραδείγματα παλινδρομικών αριθμών αποτελούν οι 11, 121, 5005 κ.ά. Παρατηρήστε ότι η ιδιότητα της "παλινδρομικότητας" εξαρτάται από το σύστημα αρίθμησης! Για παράδειγμα, στο δεκαδικό σύστημα ο αριθμός 11 είναι παλινδρομικός αλλά στο δυαδικό γράφεται ως 1011, οπότε σ' αυτό δεν είναι. Για ένα δοσμένο σύστημα αρίθμησης, ένας αριθμός ονομάζεται παλινδρομικός πρώτος όταν είναι παλινδρομικός και ταυτόχρονα πρώτος (προφανώς, το εάν είναι πρώτος ή όχι δεν έχει να κάνει με το σύστημα αρίθμησης). Οι δεκαπέντε πρώτοι δεκαδικοί παλινδρομικοί πρώτοι, είναι οι 2, 3, 5, 7, 11, 101, 131, 151, 181, 191, 313, 353, 373, 383, 727. Ο μεγαλύτερος γνωστός παλινδρομικός πρώτος είναι ο 10130022+3761673⋅1065008+1 (μικροσκοπικός, συγκρινόμενος με τον μεγαλύτερο γνωστό πρώτο, τον 48ο πρώτο του Mersenne). Είναι άγνωστο αν υπάρχουν άπειροι δεκαδικοί παλινδρομικοί πρώτοι.

Αναπάντεχες συνδέσεις
Στον τύπο του Θεωρήματος των Πρώτων Αριθμών υπάρχει ένας κρυμμένος όρος που δεν γνωρίζουμε, ο οποίος βγαίνει στην επιφάνεια με τη μορφή ενός προσεγγιστικού σφάλματος. Για αρκετά μεγάλες τιμές του x το σφάλμα μικραίνει, ποτέ όμως δεν εξανεμίζεται. Για να είμαστε απόλυτα ειλικρινείς, οφείλουμε να πούμε ότι οι μαθηματικοί έχουν βρει τρόπο να περιγράψουν αναλυτικά αυτόν τον κρυμμένο όρο. Μόνο που στην προσπάθειά τους κατάφεραν να αποκαλύψουν ένα τεράστιο μυστήριο, η λύση του οποίου ταλαιπωρεί τα μεγαλύτερα ταλέντα των μαθηματικών για περισσότερο από ενάμιση αιώνα τώρα.
Στον κρυμμένο όρο που υπονοείται από τον τύπο π(x)≈xlnx , λοιπόν, εμπλέκονται όλες οι μη τετριμμένες ρίζες της λεγόμενης συνάρτησης ζήτα του Riemann. Εάν βρήκατε την προηγούμενη πρόταση αλλόκοτη, περιμένετε να δείτε τη συνέχεια. Η συνάρτηση ζήτα συμβολίζεται διεθνώς με το ελληνικό γράμμα ζ και ορίζεται πάνω στο σύνολο των μιγαδικών αριθμών ως εξής:
ζ(s)=∑∞k=01k−s
Οι μιγαδικοί αριθμοί είναι επέκταση των πραγματικών, ζουν πάνω σε ένα επίπεδο (οι πραγματικοί αρκούνται σε μια ευθεία), ενώ μια άπειρη κατηγορία εξ' αυτών, οι λεγόμενοι φανταστικοί, όταν υψώνονται στο τετράγωνο δίνουν έναν πραγματικό αριθμό που είναι μικρότερος από το μηδέν! Η γενική μορφή ενός οποιουδήποτε μιγαδικού είναι a+ı⋅b , όπου a , b είναι πραγματικοί αριθμοί και ı2=−1 (φανταστική μονάδα). Το a ονομάζεται πραγματικό μέρος, ενώ το b φανταστικό. Τώρα, κάθε μιγαδικός αριθμός s για τον οποίο ισχύει ζ(s)=0 , ονομάζεται ρίζα της συνάρτησης ζήτα. Υπάρχουν άπειροι αρνητικοί αριθμοί που μηδενίζουν τη συνάρτηση ζήτα (για την ακρίβεια, όλοι οι ζυγοί αρνητικοί). Επιπρόσθετα, υπάρχουν και άπειροι μιγαδικοί που επίσης τη μηδενίζουν. Μια μιγαδική ρίζα της συνάρτησης ζ ονομάζεται μη τετριμμένη. Τον Αύγουστο του 1859, σε ομιλία του στη Ακαδημία του Βερολίνου, ο 32χρονος τότε μαθηματικός Bernhard Riemann ισχυρίστηκε πως όλες οι μη τετριμμένες ρίζες της συνάρτησης ζήτα έχουν πραγματικό μέρος 12 (εικασία του Riemann). Έως σήμερα κανείς δεν έχει καταφέρει να αποδείξει αν η εικασία αληθεύει ή όχι. Όλες οι μη τετριμμένες ρίζες της ζ(s) , που έχουν βρεθεί με κοπιώδεις υπολογισμούς ή με τη βοήθεια υπολογιστών, έχουν όντως πραγματικό μέρος 12 . Ωστόσο, το γεγονός αυτό από μόνο του δεν αποτελεί απόδειξη. Ποιος μας λέει ότι η επόμενη μη τετριμμένη ρίζα που θα βρεθεί, δεν θα έχει πραγματικό μέρος διαφορετικό από 12 ; Μόνο μια γενική απόδειξη θα ξεκαθαρίσει τα πράγματα, αρκεί βέβαια να επινοηθεί.
Ώστε η κατανομή των πρώτων αριθμών εμπλέκει --κατά τρόπο αναπάντεχο ακόμα και για τους έμπειρους μαθηματικούς--, όλες τις μη τετριμμένες ρίζες της συνάρτησης ζήτα. Όμως η κατανομή των ριζών αυτών είναι επίσης άγνωστη. Έως σήμερα έχουμε ισχυρές ενδείξεις πως όλες τους έχουν πραγματικό μέρος 12 , ωστόσο δεν είμαστε ακόμα βέβαιοι. Τα προηγούμενα φαντάζουν αρκετά αφηρημένα κι ο πειρασμός να αγνοηθούν, ως ανούσια κατασκευάσματα της ζωηρής φαντασίας των μαθηματικών, είναι μεγάλος. Κι όμως, κατά ένα διαβολεμένο τρόπο οι πρώτοι αριθμοί και οι μη τετριμμένες ρίζες της συνάρτησης ζήτα ξαφνικά διεκδικούν φυσικό νόημα. Μελετώντας τη συμπεριφορά συστημάτων υποατομικών σωματιδίων του κβαντικού μικρόκοσμου, οι φυσικοί παίζουν με τις ιδιοτιμές τυχαίων ερμητιανών πινάκων (πρόκειται για εξαιρετικά χρήσιμα μαθηματικά εργαλεία που για λόγους χώρου αδυνατούμε να σας παρουσιάσουμε -- χώρια που κινδυνεύουμε από πετροβολισμό). Προς μεγάλη τους έκπληξη, φυσικοί και μαθηματικοί ανακάλυψαν ότι η κατανομή των ιδιοτιμών αυτών μοιάζει ύποπτα με την κατανομή των μη τετριμμένων ριζών της συνάρτησης ζήτα. Εστιάζοντας ξανά στους πρώτους αριθμούς, το φυσικό συμπέρασμα που προκύπτει είναι ότι οι μη κανονικότητες που παρατηρούνται στην κατανομή τους προέρχονται από τυχαίο θόρυβο.
Στο μεταξύ, οι μαθηματικοί επιχειρούν να αποδείξουν την αλήθεια ή το ψεύδος της εικασίας του Riemann. Θα αλλάξει κάτι στη ζωή μας αν τα καταφέρουν; Ίσως ναι, ίσως όχι. Θα προκύψουν πρακτικές εφαρμογές; Ίσως ναι, ίσως όχι. Έχει νόημα η καθαρή μαθηματική αναζήτηση, χωρίς να υπάρχει ένας ξεκάθαρος πρακτικός στόχος; Σίγουρα ναι! Αρκεί να έχετε υπόψη πως η κατασκευή των υπολογιστών βασίζεται, εν πολλοίς, σε καθαρά θεωρητικές εργασίες των Kurt Goedel και Alan Turing. Οποιαδήποτε άποψη επιτάσσει --ή έστω υπονοεί-- την εξάσκηση μόνο "χρήσιμης έρευνας", είναι στην καλύτερη περίπτωση γελοία και στη χειρότερη επικίνδυνη.