Πρώτος αριθμός

Ιστορία

Υπάρχουν ενδείξεις σε διασωθείσες επιγραφές των αρχαίων Αιγυπτίων ότι είχαν κάποια γνώση πρώτων αριθμών: οι επεκτάσεις του αιγυπτιακού κλάσματος στον πάπυρο του Ριντ, για παράδειγμα, έχουν αρκετά διαφορετικούς τύπους για πρώτους και για σύνθετους αριθμούς. Ωστόσο, οι πιο πρώιμες διασωθείσες επιγραφές σαφούς μελέτης των πρώτων αριθμών προέρχονται από τους αρχαίους Έλληνες. Τα στοιχεία του Ευκλείδη (περίπου στο 300 π.Χ.) περιέχουν σημαντικά θεωρήματα για τους πρώτους αριθμούς, συμπεριλαμβανομένων της απειρίας των πρώτων αριθμών και του θεμελιώδους θεωρήματος της αριθμητικής. Ο Ευκλείδης επίσης απέδειξε πώς μπορούμε να κατασκευάσουμε έναν τέλειο αριθμό από ένα πρώτο Μερσέν αριθμό. Το κόσκινο του Ερατοσθένη, το οποίο αποδίδεται στον Ερατοσθένη, είναι μια απλή μέθοδος να υπολογίσουμε τους πρώτους, παρόλο που οι μεγάλοι πρώτοι δεν υπολογίζονται σήμερα με τους υπολογιστές με αυτό τον τρόπο.
Μετά τους Έλληνες, λίγα πράγματα συνέβησαν με την έρευνα των πρώτων αριθμών μέχρι τον 17ο αιώνα. Το 1640 ο Πιέρ ντε Φερμά διατύπωσε (χωρίς απόδειξη) το μικρό θεώρημα του Φερμά (αργότερα αποδείχθηκε από τους Λάιμπνιτς και  Όιλερ). Ο Φερμά υπέθεσε ότι όλοι οι αριθμοί της μορφής 2²ⁿ + 1 είναι πρώτοι (αυτοί οι αριθμοί ονομάζονται αριθμοί Φερμά) και το επαλήθευσε αυτό μέχρι και για n = 4 (ή 2¹⁶ + 1). Αλλά ο αμέσως επόμενος αριθμός Φερμά 2³² + 1 είναι σύνθετος (ένας από τους παράγοντες του που είναι πρώτος αριθμός είναι ο 641), όπως ανακάλυψε αργότερα ο Euler και μάλιστα δεν υπάρχουν παραπάνω γνωστοί αριθμοί Φερμά, οι οποίοι είναι πρώτοι. Ο Γάλλος καλόγερος Μερσέν μελέτησε τους πρώτους αριθμούς της μορφής 2ᵖ - 1, όπου p είναι πρώτος. Αυτοί οι αριθμοί ονομάζονται πρώτοι αριθμοί Μερσέν προς τιμή του. 
Το έργο του Όιλερ στη θεωρία αριθμών περιλαμβάνει πολλά συμπεράσματα για τους πρώτους αριθμούς. Ο Όιλερ απέδειξε ότι η άπειρη σειρά 1/2 + 1/3 + 1/5 + 1/7 + 1/11 + ... αποκλίνει. Το 1747 έδειξε ότι οι άρτιοι τέλειοι αριθμοί είναι ακριβώς οι ακέραιοι της μορφής 2ᵖ⁻¹(2ᵖ − 1), όπου ο δεύτερος παράγοντας είναι ένας πρώτος Μερσέν αριθμός. 
Στις αρχές του 19ου αιώνα, οι Λεγκράντ και Γκάους ανεξάρτητα υπέθεσαν ότι καθώς το x τείνει στο άπειρο, το πλήθος των πρώτων αριθμών μέχρι και το x είναι ασύμπτωτο στο κλάσμα x/ln(x), όπου ln(x) είναι ο φυσικός λογάριθμος του x. Στις ιδέες του ο Ρίμαν για τη συνάρτηση ζήτα, τις οποίες εξέδωσε το 1859, σχεδίαζε ένα πρόγραμμα που θα οδηγούσε σε μια απόδειξη του θεωρήματος των πρώτων αριθμών. Αυτό το περίγραμμα ολοκληρώθηκε από τους Χάνταμαρντ και ντε λα Βαλέ Ποσίν, οι οποίοι ανεξάρτητα απέδειξαν το θεώρημα των πρώτων αριθμών το 1896. 
Δε γίνεται να αποδείξουμε ότι ένας μεγάλος αριθμός είναι πρώτος με τη δοκιμαστική διαίρεση. Πολλοί μαθηματικοί έχουν εργαστεί στην εύρεση τεχνικών για να αποδειχτεί αν ένας μεγάλος αριθμός είναι πρώτος, αλλά συχνά αυτές οι τεχνικές περιορίζονται σε συγκεκριμένες μορφές αριθμών. Παραδείγματα τέτοιων τεχνικών είναι το τεστ του Πέπιν για τους αριθμούς Φερμά (1877), το θεώρημα του Προθ (γύρω στο 1878), το τεστ των Λούκας-Λέμερ (1856) και το γενικευμένο τεστ πρώτων αριθμών του Λούκας. Πιο πρόσφατοι αλγόριθμοι, όπως οι APRT-CL, ECPP και AKS δουλεύουν για όλους τους αριθμούς, αλλά παραμένουν πολύ πιο αργοί.   
Για ένα μεγάλο χρονικό διάστημα, οι πρώτοι αριθμοί θεωρούνταν ότι είχαν εξαιρετικά περιορισμένη εφαρμογή έξω από τα καθαρά μαθηματικά: αυτό άλλαξε τη δεκαετία του 1970, όταν οι έννοιες της κρυπτογραφίας δημοσίου κλειδιού ανακαλύφθηκαν, στην οποία κρυπτογράφηση δημόσιου κλειδιού οι πρώτοι αριθμοί αποτελούσαν τη βάση των πρώτων αλγορίθμων, όπως τον κρυπτογραφικό αλγόριθμο RSA. 
Από το 1951 όλοι οι μεγαλύτεροι πρώτοι αριθμοί έχουν βρεθεί από τους ηλεκτρονικούς υπολογιστές. Η έρευνα για όλο και μεγαλύτερους πρώτους αριθμούς έχει προκαλέσει ενδιαφέρον και έξω από τους μαθηματικούς κύκλους. Η μεγάλη διαδικτυακή έρευνα πρώτων Μερσέν αριθμών και άλλες εργασίες σε παράλληλα και κατανεμημένα συστήματα πληροφορικής για την εύρεση μεγάλων πρώτων αριθμών έχουν γίνει διάσημες τα τελευταία δέκα με δεκαπέντε χρόνια, ενώ οι μαθηματικοί συνεχίζουν να παλεύουν με τη θεωρία των πρώτων αριθμών.

Εύρεση πρώτων

Η εύρεση των πρώτων αριθμών απασχόλησε από την αρχαιότητα τους μαθηματικούς. Ένας από τους πιο απλούς αλλά και αργούς τρόπους για (μαζική) εύρεση πολλών πρώτων είναι το λεγόμενο κόσκινο του Ερατοσθένη: Στο σύνολο των φυσικών αριθμών - πρακτικά έως κάποιο μεγάλο αριθμό Ν - αρχίζουμε και αποκλείουμε πρώτα τα πολλαπλάσια του 2 μετά τα πολλαπλάσια του επόμενου μη διαγραμμένου αριθμού κ.ο.κ. έως το Ν. Παρατηρούμε ότι όλο και λιγότερους αριθμούς θα βρίσκουμε προς διαγραφή. Οι αριθμοί που θα απομείνουν είναι όλοι πρώτοι.
Το κόσκινο του Ερατοσθένη είναι ένας αργός αλγόριθμος για το αν ένας συγκεκριμένος αριθμός Ν είναι πρώτος ή όχι, διότι μεταξύ άλλων απαιτεί ουσιαστικά και την εύρεση όλων των πρώτων μικρότερων ίσων του  (αν ένας αριθμός Ν δεν έχει διαιρέτες μικρότερους ίσους του , τότε είναι πρώτος).
Στις 14 Φεβρουαρίου 1999 οι Γιούρι Ματιγιάσεβιτς και Μπόρις Στέκιν δημοσίευσαν στο διαδίκτυο το οπτικό κόσκινο των πρώτων αριθμών. Τα σημεία της παραβολής  με ακέραιες συντεταγμένες ορίζουν χορδές που τέμνουν τον οριζόντιο άξονα x΄x σε σημεία της μορφής (αβ,0) όπου α,β ακέραιοι κι επομένως σαρώνουν όλους τους σύνθετους θετικούς ακέραιους.

Αλγόριθμοι εύρεσης πρώτων

Παρατίθενται μερικοί αλγόριθμοι (κατά σειρά ταχύτητας ή και απλότητας) για την εύρεση αν ο Ν>=2 είναι πρώτος. Η σειρά επίσης αυτών των αλγορίθμων είναι παιδευτική για την εισαγωγή σε μια σειρά από προγράμματα για ηλεκτρονικούς υπολογιστές.

Απλός 2

Βασιζόμενοι στην παρατήρηση ότι κανένας αριθμός Ν δεν έχει διαιρέτη μεγαλύτερο του Ν/2, τροποποιούμε τον παραπάνω αλγόριθμο εξετάζοντας όλους τους αριθμούς Μ < Ν/2, διπλασιάζοντας έτσι την ταχύτητα σε σχέση με τον "Απλό 1".

Απλός 3

Παρατηρούμε ότι αν ένας αριθμός Ν δεν είναι πρώτος τότε έχει (τουλάχιστον) δύο διαιρέτες μεγαλύτερους από 1. Σε αυτήν την περίπτωση τουλάχιστον ένας διαιρέτης είναι μικρότερος από την τετραγωνική ρίζα του αριθμού. Τροποποιούμε τον αλγόριθμο 2 εξετάζοντας όλους τους αριθμούς Μ που είναι μικρότεροι από την τετραγωνική ρίζα του N, αν η τελευταία δεν είναι ακέραιος. Αλλιώς ο αριθμός δεν είναι πρώτος, επειδή τον διαιρεί και η τετραγωνική του ρίζα.

Στις τέχνες και τη λογοτεχνία

Οι πρώτοι αριθμοί έχουν επηρεάσει πολλούς καλλιτέχνες και συγγραφείς. Ο Γάλλος συνθέτης Ολιβιέρ Μεσσιάν χρησιμοποίησε τους πρώτους αριθμούς για να δημιουργήσει αμετρική μουσική μέσω φυσικών φαινομένων. Σε έργα, όπως Λα Νατιβίτ ντου Σενό (1935) και Κουάτρ ετούντ ντε ριμ (1949–50), ο συνθέτης χρησιμοποιεί ταυτόχρονα μοτίβα με μήκη που δίνονται από διαφορετικούς πρώτους αριθμούς για να δημιουργήσει απρόβλεπτους ρυθμούς: οι πρώτοι αριθμοί 41, 43, 47 και 53 εμφανίζονταi στο έργο "Neumes rythmiques". Σύμφωνα με τον Μεσσιάν, αυτός ο τρόπος σύνθεσης ήταν εμπνευσμένος από τις κινήσεις της φύσης, τις κινήσεις της ελεύθερης και άνισης διάρκειας. 
Στο επιστημονικής φαντασίας μυθιστόρημά του Contact, ο επιστήμονας της NASA Καρλ Σάγκαν αναφέρει ότι οι πρώτοι αριθμοί μπορούν να χρησιμοποιηθούν ως ένα μέσο επικοινωνίας με τους εξωγήινους, μια ιδέα που πρώτα ανέπτυξε ανεπίσημα με τον Αμερικανό αστρονόμο Φρανκ Ντράκε το 1975. Στο μυθιστόρημά του  The Curious Incident of the Dog in the Night-Time ο Μαρκ Χάντον, ο αφηγητής οργανώνει τα τμήματα της ιστορίας από διαδοχικούς πρώτους αριθμούς. 
Πολλές ταινίες, όπως Cube, Sneakers, The Mirror Has Two Faces και A Beautiful Mind αντικατοπτρίζουν μια δημοφιλή γοητεία των πρώτων αριθμών και της κρυπτογραφίας. Οι πρώτοι αριθμοί χρησιμοποιούνται ως αλληγορία για τη μοναξιά και την απομόνωση στο μυθιστόρημα του The Solitude of Prime Numbers του Paolo Giordano, στο οποίο οι πρώτοι αριθμοί παρουσιάζονται ως ξένοι μεταξύ των ακεραίων αριθμών.