cyanic-selkie/wikianc huggingface dataset:
Πρώτος αριθμός
Θεμελιώδες θεώρημα της αριθμητικής
Αν p είναι ένας πρώτος αριθμός και ο p διαιρεί ένα γινόμενο αb, όπου α, b είναι ακέραιοι, τότε ισχύει ότι ο p διαιρεί τον α ή ο p διαιρεί τον b. Αυτή η πρόταση είναι γνωστή ως το λήμμα του Ευκλείδη. Το λήμμα του Ευκλείδη χρησιμοποιείται σε μερικές αποδείξεις για να αποδειχθεί η μοναδικότητα της παραγοντοποίησης ενός αριθμού σε πρώτους παράγοντες.
Οι αρχαίοι Έλληνες δε θεωρούσαν τον 1 ούτε ως αριθμό κι έτσι δε τον θεωρούσαν ούτε ως πρώτο. Ωστόσο, στο 19ο αιώνα πολλοί μαθηματικοί θεωρούσαν τον 1 ως πρώτο αριθμό. Για παράδειγμα, η λίστα του Ντέρικ Νόρμαν Λέμερ που περιείχε πρώτους αριθμούς ως το 10,006,721 και εκδόθηκε μέχρι και το 1956, άρχιζε με τον 1 ως πρώτο αριθμό. Λέγεται ότι ο Ανρί Λεμπέσγκ είναι ο τελευταίος επαγγελματίας μαθηματικός που θεωρεί τον 1 ως πρώτο αριθμό. Παρόλο που ένα μεγάλο τμήμα των μαθηματικών είναι σωστό με τη θεωρία του 1 ως πρώτου αριθμού, το παραπάνω θεμελιώδες θεώρημα της αριθμητικής δε στέκει όπως είναι διατυπωμένο. Για παράδειγμα, ο αριθμός 15 μπορεί να παραγοντοποιηθεί ως 3 · 5 ή 1 · 3 · 5. Αν ο 1 ήταν πρώτος, τότε αυτές οι δύο εκφράσεις θα παρίσταναν διαφορετικές παραγοντοποιήσεις του 15 σε πρώτους αριθμούς κι έτσι το θεώρημα θα έπρεπε να τροποποιηθεί. Επιπρόσθετα, οι πρώτοι αριθμοί έχουν αρκετές ιδιότητες, τις οποίες ο αριθμός 1 δεν έχει, όπως τη σχέση του αριθμού με την αντίστοιχη τιμή του στη συνάρτηση του Όιλερ ή στη συνάρτηση του αθροίσματος των διαιρετών.
Ιστορία
Υπάρχουν ενδείξεις σε διασωθείσες επιγραφές των αρχαίων Αιγυπτίων ότι είχαν κάποια γνώση πρώτων αριθμών: οι επεκτάσεις του αιγυπτιακού κλάσματος στον πάπυρο του Ριντ, για παράδειγμα, έχουν αρκετά διαφορετικούς τύπους για πρώτους και για σύνθετους αριθμούς. Ωστόσο, οι πιο πρώιμες διασωθείσες επιγραφές σαφούς μελέτης των πρώτων αριθμών προέρχονται από τους αρχαίους Έλληνες. Τα στοιχεία του Ευκλείδη (περίπου στο 300 π.Χ.) περιέχουν σημαντικά θεωρήματα για τους πρώτους αριθμούς, συμπεριλαμβανομένων της απειρίας των πρώτων αριθμών και του θεμελιώδους θεωρήματος της αριθμητικής. Ο Ευκλείδης επίσης απέδειξε πώς μπορούμε να κατασκευάσουμε έναν τέλειο αριθμό από ένα πρώτο Μερσέν αριθμό. Το κόσκινο του Ερατοσθένη, το οποίο αποδίδεται στον Ερατοσθένη, είναι μια απλή μέθοδος να υπολογίσουμε τους πρώτους, παρόλο που οι μεγάλοι πρώτοι δεν υπολογίζονται σήμερα με τους υπολογιστές με αυτό τον τρόπο.
Μετά τους Έλληνες, λίγα πράγματα συνέβησαν με την έρευνα των πρώτων αριθμών μέχρι τον 17ο αιώνα. Το 1640 ο Πιέρ ντε Φερμά διατύπωσε (χωρίς απόδειξη) το μικρό θεώρημα του Φερμά (αργότερα αποδείχθηκε από τους Λάιμπνιτς και Όιλερ). Ο Φερμά υπέθεσε ότι όλοι οι αριθμοί της μορφής 22 n + 1 είναι πρώτοι (αυτοί οι αριθμοί ονομάζονται αριθμοί Φερμά) και το επαλήθευσε αυτό μέχρι και για n = 4 (ή 216 + 1). Αλλά ο αμέσως επόμενος αριθμός Φερμά 232 + 1 είναι σύνθετος (ένας από τους παράγοντες του που είναι πρώτος αριθμός είναι ο 641), όπως ανακάλυψε αργότερα ο Euler και μάλιστα δεν υπάρχουν παραπάνω γνωστοί αριθμοί Φερμά, οι οποίοι είναι πρώτοι. Ο Γάλλος καλόγερος Μερσέν μελέτησε τους πρώτους αριθμούς της μορφής 2p - 1, όπου p είναι πρώτος. Αυτοί οι αριθμοί ονομάζονται πρώτοι αριθμοί Μερσέν προς τιμή του.
Το έργο του Όιλερ στη θεωρία αριθμών περιλαμβάνει πολλά συμπεράσματα για τους πρώτους αριθμούς. Ο Όιλερ απέδειξε ότι η άπειρη σειρά 1/2 + 1/3 + 1/5 + 1/7 + 1/11 + ... αποκλίνει. Το 1747 έδειξε ότι οι άρτιοι τέλειοι αριθμοί είναι ακριβώς οι ακέραιοι της μορφής 2p-1(2p − 1), όπου ο δεύτερος παράγοντας είναι ένας πρώτος Μερσέν αριθμός.
Στις αρχές του 19ου αιώνα, οι Λεγκράντ και Γκάους ανεξάρτητα υπέθεσαν ότι καθώς το x τείνει στο άπειρο, το πλήθος των πρώτων αριθμών μέχρι και το x είναι ασύμπτωτο στο κλάσμα x/ln(x), όπου ln(x) είναι ο φυσικός λογάριθμος του x. Στις ιδέες του ο Ρίμαν για τη συνάρτηση ζήτα, τις οποίες εξέδωσε το 1859, σχεδίαζε ένα πρόγραμμα που θα οδηγούσε σε μια απόδειξη του θεωρήματος των πρώτων αριθμών. Αυτό το περίγραμμα ολοκληρώθηκε από τους Χάνταμαρντ και ντε λα Βαλέ Ποσίν, οι οποίοι ανεξάρτητα απέδειξαν το θεώρημα των πρώτων αριθμών το 1896.
Δε γίνεται να αποδείξουμε ότι ένας μεγάλος αριθμός είναι πρώτος με τη δοκιμαστική διαίρεση. Πολλοί μαθηματικοί έχουν εργαστεί στην εύρεση τεχνικών για να αποδειχτεί αν ένας μεγάλος αριθμός είναι πρώτος, αλλά συχνά αυτές οι τεχνικές περιορίζονται σε συγκεκριμένες μορφές αριθμών. Παραδείγματα τέτοιων τεχνικών είναι το τεστ του Πέπιν για τους αριθμούς Φερμά (1877), το θεώρημα του Προθ (γύρω στο 1878), το τεστ των Λούκας-Λέμερ (1856) και το γενικευμένο τεστ πρώτων αριθμών του Λούκας. Πιο πρόσφατοι αλγόριθμοι, όπως οι APRT-CL, ECPP και AKS δουλεύουν για όλους τους αριθμούς, αλλά παραμένουν πολύ πιο αργοί.
Για ένα μεγάλο χρονικό διάστημα, οι πρώτοι αριθμοί θεωρούνταν ότι είχαν εξαιρετικά περιορισμένη εφαρμογή έξω από τα καθαρά μαθηματικά: αυτό άλλαξε τη δεκαετία του 1970, όταν οι έννοιες της κρυπτογραφίας δημοσίου κλειδιού ανακαλύφθηκαν, στην οποία κρυπτογράφηση δημόσιου κλειδιού οι πρώτοι αριθμοί αποτελούσαν τη βάση των πρώτων αλγορίθμων, όπως τον κρυπτογραφικό αλγόριθμο RSA.
Από το 1951 όλοι οι μεγαλύτεροι πρώτοι αριθμοί έχουν βρεθεί από τους ηλεκτρονικούς υπολογιστές. Η έρευνα για όλο και μεγαλύτερους πρώτους αριθμούς έχει προκαλέσει ενδιαφέρον και έξω από τους μαθηματικούς κύκλους. Η μεγάλη διαδικτυακή έρευνα πρώτων Μερσέν αριθμών και άλλες εργασίες σε παράλληλα και κατανεμημένα συστήματα πληροφορικής για την εύρεση μεγάλων πρώτων αριθμών έχουν γίνει διάσημες τα τελευταία δέκα με δεκαπέντε χρόνια, ενώ οι μαθηματικοί συνεχίζουν να παλεύουν με τη θεωρία των πρώτων αριθμών.
Πλήθος πρώτων αριθμών
Υπάρχουν άπειροι το πλήθος πρώτοι αριθμοί. Ένας άλλος τρόπος για να πούμε το ίδιο είναι ότι η ακολουθία
2, 3, 5, 7, 11, 13, ...
των πρώτων αριθμών δεν τελειώνει ποτέ. Αυτή η πρόταση ονομάζεται θεώρημα του Ευκλείδη προς τιμή του αρχαίου Έλληνα μαθηματικού Ευκλείδη, αφού η πρώτη γνωστή απόδειξη για αυτή την πρόταση αποδίδεται σε αυτόν. Πολλές περισσότερες αποδείξεις της απειρίας των πρώτων αριθμών είναι γνωστές, όπως μια αναλυτική απόδειξη από τον Όιλερ, η απόδειξη του Γκόλντμπαχ βασισμένη στους αριθμούς Φερμά, η απόδειξη του Φούρστενμπεργκ χρησιμοποιώντας γενική τοπολογία και η κομψή απόδειξη του Κούμερ.
Έστω ένα πεπερασμένο σύνολο S πρώτων αριθμών. Η ιδέα - κλειδί είναι να θεωρήσουμε το γινόμενο όλων αυτών των αριθμών συν ένα:
Όπως κάθε άλλος φυσικός αριθμός, ο Ν μπορεί να διαιρεθεί από τουλάχιστον ένα πρώτο αριθμό (είναι πιθανό ο Ν να είναι πρώτος).
Κανένας από τους πρώτους αριθμούς οι οποίοι διαιρούν τον Ν δεν μπορεί να είναι στοιχείο του πεπερασμένου συνόλου S των πρώτων αριθμών με το οποίο ξεκινήσαμε, επειδή διαιρώντας τον Ν με οποιοδήποτε από αυτούς τους πρώτους αριθμούς αφήνει υπόλοιπο 1. Επομένως, οι πρώτοι από τους οποίους ο Ν διαιρείται είναι επιπλέον πρώτοι εκτός από αυτόν με τον οποίο ξεκινήσαμε. Έτσι κάθε πεπερασμένο σύνολο πρώτων αριθμών μπορεί να επεκταθεί σε ένα μεγαλύτερο πεπερασμένο σύνολο πρώτων αριθμών.
Συχνά αναφέρεται εσφαλμένα ότι ο Ευκλείδης ξεκινάει με την υπόθεση ότι αρχικά το σύνολο που θεωρούμε περιέχει όλους τους πρώτους αριθμούς, καταλήγοντας σε μια αντίφαση ή ότι το σύνολο περιέχει ακριβώς τους n μικρότερους πρώτους αριθμούς και όχι κάθε πεπερασμένο σύνολο πρώτων αριθμών. Σήμερα, το γινόμενο των μικρότερων n πρώτων αριθμών συν ένα συμβατικά ονομάζεται ο n-οστός αριθμός του Ευκλείδη.
Αυτό το άθροισμα γίνεται μεγαλύτερο από κάθε πραγματικό αριθμό με την προϋπόθεση ότι ο p είναι αρκετά μεγάλος. Αυτό δείχνει ότι υπάρχουν απείρως πολλοί πρώτοι αριθμοί, αφού ειδάλλως αυτό το άθροισμα θα μεγάλωνε μόνο μέχρι να φτάσουμε στο μεγαλύτερο πρώτο αριθμό p. Η αύξηση του S(p) υπολογίζεται από το δεύτερο θεώρημα του Μερσέν. Σε σύγκριση με το παραπάνω άθροισμα, παρατηρούμε ότι το άθροισμα
δεν τείνει στο άπειρο, καθώς το n τείνει στο άπειρο. Με αυτή την έννοια, οι πρώτοι αριθμοί εμφανίζονται πιο συχνά από τα τετράγωνα των φυσικών αριθμών. Το θεώρημα του Μπραν αναφέρει ότι το άθροισμα των αντίστροφων δύο διδύμων πρώτων αριθμών,
είναι πεπερασμένο.
Αναγνώριση πρώτου αριθμού και παραγοντοποίηση ακεραίου
Υπάρχουν ποικίλες μέθοδοι για να προσδιορίσουμε αν ένας αριθμός n είναι πρώτος. Η πιο βασική μέθοδος, η δοκιμαστική διαίρεση, έχει μικρή πρακτική χρησιμότητα επειδή είναι αργή. Ένα τμήμα των σύγχρονων μεθόδων για τον προσδιορισμό αν ένας αριθμός είναι πρώτος είναι εφαρμόσιμο για όλους τους αριθμούς, ενώ οι πιο αποτελεσματικές μέθοδοι είναι διαθέσιμες μόνο για συγκεκριμένες κατηγορίες αριθμών. Οι περισσότερες από αυτές τις μεθόδους λένε μόνο αν ο αριθμός είναι πρώτος ή όχι. Οι μέθοδοι, οι οποίες επιπλέον βρίσκουν και έναν ή περισσότερους παράγοντες του υπό εξέταση αριθμού ονομάζονται αλγόριθμοι παραγοντοποίησης.
Η πιο βασική μέθοδος ελέγχου αν ένας ακέραιος αριθμός είναι πρώτος ονομάζεται δοκιμαστική διαίρεση. Αυτή η μέθοδος συνίσταται στη διαίρεση του n από κάθε ακέραιο m, ο οποίος είναι του 1 και μικρότερος ή ίσος της τετραγωνικής ρίζας του n. Αν το αποτέλεσμα οποιασδήποτε από αυτές τις διαιρέσεις είναι ακέραιος, τότε ο n δεν είναι πρώτος, ειδάλλως είναι πρώτος αριθμός. Πράγματι, αν n = αb είναι σύνθετος (με α και b ≠ 1), τότε ένας από τους παράγοντες α ή b απαραίτητα το πολύ ίσος με \sqrt{n}. Για παράδειγμα, για n = 37 οι δοκιμαστικές διαιρέσεις είναι από τους m = 2, 3, 4, 5 και 6. Κανένας από αυτούς τους αριθμούς δε διαιρεί το 37, οπότε ο 37 είναι πρώτος. Αυτός ο τρόπος μπορεί να εφαρμοστεί πιο αποτελεσματικά αν μια ολοκληρωμένη λίστα πρώτων αριθμών μέχρι και \sqrt{n} είναι γνωστή - μετά οι δοκιμαστικές διαιρέσεις χρειάζεται να γίνουν μόνο για εκείνους τους m που είναι πρώτοι. Για παράδειγμα, για να ελέγξουμε αν ο 37 είναι πρώτος, μόνο τρεις διαιρέσεις είναι απαραίτητες (m = 2, 3 και 5), αφού οι αριθμοί 4 και 6 είναι σύνθετοι.
Η απλή μέθοδος της δοκιμαστικής διαίρεσης γρήγορα γίνεται μη πρακτική για τον έλεγχο μεγάλων ακεραίων επειδή το πλήθος των πιθανών παραγόντων μεγαλώνει ραγδαία καθώς ο n αυξάνεται. Σύμφωνα με το θεώρημα των πρώτων αριθμών, το οποίο αναλύεται παρακάτω, το πλήθος των πρώτων αριθμών μικρότερων του \sqrt{n} είναι της τάξης. Για τον μικρότερο πρώτο μεγαλύτερο του 1020, το πλήθος των πρώτων που πρέπει να δοκιμαστούν είναι περίπου 455 εκατομμύρια. Πάρα πολλοί από αυτούς δεν χωράνε σε 32bit (1010 > 4*109 ≈ 232), αλλά ακόμα και αν χωρούσαν θα χρειαζόταν περίπου 4*455 = 910 εκατομμύρια bytes για την αποθήκευσή τους. Εναλλακτικά, χωρίς αποθήκευση πρώτων αριθμών, χρειάζονται περίπου 10 δισεκατομμύρια διαιρέσεις.
Ένας αλγόριθμος, ο οποίος αποδίδει όλους τους πρώτους αριθμούς μέχρι ένα δοθέν όριο, όπως απαιτείται στη μέθοδο της δοκιμαστικής διαίρεσης, ονομάζεται κόσκινο πρώτων αριθμών. Το αρχαιότερο παράδειγμα, το κόσκινο του Ερατοσθένη είναι χρήσιμο για σχετικά μικρούς πρώτους αριθμούς. Το σύγχρονο κόσκινο του Άτκιν είναι πιο περίπλοκο, αλλά πιο γρήγορο, όταν βελτιστοποιείται κατάλληλα. Πριν την ανακάλυψη των υπολογιστών, χρησιμοποιούνταν επίσης κατάλογοι πρώτων αριθμών με όρια μέχρι και 107.
Οι σύγχρονοι έλεγχοι για τους πρώτους αριθμούς διαιρούνται σε δύο κατηγορίες, τους πιθανοτικούς (ή Μόντε Κάρλο) και τους αιτιοκρατικούς (ντετερμινιστικούς) αλγορίθμους. Ο έλεγχος του Φερμά για τους πρώτους αριθμούς βασίζεται στο μικρό θεώρημα του Φερμά. Το θεώρημα αυτό λέει ότι για κάθε πρώτο αριθμό p και για κάθε ακέραιο α, ο οποίος δε διαιρείται από τον p, ο αριθμός ap − 1 − 1 διαιρείται από τον p. Έτσι, αν ο αριθμός an − 1 − 1 δε διαιρείται από τον n, τότε ο n δεν μπορεί να είναι πρώτος. Ωστόσο, το αντίστροφο δεν ισχύει. Οι σύνθετοι αριθμοί που περνάνε τον έλεγχο του Φερμά για κάποιο α, ονομάζονται ψευδοπρώτοι στη βάση α. Μάλιστα, υπάρχουν άπειροι σύνθετοι αριθμοί n, οι οποίοι περνούν τον έλεγχου του Φερμά για κάθε α σχετικά πρώτο με τον n (αριθμοί Καρμάικλ). Ο δημοφιλής αλγόριθμος Miller-Rabin χρησιμοποιεί μια παραλλαγή του ελέγχου του Φερμά και ελέγχοντας ένα πλήθος από τυχαία α, εγγυάται ότι ένας αριθμός που περνάει τον έλεγχο για κάθε α είναι πρώτος με μεγάλη στατιστική βεβαιότητα. Η στατιστική βεβαιότητα είναι ανάλογη του πλήθους των τυχαίων α που χρησιμοποιεί ο αλγόριθμος.
Οι αιτιοκρατικοί (ντετερμινιστικοί) αλγόριθμοι αναγνωρίζουν έναν αριθμό ως πρώτο αν και μόνον αν είναι πρώτος. Για πρακτικά μεγέθη, ο ποιο γρήγορος αλγόριθμος αυτής της κατηγορίας χρησιμοποιεί την απόδειξη της ελλειπτικής καμπύλης (ECPP) για να αναγνωρίσει ένα αριθμό ως πρώτο. Η χρονική πολυπλοκότητα του αλγορίθμου αυτού είναι κατά μέσον όρο πολυωνυμική, αλλά δεν είναι γνωστό αν αυτό συμβαίνει και στη χειρότερη περίπτωση. Ο αλγόριθμος AKS είναι μεγάλης θεωρητικής σημασίας καθώς αποδεικνύει ότι το πρόβλημα της αναγνώρισης πρώτου αριθμού έχει πολυωνυμική χρονική πολυπλοκότητα στη χειρότερη περίπτωση. Είναι όμως κατά πολύ αργότερος από τον ECCP για πρακτικά μεγέθη. Οι αιτιοκρατικές μέθοδοι είναι τυπικά πιο αργές από τις πιθανοτικές κι έτσι οι τελευταίες εφαρμόζονται πρώτες πριν χρησιμοποιηθούν οι πιο χρονοβόρες αιτιοκρατικές μέθοδοι.
Εκτός από τις παραπάνω δοκιμές για τους πρώτους αριθμούς για κάθε φυσικό αριθμό n, ένα πλήθος πολύ περισσότερο αποτελεσματικών μεθόδων για πρώτους αριθμούς είναι διαθέσιμο για συγκεκριμένους αριθμούς. Για παράδειγμα, για να εκτελεστεί η μέθοδος του Lucas για τους πρώτους απαιτείται η γνώση των παραγόντων που είναι πρώτοι αριθμοί του αριθμού n - 1, ενώ η μέθοδος των Λούκας-Λέμερ για τους πρώτους αριθμούς απαιτεί τους παράγοντες που είναι πρώτοι αριθμοί του αριθμού n + 1 ως δεδομένο. Για παράδειγμα, αυτές οι μέθοδοι μπορούν να εφαρμοστούν για να ελέγξουμε αν οι αριθμοί
n! ± 1 = 1 · 2 · 3 · ... · n ± 1
είναι πρώτοι. Οι πρώτοι αριθμοί αυτής της μορφής είναι γνωστοί ως παραγοντικοί πρώτοι αριθμοί. Άλλοι πρώτοι αριθμοί, όπου είτε ο p + 1 ή ο p - 1 είναι μιας συγκεκριμένης μορφής περιλαμβάνουν τους πρώτους αριθμούς Σόφι Ζερμέν (πρώτοι αριθμοί της μορφής 2p + 1, όπου p είναι πρώτος), τους αρχέγονους πρώτους αριθμούς, τους πρώτους αριθμούς του Φερμά και τους πρώτους αριθμούς του Μερσέν, οι οποίοι είναι πρώτοι αριθμοί της μορφής 2p - 1, όπου p είναι ένας τυχαίος πρώτος αριθμός. Η μέθοδος των Λούκας-Λέμερ είναι εξαιρετικά γρήγορη για τους πρώτους αριθμούς της μορφής αυτής. Για το λόγο αυτό ο γνωστός πρώτος αριθμός έχει γίνει σχεδόν ένας πρώτος Μερσέν από τότε που ανακαλύφθηκαν οι υπολογιστές.
Οι πρώτοι αριθμοί Φερμά είναι της μορφής
n = 2i · m,
όπου m είναι ένας οποιοσδήποτε αριθμός από τους πρώτους Φερμά αριθμούς και i είναι ένας οποιοσδήποτε φυσικός αριθμός ή το μηδέν.
Ο παρακάτω πίνακας δίνει τους μεγαλύτερους γνωστούς πρώτους αριθμούς των προαναφερθέντων τύπων. Κάποιοι από αυτούς τους πρώτους βρέθηκαν χρησιμοποιώντας κατανεμημένα συστήματα πληροφορικής.
Εύρεση πρώτων
thumb|right|250px|[[Κόσκινο του Ερατοσθένη]]
Η εύρεση των πρώτων αριθμών απασχόλησε από την αρχαιότητα τους μαθηματικούς. Ένας από τους πιο απλούς αλλά και αργούς τρόπους για (μαζική) εύρεση πολλών πρώτων είναι το λεγόμενο κόσκινο του Ερατοσθένη: Στο σύνολο των φυσικών αριθμών - πρακτικά έως κάποιο μεγάλο αριθμό Ν - αρχίζουμε και αποκλείουμε πρώτα τα πολλαπλάσια του 2 μετά τα πολλαπλάσια του επόμενου μη διαγραμμένου αριθμού κ.ο.κ. έως το Ν. Παρατηρούμε ότι όλο και λιγότερους αριθμούς θα βρίσκουμε προς διαγραφή. Οι αριθμοί που θα απομείνουν είναι όλοι πρώτοι. Το κόσκινο του Ερατοσθένη είναι ένας αργός αλγόριθμος για το αν ένας συγκεκριμένος αριθμός Ν είναι πρώτος ή όχι, διότι μεταξύ άλλων απαιτεί ουσιαστικά και την εύρεση όλων των πρώτων μικρότερων ίσων του \sqrt{N} (αν ένας αριθμός Ν δεν έχει διαιρέτες μικρότερους ίσους του \sqrt{N}, τότε είναι πρώτος).
thumb|right|250px|[[Οπτικό κόσκινο Matiyasevich-Stechkin ]]
Στις 14 Φεβρουαρίου 1999 οι Γιούρι Ματιγιάσεβιτς και Μπόρις Στέκιν δημοσίευσαν στο διαδίκτυο το οπτικό κόσκινο των πρώτων αριθμών. Τα σημεία της παραβολής x=y^2 με ακέραιες συντεταγμένες ορίζουν χορδές που τέμνουν τον οριζόντιο άξονα x΄x σε σημεία της μορφής (αβ,0) όπου α,β ακέραιοι κι επομένως σαρώνουν όλους τους σύνθετους θετικούς ακέραιους.
Αλγόριθμοι εύρεσης πρώτων
Παρατίθενται μερικοί αλγόριθμοι (κατά σειρά ταχύτητας ή και απλότητας) για την εύρεση αν ο Ν>=2 είναι πρώτος. Η σειρά επίσης αυτών των αλγορίθμων είναι παιδευτική για την εισαγωγή σε μια σειρά από προγράμματα για ηλεκτρονικούς υπολογιστές.
Απλός 2
Βασιζόμενοι στην παρατήρηση ότι κανένας αριθμός Ν δεν έχει διαιρέτη μεγαλύτερο του Ν/2, τροποποιούμε τον παραπάνω αλγόριθμο εξετάζοντας όλους τους αριθμούς Μ < Ν/2, διπλασιάζοντας έτσι την ταχύτητα σε σχέση με τον "Απλό 1".
Απλός 3
Παρατηρούμε ότι αν ένας αριθμός Ν δεν είναι πρώτος τότε έχει (τουλάχιστον) δύο διαιρέτες μεγαλύτερους από 1. Σε αυτήν την περίπτωση τουλάχιστον ένας διαιρέτης είναι μικρότερος από την τετραγωνική ρίζα του αριθμού. Τροποποιούμε τον αλγόριθμο 2 εξετάζοντας όλους τους αριθμούς Μ που είναι μικρότεροι από την τετραγωνική ρίζα του N, αν η τελευταία δεν είναι ακέραιος. Αλλιώς ο αριθμός δεν είναι πρώτος, επειδή τον διαιρεί και η τετραγωνική του ρίζα.
Απλός 4
Εφαρμόζοντας το Θεώρημα του Ουίλσον μπορούμε να εξετάσουμε, αν ένας αριθμός Ν είναι πρώτος ή όχι. Σύμφωνα με το θεώρημα αυτό ο Ν είναι πρώτος αν και μόνο αν ισχύει αν δηλαδή το υπόλοιπο της διαίρεσης του Ν-1 παραγοντικό με το Ν, είναι ίσο με το υπόλοιπο της διαίρεσης του -1 με το N.
Ο μεγαλύτερος γνωστός πρώτος αριθμός
Τον Αύγουστο του 2023 ο μεγαλύτερος γνωστός πρώτος αριθμός ήταν ο 282589933 − 1, ο οποίος έχει 24.862.048 ψηφία. Βρέθηκε τον Δεκέμβριο του 2018 από το Great Internet Mersenne Prime Search (GIMPS).
Δεύτερος  είναι ο 277.232.917 − 1, ο οποίος έχει 23.249.425 ψηφία. Βρέθηκε τον Δεκέμβριο του 2017 από το Great Internet Mersenne Prime Search (GIMPS).
Ο τρίτος πρώτος είναι ο:
Ο τέταρτος πρώτος είναι ο :
και η ανακάλυψη του, έγινε στις 25 Ιανουαρίου 2013, μέσω του διαδικτυακού προγράμματος κατανεμημένης επεξεργασίας GIMPS (Great Internet Mersenne Prime Search). Ο αριθμός αυτός έχει 17.425.179 ψηφία (ο δεύτερος με πάνω από 10 εκατομμύρια ψηφία) και έχει την πρόσθετη ιδιότητα να είναι ο 48ος Μερσέν πρώτος (Mersenne prime) που ανακαλύφθηκε. Ο 47ος Μερσέν πρώτος, ο 243,112,609 − 1, ανακαλύφθηκε στις 25 Αυγούστου του 2008.
Στο πρόσφατο παρελθόν, όλοι οι πρώτοι που ανακαλύφθηκαν ήταν Μερσέν πρώτοι.
Επίσης, για τον πρώτο πρώτο αριθμό που ανακαλύφθηκε και είχε πάνω από 10.000.000 ψηφία, δόθηκαν 100.000 δολάρια.
Κατανομή
Η κατανομή των πρώτων αριθμών γενικά, όπως η ερώτηση πόσοι πρώτοι αριθμοί είναι μικρότεροι από ένα δοθέντα πρώτο αριθμό, πόσο μεγάλο είναι το όριο, περιγράφεται από το θεώρημα των πρώτων αριθμών, αλλά δεν είναι γνωστός κανένας τύπος που να είναι αποτελεσματικός για το n-οστό πρώτο αριθμό.
Υπάρχουν αυθαίρετα μεγάλες ακολουθίες διαδοχικών μη πρώτων αριθμών, όπως για κάθε θετικό ακέραιο αριθμό n οι n διαδοχικοί ακέραιοι από (n + 1)! + 2 ως (n + 1)! + n + 1 (συμπεριλαμβανομένης και της τελικής τιμής) είναι όλοι σύνθετοι αριθμοί (αφού (n + 1)! + k διαιρείται από τον k για k από 2 ως n + 1).
Το θεώρημα του Ντίριχλετ για τις αριθμητικές προόδους, στη βασική του μορφή, ισχυρίζεται ότι τα γραμμικά πολυώνυμα
p(n) = α + bn
με τους σχετικά πρώτους α και b να παίρνουν άπειρα πολλές τιμές πρώτων αριθμών. Ισχυρότερες μορφές του θεωρήματος αναφέρουν ότι το άθροισμα των τιμών που επιστρέφει το πολυώνυμο αυτών των τιμών που είναι πρώτοι αριθμοί αποκλίνει και αυτές οι διαφορές που υπάρχουν στα πολυώνυμα με το ίδιο b έχουν περίπου τις ίδιες αναλογίες των πρώτων αριθμών.
Η αντίστοιχη ερώτηση για τα τετραγωνικά πολυώνυμα είναι λιγότερο κατανοητή.
Δεν υπάρχει κανένας γνωστός αποτελεσματικός τύπος για τους πρώτους αριθμούς. Για παράδειγμα, το θεώρημα του Μιλς και ένα θεώρημα του Ράιτ ισχυρίζονται ότι υπάρχουν πραγματικές σταθερές Α > 1 και μ, τέτοιες ώστε
να είναι πρώτοι αριθμοί για κάθε φυσικό αριθμό n. Εδώ αντιπροσωπεύει ακέραιο μέρος της έκφρασης, δηλαδή το μεγαλύτερο ακέραιο που δεν είναι  από τον αριθμό που είναι στις αγκύλες. Ο τελευταίος τύπος μπορεί να αποδειχθεί χρησιμοποιώντας το αξίωμα του Μπέρτραντ (αποδεδειγμένο πρώτα από τον Παφνούτι Λβόβιτς Τσέμπισσιοφ), το οποίο αναφέρει ότι πάντα υπάρχει τουλάχιστον ένας πρώτος αριθμός p με n < p < 2n - 2, για κάθε φυσικό αριθμό n > 3. Ωστόσο, για να υπολογίσουμε τον Α ή τον μ απαιτείται η γνώση των απείρως πολλών πρώτων αριθμών με τους οποίους θα ξεκινήσουμε. Ένας άλλος τύπος βασίζεται στο θεώρημα του Ουίλσον και παράγει τον αριθμό 2 πολλές φορές και όλους τους άλλους πρώτους αριθμούς ακριβώς μία φορά.
Δεν υπάρχει κανένα μη σταθερό πολυώνυμο, ακόμη και σε αρκετές μεταβλητές, οι οποίες παίρνουν ως τιμές μόνο πρώτους αριθμούς. Ωστόσο, υπάρχει ένα σύνολο διοφαντικών εξισώσεων σε 9 μεταβλητές και μια παράμετρος με την εξής ιδιότητα: η παράμετρος είναι πρώτος αριθμός αν και μόνο αν το σύστημα που προκύπτει από τις εξισώσεις έχει μία λύση στους φυσικούς αριθμούς. Αυτό θα μπορούσε να χρησιμοποιηθεί για να αποκτήσει ένα απλό τύπο με την ιδιότητα ότι όλες οι θετικές τιμές του είναι πρώτοι αριθμοί.
Η συνάρτηση που καταμετράει τους πρώτους αριθμούς π(n) ορίζεται ως το πλήθος των πρώτων αριθμών μέχρι και τον n. Για παράδειγμα π(11) = 5, αφού υπάρχουν πέντε πρώτοι αριθμοί μικρότεροι ή ίσοι του 11. Υπάρχουν γνωστοί αλγόριθμοι για να υπολογίσουμε τις ακριβείς τιμές της συνάρτησης π(n) πιο γρήγορα από ότι να υπολογίζαμε αν κάθε αριθμός είναι πρώτος μέχρι και τον n. Το θεώρημα των πρώτων αριθμών αναφέρει ότι η π(n) δίνεται περίπου από τον τύπο
με την έννοια ότι η αναλογία της π(n) με το κλάσμα του δεξιού μέλους τείνει στο 1, όταν ο n τείνει στο άπειρο. Αυτό συνεπάγεται ότι η πιθανότητα ένας αριθμός μικρότερος του n να είναι πρώτος είναι (περίπου) αντιστρόφως ανάλογη του πλήθους των ψηφίων του n. Ένας πιο ακριβής υπολογισμός για την π(n) δίνεται από το λογαριθμικό ολοκλήρωμα
Το θεώρημα πρώτων αριθμών συνεπάγεται ότι υπολογίζει το μέγεθος του n-οστού πρώτου αριθμού pn (δηλαδή p1 = 2, p2 = 3, κ.ο.κ.) : μέχρι ένα οριοθετημένο παράγοντα, ο pn αυξάνεται όπως η nlog(n). Πιο συγκεκριμένα, τα κενά των πρώτων αριθμών,δηλαδή οι διαφορές pn - pn-1 των δύο διαδοχικών πρώτων αριθμών, γίνονται αυθαίρετα μεγάλες. Αυτή η τελευταία πρόταση μπορεί επίσης να διατυπωθεί με ένα πιο στοιχειώδη τρόπο σημειώνοντας ότι η ακολουθία n! + 2, n! + 3, …, n! + n αποτελείται από n - 1 σύνθετους αριθμούς, για κάθε φυσικό αριθμό n.
Μια αριθμητική πρόοδος είναι ένα σύνολο φυσικών αριθμών, οι οποίοι δίνουν το ίδιο υπόλοιπο, όταν διαιρούνται από κάποιους σταθερούς αριθμούς q, οι οποίοι ονομάζονται μέτρο. Για παράδειγμα
3, 12, 21, 30, 39, ...,
είναι μια αριθμητική πρόοδος μέτρου q = 9. Εκτός από το 3, κανείς από αυτούς τους αριθμούς δεν είναι πρώτος, αφού 3 + 9n = 3(1 + 3n), έτσι ώστε οι υπόλοιποι αριθμοί της προόδου αυτής είναι όλοι σύνθετοι. (Σε γενικές γραμμές, όλοι οι πρώτοι αριθμοί μεγαλύτεροι του q είναι της μορφής q# · n + m, όπου 0 < m < q# και ο m δεν έχει κανένα παράγοντα πρώτο αριθμό ≤ q.) Έτσι, η πρόοδος
α, α + q, α + 2q, α + 3q, ...
απείρως πολλούς πρώτους αριθμούς, μόνο όταν οι α και q είναι σχετικοί πρώτοι αριθμοί, δηλαδή ο μέγιστος κοινός τους διαιρέτης είναι το ένα. Αν ικανοποιείται αυτή η αναγκαία συνθήκη, τότε το θεώρημα του Ντίριχλετ για τις αριθμητικές προόδους ισχυρίζεται ότι η πρόοδος περιέχει απείρως πολλούς πρώτους αριθμούς. Η εικόνα παρακάτω απεικονίζει την πρόοδο με q = 9: οι αριθμοί είναι τυλιγμένοι γύρω μέχρι να περάσει ένα πολλαπλάσιο του 9. Οι πρώτοι αριθμοί είναι μαρκαρισμένοι με κόκκινο χρώμα. Οι σειρές(= πρόοδοι) που αρχίζουν με α = 3, 6 ή 9 περιέχουν το πολύ ένα πρώτο αριθμό. Σε όλες τις άλλες σειρές (α = 1, 2, 4, 5, 7 και 8) υπάρχουν απείρως πολλοί πρώτοι αριθμοί. Επιπλέον, οι πρώτοι αριθμοί κατανέμονται ισομερώς μεταξύ αυτών των σειρών σε όλη τη ροή - η πυκνότητα των πρώτων αριθμών με σύγκλιση α μέτρου 9 είναι 1/6.
Ο Όιλερ σημείωσε ότι η συνάρτηση
n2 + n + 41
δίνει πρώτους αριθμούς για 0 ≤ n < 40, ένα γεγονός που οδηγεί βαθιά μέσα στην αλγεβρική θεωρία αριθμών και πιο συγκεκριμένα στους αριθμούς Χέεγκνερ. Για μεγαλύτερα n, η συνάρτηση δίνει σύνθετους αριθμούς. Η εικασία F των Χάρντι-Λίτλγουντ κάνει μια ασυμπτωτική πρόβλεψη για την πυκνότητα των πρώτων αριθμών μεταξύ των τιμών των δευτεροβάθμιων πολυωνύμων (με ακέραιους συντελεστές a, b και c)
Ωστόσο, η πρόοδος έχει αποδειχτεί δύσκολο να βρεθεί: κανένα δευτεροβάθμιο πολυώνυμο (με a ≠ 0) δεν είναι γνωστό να παίρνει απείρως πολλούς πρώτους αριθμούς ως τιμές. Η σπείρα του Ούλαμ απεικονίζει όλους τους φυσικούς αριθμούς με ένα σπειροειδές τρόπο. Οι πρώτοι αριθμοί μαζεύονται σε συγκεκριμένες διαγώνιες και όχι σε άλλες, γεγονός που υποδηλώνει ότι κάποια δευτεροβάθμια πολυώνυμα παίρνουν ως τιμές πρώτους αριθμούς πιο συχνά από άλλα.
Ανοικτά ερωτήματα
Η συνάρτηση ζήτα του Ρίμαν ζ(s) ορίζεται ως ένα άπειρο άθροισμα
όπου s είναι ένας μιγαδικός αριθμός με πραγματικό μέρος μεγαλύτερο του 1. Είναι συνέπεια του θεμελιώδους θεωρήματος της αριθμητικής ότι αυτό το άθροισμα συμφωνεί με το άπειρο γινόμενο
Η συνάρτηση ζήτα είναι στενά συνδεδεμένη με τους πρώτους αριθμούς. Για παράδειγμα, το προαναφερθέν γεγονός ότι υπάρχουν άπειροι πρώτοι αριθμοί μπορεί επίσης να δειχθεί χρησιμοποιώντας τη συνάρτηση ζήτα: αν υπήρχαν πεπερασμένου του πλήθους πρώτοι αριθμοί, τότε η ζ(1) θα είχε μια πεπερασμένη τιμή. Ωστόσο, η αρμονική σειρά 1 + 1/2 + 1/3 + 1/4 + ... αποκλίνει (δηλαδή ξεπερνά κάθε δεδομένο αριθμό) κι έτσι πρέπει να υπάρχουν απείρως πολλοί πρώτοι αριθμοί. Ένα άλλο παράδειγμα της σημαντικότητας της συνάρτησης ζήτα και μια γεύση από τη σύγχρονη αλγεβρική θεωρία αριθμών είναι η παρακάτω ταυτότητα (πρόβλημα της Βασιλείας), σύμφωνα με τον Όιλερ,
Η τιμή της ζ(2), 6/π2, είναι η πιθανότητα δύο τυχαία επιλεγμένοι αριθμοί να είναι σχετικά πρώτοι.
Η χωρίς απόδειξη υπόθεση του Ρίμαν, από το 1859, αναφέρει ότι εκτός από τους s = -2, -4, ... όλα τα μηδενικά της ζήτα συνάρτησης έχουν πραγματικό μέρος ίσο με 1/2. Η σύνδεση στους πρώτους αριθμούς είναι αυτή που ουσιαστικά λέει ότι οι πρώτοι αριθμοί κατανέμονται όσο πιο τακτικά γίνεται. Από φυσική άποψη, η υπόθεση περίπου αναφέρει ότι η αταξία στην κατανομή των πρώτων αριθμών προέρχεται μόνο από τυχαίο θόρυβο. Από μαθηματική άποψη, η υπόθεση περίπου αναφέρει ότι η ασυμπτωτική κατανομή των πρώτων αριθμών (σχετικά με το ότι οι αριθμοί x/logx που είναι μικρότεροι από x είναι πρώτοι αριθμοί, θεώρημα πρώτων αριθμών) επίσης ισχύει για πολύ μικρότερα σε μήκος διαστήματα σχετικά με την τετραγωνική ρίζα του x (για διαστήματα κοντά στο x). Αυτή η υπόθεση θεωρείται γενικά ορθή. Πιο συγκεκριμένα, η απλούστερη υπόθεση είναι ότι οι πρώτοι αριθμοί δε θα έπρεπε να έχουν σημαντικές αταξίες χωρίς ένα καλό λόγο.
Εκτός από την υπόθεση του Ρίμαν, πολλές ακόμη εικασίες σχετικά με τους πρώτους αριθμούς έχουν διατυπωθεί. Συχνά έχοντας μια στοιχειώδη σύνθεση, πολλές από αυτές τις εικασίες δεν έχουν απόδειξη για δεκαετίες: και τα τέσσερα προβλήματα του Λαντό παραμένουν άλυτα από το 1912. Ένα από αυτά είναι η εικασία του Γκόλντμπαχ, η οποία βεβαιώνει ότι κάθε άρτιος ακέραιος αριθμός n μεγαλύτερος του 2 μπορεί να γραφεί ως άθροισμα δύο πρώτων αριθμών. Από το Φεβρουάριο του 2011, αυτή η εικασία έχει επαληθευτεί για όλους τους αριθμούς μέχρι και n = 2 · 1017. Πιο απλές προτάσεις από αυτή έχουν αποδειχτεί, για παράδειγμα το θεώρημα του Βινογκραντόφ λέει ότι κάθε αρκετά μεγάλος περιττός ακέραιος αριθμός μπορεί να γραφεί ως άθροισμα τριών πρώτων αριθμών. Το θεώρημα του Κεν λέει ότι κάθε αρκετά μεγάλος άρτιος αριθμός μπορεί να γραφεί ως άθροισμα ενός πρώτου και ενός ημιπρώτου (= γινόμενο δύο πρώτων αριθμών) αριθμού. Επιπρόσθετα, κάθε άρτιος ακέραιος αριθμός μπορεί να γραφεί ως άθροισμα έξι πρώτων αριθμών. Το τμήμα της θεωρίας αριθμών που μελετά αυτές τις ερωτήσεις ονομάζεται πρόσθετη θεωρία αριθμών.
Ένας τρίτος τύπος εικασιών αφορά τις πτυχές της κατανομής των πρώτων αριθμών. Εικάζεται ότι υπάρχουν απείρως πολλοί δίδυμοι πρώτοι αριθμοί, ζευγάρια πρώτων αριθμών με διαφορά 2 (εικασία των διδύμων πρώτων αριθμών). Η εικασία του Πόλινακ ενισχύει την παραπάνω εικασία, καθώς αναφέρει ότι για κάθε θετικό ακέραιο αριθμό n, υπάρχουν απείρως πολλά ζευγάρια διαδοχικών πρώτων αριθμών με διαφορά 2n. Εικάζεται ότι υπάρχουν απείρως πολλοί πρώτοι αριθμοί της μορφής n2 + 1. Αυτές οι εικασίες είναι ειδικές περιπτώσεις της ευρείας υπόθεσης Η του Σίντσελ. Η εικασία του Μπρόκαρντ λέει ότι υπάρχουν πάντα τουλάχιστον τέσσερις πρώτοι αριθμοί μεταξύ των τετραγώνων δύο διαδοχικών πρώτων αριθμών μεγαλύτερων του 2. Η εικασία του Λεγκρέντ αναφέρει ότι υπάρχει ένας πρώτος αριθμός μεταξύ n2 και (n + 1)2 για κάθε θετικό ακέραιο αριθμό n. Υπονοείται από την ισχυρότερη εικασία του Κράμερ.
Οι εικασίες του Γκόλντμπαχ
Είναι πολύ γνωστή η πρώτη εικασία που διατύπωσε ο Κρίστιαν Γκόλντμπαχ 1690-1764, η οποία σχετίζεται με τους πρώτους αριθμούς. Ο Γκόλντμπαχ υποστήριξε ότι κάθε άρτιος αριθμός μεγαλύτερος του 2, μπορεί να γραφεί ως άθροισμα δύο πρώτων αριθμών. Η απόδειξη της παραπάνω εικασίας ταλανίζει ακόμα και σήμερα τους μαθηματικούς, καθώς παράλληλα οι υπολογιστές επιβεβαιώνουν την εικασία για όλο και μεγαλύτερους αριθμούς. Το 1998, η εικασία επιβεβαιώθηκε για αριθμούς μέχρις και της τάξης του 10^{14}
Η δεύτερη εικασία του Γκόλντμπαχ έγκειται στο ότι κάθε περιττός αριθμός του 6 είναι άθροισμα τριών πρώτων αριθμών. Και αυτή η εικασία παραμένει αναπόδεικτη, αν και επιβεβαιώνεται από ηλεκτρονικούς υπολογιστές. Τυχόν απόδειξη της πρώτης εικασίας του Γκόλντμπαχ θα αποδείκνυε αμέσως και τη δεύτερη εικασία. Στη πρώτη εικασία γιατί <... του 2;...>, 2=1+1 άθροισμα δύο Πρώτων ή να διατυπωθεί    <.....ως άθροισμα δύο διαφορετικών Πρώτων ......>.
Εφαρμογές
Για πολύ καιρό, η θεωρία αριθμών γενικά και η μελέτη των πρώτων αριθμών συγκεκριμένα αποτελούσαν κλασικό παράδειγμα των καθαρών μαθηματικών, με καθόλου εφαρμογές έξω από το θεωρητικό κομμάτι. Πιο συγκεκριμένα, μαθηματικοί που ασχολήθηκαν με τη θεωρία αριθμών, όπως ο Βρετανός Γ. Χ. Χάρντι υπερηφανεύονταν ότι εργάζονταν πάνω σε κάτι που δεν είχε καμία στρατιωτική σημασία. Ωστόσο, αυτή η οπτική καταρρίφθηκε τη δεκαετία του 1970, όταν ανακοινώθηκε δημοσίως ότι οι πρώτοι αριθμοί μπορούσαν να χρησιμοποιηθούν ως βάση για τη δημιουργία αλγορίθμων κρυπτογραφίας δημοσίου κλειδιού. Οι πρώτοι αριθμοί επίσης χρησιμοποιήθηκαν για πίνακες κατακερματισμού και για γεννήτριες ψευδοτυχαίων αριθμών.
Μερικές μηχανές με στροφείο (rotor machines) σχεδιάστηκαν με ένα διαφορετικό πλήθος καρφιών σε κάθε στροφείο, με το πλήθος των καρφιών σε κάθε στροφείο να είτε πρώτος, ή σύνθετος στο πλήθος των καρφιών οποιουδήποτε άλλου στροφείου. Αυτό βοήθησε στη δημιουργία ενός πλήρους κύκλου πιθανών θέσεων στροφείων πριν την επανάληψη κάθε θέσης.
Ο Διεθνής Πρότυπος Αριθμός Βιβλίου δουλεύει με ένα ψηφίο ελέγχου, το οποίο εκμεταλλεύεται το γεγονός ότι ο αριθμός 11 είναι πρώτος αριθμός.
Η αριθμητική modular τροποποιεί τη συνήθη αριθμητική χρησιμοποιώντας μόνο τους αριθμούς
{0, 1, 2, ..., n - 1},
όπου ο n είναι ένας σταθερός φυσικός αριθμός που ονομάζεται modulus. ο υπολογισμός των αθροισμάτων, των διαφορών και των γινομένων γίνεται ως συνήθως, αλλά όποτε συναντούμε ένα αρνητικό αριθμό ή ένα αριθμό μεγαλύτερο του n - 1, αυτός αντικαθίσταται από το υπόλοιπο μετά τη διαίρεση από τον n. Για παράδειγμα, για n = 7, το άθροισμα 3 + 5 ισούται με 1 αντί για 8, αφού όταν το 8 διαιρείται με το 7 αφήνει υπόλοιπο 1. Για να αναφερθούμε σε αυτό, λέμε ότι το 3 + 5 είναι σύμφωνο με το 1 modulo 7 και γράφουμε
Ομοίως, 6 + 1 ≡ 0 (mod 7), 2 - 5 ≡ 4 (mod 7), αφού -3 + 7 = 4 και 3 · 4 ≡ 5 (mod 7), καθώς το 12 αφήνει υπόλοιπο το 5. Οι βασικές ιδιότητες της πρόσθεσης και του πολλαπλασιασμού γνωστές από τους ακεραίους ισχύουν και στην modular αριθμητική. Στον τομέα της αφηρημένης άλγεβρας, το παραπάνω σύνολο των ακεραίων, το οποίο συμβολίζεται με Z/nZ, είναι επομένως ένας αντιμεταθετικός δακτύλιος για κάθε n. Η διαίρεση όμως, δεν είναι γενικά δυνατή σε αυτή την κατάσταση. Για παράδειγμα, για n = 6, στην εξίσωση
μια λύση του x, η οποία θα ήταν ανάλογη με 2/3, δεν μπορεί να βρεθεί, καθώς το ένα μπορεί να βρεθεί υπολογίζοντας 3 · 0, ..., 3 · 5 modulo 6. Το ιδιαίτερο χαρακτηριστικό των πρώτων αριθμών είναι το εξής: η διαίρεση είναι δυνατή στη modular αριθμητική αν και μόνο αν ο n είναι πρώτος αριθμός. Ισοδύναμα, ο n είναι πρώτος αριθμός αν και μόνο αν όλοι οι ακέραιοι m που ικανοποιούν την ανισότητα 2 ≤ m ≤ n − 1 είναι σχετικοί πρώτοι με τον n, δηλαδή ο μόνος κοινός διαιρέτης τους είναι το 1. Πράγματι, για n = 7, η εξίσωση
έχει μοναδική λύση, τη x = 3. Εξαιτίας αυτού, για κάθε πρώτο αριθμό p, το Z/pZ (μερικές φορές σημειώνεται ως Fp) ονομάζεται σώμα ή πιο συγκεκριμένα πεπερασμένο σώμα, αφού περιέχει πεπερασμένου του πλήθους, δηλαδή p, στοιχεία. Ένα πλήθος θεωρημάτων μπορούν να προέρχονται από τη μελέτη του Fp με αυτό τον αφηρημένο τρόπο. Για παράδειγμα, το μικρό θεώρημα του Fermat, το οποίο αναφέρει ότι
για κάθε ακέραιο αριθμό a που δε διαιρείται από τον p, μπορεί να αποδειχθεί χρησιμοποιώντας αυτές τις έννοιες. Αυτό συνεπάγεται ότι
Η εικασία του Τζιούγκα λέει ότι αυτή η εξίσωση είναι επίσης μια επαρκής συνθήκη για να πούμε ότι ο p είναι πρώτος αριθμός. Μια άλλη συνέπεια του μικρού θεωρήματος του Fermat είναι η εξής: αν ο p είναι ένας πρώτος αριθμός διαφορετικός του 2 και του 5, ο 1/p είναι πάντα ένας περιοδικός αριθμός, με περίοδο p - 1 ή ένα διαιρέτη του p - 1. Το κλάσμα 1/p εκφρασμένο επίσης στη βάση q (αντί στη βάση 10) έχει παρόμοιο αποτέλεσμα, υπό τον όρο ο p δεν είναι παράγοντας του q ως πρώτος αριθμός. Το θεώρημα του Ουίλσον λέει ότι ένας ακέραιος αριθμός p > 1 είναι πρώτος αν και μόνο αν το παραγοντικό (p - 1)! + 1 είναι διαιρέσιμο από τον p. Επιπλέον, ένας ακέραιος αριθμός n > 4 είναι σύνθετος αν και μόνο αν (n - 1)! είναι διαιρέσιμο από τον n.
Πολλά μαθηματικά πεδία χρησιμοποιούν πολύ τους πρώτους αριθμούς. Ένα παράδειγμα από τη θεωρία των πεπερασμένων σωμάτων είναι τα θεωρήματα του Sylow: αν G είναι ένα πεπερασμένο σώμα και pn είναι η μεγαλύτερη δύναμη του πρώτου αριθμού p που διαιρεί τη διάταξη G, τότε η G έχει μια υποομάδα τάξης pn. Επίσης, κάθε ομάδα με διάταξη πρώτων αριθμών είναι κυκλική (θεώρημα του Lagrange).
Αναπόφευκτα, μερικοί από τους αριθμούς που συναντώνται στη φύση είναι πρώτοι. Ωστόσο, υπάρχουν σχετικά λίγα παραδείγματα αριθμών, οι οποίοι εμφανίζονται στη φύση, επειδή είναι πρώτοι.
Ένα παράδειγμα της χρήσης των πρώτων αριθμών στη φύση είναι ως εξελικτική στρατηγική που χρησιμοποιείται από τα τζιτζίκια του γένους Magicicada. Αυτά τα έντομα περνούν τον περισσότερο χρόνο της ζωής τους ως προνύμφες υπογείως. Τα έντομα αυτά μεγαλώνουν και στη συνέχεια βγαίνουν από τις φωλιές τους μετά από 13 ή 17 χρόνια, χρονικό σημείο από το οποίο θα αρχίσουν να πετάνε, να γεννάνε και μετά από λίγες εβδομάδες το πολύ πεθαίνουν. Θεωρείται ότι η λογική για αυτό είναι ότι τα διαστήματα πρώτων αριθμών μεταξύ καταστάσεων έκτακτης ανάγκης καθιστούν πολύ δύσκολο να εξελιχθούν τα αρπακτικά, οι οποίοι θα μπορούσαν να εξειδικευτούν ως θηρευτές των Magicicada. Αν τα έντομα αυτά δεν εμφανίζονταν σε διαστήματα πρώτων αριθμών, ας πούμε κάθε 12 χρόνια, τότε οι θηρευτές τους που θα εμφανίζονταν κάθε 2, 3, 4, 6 ή 12 χρόνια θα ήταν σίγουρο ότι θα τα συναντούσαν. Για πάνω από 200 χρόνια, ο μέσος όρος του πληθυσμού των αρπακτικών κατά τη διάρκεια της πιθανής γέννησης 14 και 15 ετών των τζιτζικιών θα ήταν έως και 2% υψηλότερα από ότι κατά τη διάρκεια γέννησής τους 13 και 17 ετών. Παρόλο που είναι μικρό, το πλεονέκτημα αυτό εμφανίζεται να είναι αρκετό για να οδηγηθούν στη φυσική επιλογή υπέρ της προνομιακής αρίθμησης του κύκλου ζωής για αυτά τα έντομα.
Αυτό είναι το πρόβλημα ότι τα μηδενικά της συνάρτηση ζήτα ζήτα συνάρτησης είναι συνδεδεμένα με τα επίπεδα ενέργειας των πολύπλοκων κβαντικών συστημάτων.
Γενικεύσεις
Από τους πρώτους αριθμούς προκύπτουν δύο πιο γενικές έννοιες, οι οποίες εφαρμόζονται στα στοιχεία κάθε αντιμεταθετικού δακτυλίου R, μια αλγεβρική δομή, όπου ορίζονται η πρόσθεση, η αφαίρεση και ο πολλαπλασιασμός: πρώτα στοιχεία και στοιχεία που δεν ανάγονται. Ένα στοιχείο p του R ονομάζεται πρώτο στοιχείο αν δεν είναι ούτε μηδέν ούτε μονάδα (δηλαδή δεν έχει αντίστροφο στον πολλαπλασιασμό) και ικανοποιεί την παρακάτω προϋπόθεση: δοθέντων x και y στο R, τέτοια ώστε ο p να διαιρεί το γινόμενο xy, τότε ο p διαιρεί τον x ή τον y. Ένα στοιχείο δεν ανάγεται αν δεν μπορεί να γραφεί ως γινόμενο δύο στοιχείων του δακτυλίου, τα οποία δεν είναι μονάδες. Στο δακτύλιο Ζ των ακεραίων αριθμών, το σύνολο των πρώτων στοιχείων ισούται με το σύνολο των στοιχείων που δεν ανάγονται, το οποίο είναι το
Σε κάθε δακτύλιο R, κάθε πρώτο στοιχείο δεν ανάγεται. Το αντίστροφο γενικά δεν ισχύει, αλλά ισχύει για τη μοναδική παραγοντοποίηση διαστημάτων.
Το θεμελιώδες θεώρημα της αριθμητικής συνεχίζει να ισχύει στη μοναδική παραγοντοποίηση διαστημάτων. Ένα παράδειγμα τέτοιου διαστήματος είναι οι ακέραιοι του Γκάους Z[i], οι οποίοι αποτελούν το σύνολο των μιγαδικών αριθμών της μορφής a + bi, όπου το i δηλώνει τη μονάδα των φανταστικών αριθμών και οι a και b είναι τυχαίοι ακέραιοι αριθμοί. Τα πρώτα στοιχεία του συνόλου αυτού είναι γνωστά ως πρώτοι αριθμοί του Gauss. Κάθε πρώτος αριθμός (ακέραιος) δεν είναι πρώτος αριθμός του Γκάους: στο μεγαλύτερο δακτύλιο Z[i], 2 παράγοντες στο γινόμενο των δύο πρώτων αριθμών του Γκάους (1 + i) και (1 - i). Λογικοί πρώτοι αριθμοί (δηλαδή πρώτα στοιχεία του Ζ) της μορφής 4k + 3 είναι πρώτοι αριθμοί του Γκάους, ενώ όλοι οι πρώτοι αριθμοί της μορφής 4k + 1 δεν είναι.
Τα ιδανικά των πρώτων αριθμών είναι τα σημεία των αλγεβρογεωμετρικών αντικειμένων, μέσω της έννοιας του φάσματος ενός δακτυλίου. Η αλγεβρική γεωμετρία επίσης επωφελείται από αυτή την έννοια και πράγματι πολλές έννοιες υπάρχον ταυτόχρονα και στη γεωμετρία και στη θεωρία αριθμών. Για παράδειγμα, η παραγοντοποίηση ή η διακλάδωση των ιδανικών των πρώτων αριθμών, όταν αρθεί σε ένα επεκταμένο διάστημα, ένα βασικό πρόβλημα της αλγεβρικής θεωρίας αριθμών, έχει κάποιες ομοιότητες με διακλάδωση στη γεωμετρία. Τέτοιες ερωτήσεις διακλάδωσης, οι οποίες εμφανίζονται ακόμη και σε ερωτήσεις της θεωρίας αριθμών, αποκλειστικά ασχολούνται με ακεραίους αριθμούς. Για παράδειγμα, τα ιδανικά των πρώτων αριθμών στο δακτύλιο των ακεραίων αριθμών σε διάστημα με τα τετράγωνα των αριθμών μπορούν να χρησιμοποιηθούν στην απόδειξη της τετραγωνικής αμοιβαιότητας, μια πρόταση η οποία αφορά τη λύση των δευτεροβάθμιων εξισώσεων
όπου ο x είναι ένας ακέραιος και p και q είναι (συνήθεις) πρώτοι αριθμοί. Οι πρόσφατες προσπάθειες για την απόδειξη του τελευταίου θεωρήματος του Φερμά κορυφώθηκαν, όταν ο Kummer εισήγαγε τους τακτικούς πρώτους αριθμούς, δηλαδή πρώτους αριθμούς που ικανοποιούν μια συγκεκριμένη προϋπόθεση σχετικά με την αποτυχία της μοναδικής παραγοντοποίησης στο δακτύλιο που αποτελείται από τις εκφράσεις
όπου a0, ..., ap-1 είναι ακέραιοι και ο ζ είναι ένας μιγαδικός αριθμός, τέτοιος ώστε ζp = 1.
Η θεωρία των αποτιμήσεων (valuation theory) μελετά συγκεκριμένες συναρτήσεις από ένα διάστημα Κ στους πραγματικούς αριθμούς R που ονομάζονται αποτιμήσεις. Κάθε τέτοια αποτίμηση αποδίδει μια τοπολογία στο Κ και δυο αποτιμήσεις ονομάζονται ισοδύναμες, αν αποδίδουν την ίδια τοπολογία. Ένας πρώτος αριθμός του Κ (μερικές φορές λέγεται μια τοποθεσία του Κ) είναι μια κλάση ισοδυναμίας των αποτιμήσεων. Για παράδειγμα, η p-αδική αποτίμηση ενός ρητού αριθμού q ορίζεται να είναι ο ακέραιος vp(q), τέτοιος ώστε
όπου οι r και s δεν είναι διαιρέσιμοι από τον p. Για παράδειγμα, v3(18/7) = 2. Ο p-αδικός τύπος ορίζεται ως
Πιο συγκεκριμένα, αυτός ο τύπος γίνεται μικρότερος, όταν ένας αριθμός πολλαπλασιάζεται από τον p, σε έντονη αντίθεση με τη συνήθη απόλυτη τιμή (επίσης αναφέρεται και ως άπειρος πρώτος). Ενώ συμπληρώνουμε τον Q (περίπου συμπληρώνοντας τα κενά) όσον αφορά την απόλυτη τιμή, αυτή αποδίδει το διάστημα των πραγματικών αριθμών, συμπληρώνοντας όσον αφορά τον p-αδικό τύπο |-|p αποδίδει το διάστημα των p-αδικών αριθμών. Αυτοί είναι ουσιαστικά όλοι οι πιθανοί τρόποι να συμπληρώσουμε τον Q, σύμφωνα με το θεώρημα του Οστρόφσκι.Ορισμένες αριθμητικές ερωτήσεις που σχετίζονται με τον Q ή με πιο γενικά καθολικά πεδία μπορούν να μεταφερθούν εμπρός και πίσω στα συμπληρωμένα (ή τοπικά) διαστήματα. Αυτή η τοπική-καθολική αρχή υπογραμμίζει ξανά τη σημασία των πρώτων αριθμών στη θεωρία αριθμών.
Στις τέχνες και τη λογοτεχνία
Οι πρώτοι αριθμοί έχουν επηρεάσει πολλούς καλλιτέχνες και συγγραφείς. Ο Γάλλος συνθέτης Ολιβιέρ Μεσσιάν χρησιμοποίησε τους πρώτους αριθμούς για να δημιουργήσει αμετρική μουσική μέσω φυσικών φαινομένων. Σε έργα, όπως Λα Νατιβίτ ντου Σενό (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, στο οποίο οι πρώτοι αριθμοί παρουσιάζονται ως ξένοι μεταξύ των ακεραίων αριθμών.
Μεταμόρφωση Εύβοιας
Η Μεταμόρφωση είναι μικρό χωριό της κεντρικής Εύβοιας στην Περιφερειακής Ενότητας Εύβοιας. με υψόμετρο 100 μέτρα. Απέχει 33 χλμ. Α. από τη Χαλκίδα, 6 χλμ. Β. από την Αμάρυνθο και 13 χλμ. ΒΑ. από την Ερέτρια (έδρα του δήμου). Επίσημα αναφέρεται, μετά την Επανάσταση του 1821 και την ενσωμάτωση της Εύβοιας, το 1835 ως Άνω Μάμουλα να προσαρτάται στον τότε δήμο Αμαρυνθίων ενώ το 1954 με το ΦΕΚ 188Α - 19/08/1954 μετονομάστηκε σε Μεταμόρφωση. Σύμφωνα με το πρόγραμμα Καλλικράτης μαζί με το γειτονικό Γυμνό αποτελούν τη δημοτική κοινότητα Γυμνού που υπάγεται στη δημοτική ενότητα Αμαρυνθίων του Δήμου Eρέτριας και σύμφωνα με την απογραφή του 2011 έχει πληθυσμό 22 κατοίκους.
Παραπομπές
Κατηγορία:Χωριά του νομού Εύβοιας Κατηγορία:Δήμος Ερέτριας
Βραχμαπούτρας
Ο Βραχμαπούτρα ή Τσανγκπό-Βραχμαπούτρα είναι ποταμός της Νότιας Ασίας, που διαρρέει την Κίνα, την Ινδία και το Μπανγκλαντές.
Πηγάζει από το νοτιοδυτικό Θιβέτ, σε υψόμετρο περίπου 6.000 μέτρων, και με το όνομα Γιαρλούνγκ Τσανγκπό διαρρέει το νότιο Θιβέτ. Στη συνέχεια, μέσα από φαράγγια, περνά στην περιοχή Αρουνάτσαλ Πραντές της Ινδίας, όπου είναι γνωστός ως Ντιχάνγκ. Έπειτα διαρέει μέσω της κοιλάδας του Άσαμ, όπου είναι γνωστός ως Βραχμαπούτρα, προς το Μπανγκλαντές (όπου ονομάζεται Τζαμούνα). Στο Μπανγκλαντές συνδέεται με τον Γάγγη στην περιοχή του Δέλτα του Γάγγη και τέλος εκβάλλει στον Κόλπο της Βεγγάλης.
Ο Βραχμαπούτρας έχει μήκος 2.896 χιλιόμετρα και στο μεγαλύτερο μέρος του είναι πλωτός. Κατά τη διάρκεια της άνοιξης σημειώνονται 100.000 κυβικά μέτρα ανά δευτερόλεπτο. Το μέσο βάθος του ποταμού είναι 124 πόδια (38 μέτρα) και το μέγιστο βάθος είναι 380 πόδια (120 μ).
Το νότιο τμήμα του Βραχμαπούτρα θεωρείται ιερό από τους Ινδουιστές. Το όνομα του ποταμού στα Σανσκριτικά σημαίνει "ο γιος του Βράχμα".
Παραπομπές
Κατηγορία:Γεωγραφία του Θιβέτ Κατηγορία:Ποταμοί της Κίνας Κατηγορία:Ποταμοί της Ινδίας Κατηγορία:Ποταμοί του Μπανγκλαντές Κατηγορία:Διεθνείς ποταμοί της Ασίας
Παγκόσμιο Κύπελλο Ποδοσφαίρου Ενόπλων 1969
Το 24ο Παγκόσμιο Κύπελλο Ποδοσφαίρου Ενόπλων (ΣΙΣΜ) διεξήχθη στην Αθήνα, στο Γήπεδο Λεωφόρου Αλεξάνδρας, από την 17η ως την 25η Ιουνίου του 1969.
Νικήτρια αναδείχθηκε η Εθνική Ομάδα Ποδοσφαίρου Ενόπλων της Ελλάδας με 1 ισοπαλία και μια νίκη στον όμιλο της, νίκη στα ημιτελικά και με έναν επεισοδιακό τελικό που η Ελλάδα πήρε το τρόπαιο με "νίκη άνευ αγώνος" στον τελικό που διακόπηκε στο 80΄ με το σκορ στο 0-0, λόγω αποχώρησης της ομάδας της Αλγερίας από τον αγωνιστικό χώρο διαμαρτυρόμενη έντονα για την διαιτησία.
Χώρες που μετείχαν
Στην τελική φάση μετείχαν έξι αντιπροσωπευτικές ομάδες χωρών (συνολικά 13), οι οποίες εκτός της διοργανώτριας Ελλάδας προκρίθηκαν από προκριματικούς ομίλους ως εξής:
Σύστημα διεξαγωγής
Στην πρώτη φάση οι έξι ομάδες χωρίστηκαν σε δυο ομίλους των τριών. Οι δυο πρώτες προκρίθηκαν στα ημιτελικά, όπου αγωνίστηκαν "χιαστί", η πρώτη του Α΄ με τη δεύτερη του Β΄ ομίλου. Οι νικητές έπαιξαν στον τελικό και οι ηττημένοι για την 3η θέση. Σε περιπτώσεις ισοβαθμίας (στους ομίλους) και σε περίπτωση ισοπαλίας μετά την παράταση (στα νοκ-άουτ ματς), υπερίσχυε η ομάδα που είχε κερδίσει περισσότερα κόρνερ, ένας κανονισμός που εφάρμοζε παραδοσιακά το ΣΙΣΜ, θεωρώντας πως έτσι προκρίνεται η πιο επιθετική ομάδα.
Τελικός
Η ομάδα της Αλγερίας αποχώρησε στο 80΄ διαμαρτυρόμενη για τη διαιτησία και μηδενίστηκε.
Ο αγώνας ήταν πολύ σκληρός και από το 32΄ οι δυο ομάδες έπαιζαν με δέκα παίκτες, όταν διαπληκτίστηκαν και αποβλήθηκαν ο Μποτίνος και ο Αμέρ. Οι διαμαρτυρίες των Αλγερινών ξεκίνησαν στο 62΄, όταν ο διαιτητής έδωσε πέναλτι υπέρ της Ελλάδας. Ο αγώνας διακόπηκε για πέντε λεπτά και στη συνέχεια το εκτέλεσε ο Δημητρίου πάνω στα χέρια του τερματοφύλακα. Στο 77΄ τραυματίστηκε ο Αλγερινός τερματοφύλακας και οι συμπαίκτες του διαμαρτυρήθηκαν έντονα στο διαιτητή ζητώντας να τιμωρηθούν οι Έλληνες για σκληρό παίξιμο απειλώντας να αποχωρήσουν. Στις διαμαρτυρίες πήραν μέρος και άτομα από τον πάγκο της αλγερινής ομάδας (αναπληρωματικοί, μασέρ, βοηθοί προπονητή και παράγοντες). Τελικά, μετά από τρία λεπτά αποχώρησαν από το γήπεδο και ο διαιτητής σφύριξε τη λήξη, διακόπτοντας το ματς υπέρ της Ελλάδας. Έτσι το τρόπαιο απονεμήθηκε στην Ελλάδα, που θεωρήθηκε νικήτρια άνευ αγώνος.