.
Στα μαθηματικά πρώτος αριθμός (ή απλά πρώτος) είναι ένας φυσικός αριθμός μεγαλύτερος της μονάδας με την ιδιότητα οι μόνοι φυσικοί διαιρέτες του να είναι η μονάδα και ο εαυτός του. Ένας φυσικός αριθμός μεγαλύτερος της μονάδας , ο οποίος δεν είναι πρώτος αριθμός ονομάζεται σύνθετος αριθμός. Για παράδειγμα, ο αριθμός 5 είναι πρώτος, επειδή μόνο οι αριθμοί 1 και 5 τον διαιρούν εξίσου, ενώ ο 6 είναι σύνθετος επειδή έχει διαιρέτες τους 2 και 3 εκτός των 1 και 6. Το μηδέν και το ένα δεν είναι πρώτοι αριθμοί. Το μηδέν συχνά δεν θεωρείται καν φυσικός αριθμός.
Η ακολουθία των 25 πρώτων αριθμών είναι η εξής:
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, ...
Ο αριθμός 2 είναι ο μόνος άρτιος (ζυγός) πρώτος αριθμός. Όλοι οι άλλοι πρώτοι είναι περιττοί (μονοί).
Το θεμελιώδες θεώρημα της αριθμητικής καθορίζει το βασικό ρόλο των πρώτων αριθμών στη θεωρία αριθμών: κάθε ακέραιος αριθμός μεγαλύτερος του 1 μπορεί να γραφεί ως γινόμενο πρώτων κατά μοναδικό τρόπο. Η μοναδικότητα σε αυτό το θεώρημα προϋποθέτει την εξαίρεση του 1 ως πρώτου αριθμού επειδή ένας πρώτος μπορεί να περιέχει αυθαίρετα πολλές φορές το 1 σε κάθε γινόμενο, για παράδειγμα 3, 1 x 3, 1 x 1 x 3, κ.ο.κ. είναι όλοι παράγοντες του 3.
Μια απλή αλλά αργή μέθοδος για να επαληθευτεί αν ένας δοθείς αριθμός n είναι πρώτος είναι η λεγόμενη δοκιμαστική διαίρεση. Η δοκιμαστική διαίρεση συνίσταται στον έλεγχο αν ο n είναι πολλαπλάσιο κάποιου ακέραιου αριθμού μεταξύ του 2 και του √n. Οι αλγόριθμοι που είναι πολύ πιο αποτελεσματικοί από τη δοκιμαστική διαίρεση έχουν επινοηθεί για να ελέγχουμε αν μεγαλύτεροι αριθμοί είναι πρώτοι. Ιδιαίτερα γρήγορες μέθοδοι είναι διαθέσιμες για αριθμούς ειδικών μορφών, όπως είναι αριθμοί Μερσέν. Ο μεγαλύτερος γνωστός πρώτος αριθμός από τον Ιανουάριο του 2016 έχει 22.338.618 δεκαδικά ψηφία.
Υπάρχουν άπειροι σε πλήθος πρώτοι αριθμοί, όπως απέδειξε ο Ευκλείδης περίπου στο 300 π.Χ. Δεν υπάρχει κανένας γνωστός τύπος ο οποίος να διαχωρίζει όλους τους πρώτους αριθμούς από τους σύνθετους. Ωστόσο, η κατανομή των πρώτων αριθμών, όπως λέμε τη στατιστική συμπεριφορά των πρώτων γενικά, μπορεί να μοντελοποιηθεί. Το πρώτο αποτέλεσμα προς αυτή την κατεύθυνση είναι το θεώρημα πρώτων αριθμών, το οποίο αποδείχτηκε στα τέλη του 19ου αιώνα, το οποίο λέει ότι η πιθανότητα ενός τυχαία επιλεγμένου αριθμού n να είναι πρώτος είναι αντιστρόφως ανάλογη του πλήθους των ψηφίων ή του λογαρίθμου του n.
Οι πρώτοι αριθμοί είναι ένα από τα αντικείμενα της θεωρίας αριθμών και είναι μια πολύ ενεργή ερευνητικά περιοχή των μαθηματικών. Πολλά ερωτήματα γύρω από τους πρώτους αριθμούς παραμένουν ανοιχτά, όπως η εικασία του Ρίμαν, η εικασία του Γκόλντμπαχ, η οποία λέει ότι κάθε άρτιος ακέραιος μεγαλύτερος του 2 μπορεί να γραφεί ως άθροισμα δύο πρώτων και η εικασία των διδύμων πρώτων, η οποία λέει ότι υπάρχουν άπειρα σε πλήθος ζευγάρια πρώτων των οποίων η διαφορά είναι 2. Τέτοιες ερωτήσεις οδήγησαν στην ανάπτυξη διάφορων κλάδων της θεωρίας αριθμών, εστιάζοντας στην αναλυτική ή αλγεβρική πλευρά των αριθμών. Οι πρώτοι χρησιμοποιούνται σε πολλούς τομείς στην τεχνολογία πληροφοριών, όπως στην Κρυπτογράφηση Δημόσιου Κλειδιού, η οποία χρησιμοποιεί ιδιότητες, όπως τη δυσκολία να αναλύεις ένα μεγάλο αριθμό σε γινόμενο πρώτων αριθμών. Οι πρώτοι αριθμοί συμβάλλουν σε διάφορες γενικεύσεις σε άλλους μαθηματικούς τομείς, ιδίως στην άλγεβρα, όπως τα στοιχεία πρώτων και τα ιδανικά πρώτων.
Ορισμός και παραδείγματα
Ένας φυσικός αριθμός (όπως 1, 2, 3, 4, 5, κ.ο.κ.) ονομάζεται πρώτος ή πρώτος αριθμός αν έχει ακριβώς δύο θετικούς διαιρέτες, τον 1 και τον εαυτό του. Οι φυσικοί αριθμοί μεγαλύτεροι της μονάδας που δεν είναι πρώτοι ονομάζονται σύνθετοι.
Ο αριθμός 12 δεν είναι πρώτος, καθώς 12 αντικείμενα μπορούν να τοποθετηθούν σε 3 ισομεγέθεις στήλες με 4 αντικείμενα η καθεμία (μεταξύ άλλων τρόπων). 11 αντικείμενα δεν μπορούν να τοποθετηθούν σε αρκετές ισομεγέθεις στήλες με παραπάνω από ένα αντικείμενο σε καθεμία χωρίς να περισσεύουν κάποια παραπάνω αντικείμενα (υπόλοιπο). Επομένως, ο αριθμός 11 είναι πρώτος.
Μεταξύ των αριθμών 1 και 6, οι αριθμοί 2, 3 και 5 είναι πρώτοι, ενώ οι αριθμοί 1, 4 και 6 δεν είναι πρώτοι. Ο 1 εξαιρείται από τους πρώτους αριθμούς για τους λόγους που εξηγούνται παρακάτω. Ο 2 είναι πρώτος αριθμός, διότι οι μόνοι φυσικοί αριθμοί που τον διαιρούν είναι οι 1 και 2. Στη συνέχεια, ο 3 είναι πρώτος επίσης επειδή οι 1 και 3 διαιρούν τον 3 χωρίς υπόλοιπο, αλλά ο 3 διαιρείται από το 2 με υπόλοιπο 1. Έτσι, ο 3 είναι πρώτος. Ωστόσο, ο 4 είναι σύνθετος, αφού ο 2 είναι ένας άλλος αριθμός (εκτός των 1 και 4) που διαιρεί τον 4 χωρίς υπόλοιπο:
4 = 2 · 2.
Ο 5 είναι επίσης πρώτος, επειδή κανένας από τους αριθμούς 2, 3, 4 δε διαιρεί τον 5. Στη συνέχεια, ο 6 διαιρείται από τους 2 και 3, αφού
6 = 2 · 3.
Άρα, ο 6 δεν είναι πρώτος. Η εικόνα στα δεξιά απεικονίζει ότι ο 12 δεν είναι πρώτος: 12 = 3 · 4. Κανένας άρτιος αριθμός μεγαλύτερος του 2 δεν είναι πρώτος, επειδή εξ ορισμού κάθε τέτοιος αριθμός n έχει τουλάχιστον τρεις διαφορετικούς διαιρέτες, τους 1, 2 και n. Αυτό συνεπάγεται ότι ο n δεν είναι πρώτος. Επομένως, ο όρος περιττός πρώτος αναφέρεται σε κάθε πρώτο αριθμό μεγαλύτερο του 2. Ανάλογα, όλοι οι πρώτοι μεγαλύτεροι του 5, γραμμένοι στο σύνηθες δεκαδικό σύστημα, τελειώνουν σε 1, 3, 7 ή 9, αφού οι άρτιοι αριθμοί είναι πολλαπλάσια του 2 και οι αριθμοί που τελειώνουν σε 0 ή 5 είναι πολλαπλάσια του 5.
Αν ο n είναι ένας φυσικός αριθμός, τότε οι αριθμοί 1 και n τον διαιρούν χωρίς υπόλοιπο. Συνεπώς, η προϋπόθεση ένας αριθμός να είναι πρώτος μπορεί να επαναδιατυπωθεί ως εξής: ένας αριθμός είναι πρώτος αν είναι μεγαλύτερος του 1 και αν κανείς από τους
2, 3, ..., n-1
δε διαιρεί τον n (χωρίς υπόλοιπο). Επιπλέον, ένας άλλος τρόπος να πούμε το ίδιο είναι: ένας αριθμός n > 1 είναι πρώτος αν δε μπορεί να γραφεί ως γινόμενο δύο ακεραίων α και b, όπου α και b είναι μεγαλύτεροι του 1:
n = α · b.
Με άλλα λόγια, ο n είναι πρώτος αν n αντικείμενα δεν μπορούν να διαιρεθούν σε μικρότερες ισομεγέθεις ομάδες με παραπάνω από ένα αντικείμενα.
Οι μικρότεροι 168 πρώτοι αριθμοί (όλοι οι πρώτοι αριθμοί μικρότεροι του 1000) είναι οι εξής:
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, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997.
Το σύνολο όλων των πρώτων αριθμών συνήθως συμβολίζεται με P.
Θεμελιώδες θεώρημα της αριθμητικής
Βασικό άρθρο : Θεμελιώδες θεώρημα της αριθμητικής
Η τεράστια σημασία των πρώτων αριθμών για τη θεωρία αριθμών και τα μαθηματικά γενικότερα πηγάζει από το θεμελιώδες θεώρημα της αριθμητικής, το οποίο αναφέρει ότι κάθε θετικός ακέραιος μεγαλύτερος του 1 μπορεί να γραφεί ως γινόμενο ενός ή περισσότερων πρώτων κατά ένα μοναδικό τρόπο εκτός από τη σειρά διάταξης των παραγόντων που είναι πρώτοι αριθμοί. Οι πρώτοι μπορούν έτσι να θεωρηθούν βασικά δομικά στοιχεία των φυσικών αριθμών. Για παράδειγμα:
23244 = 2 · 2 · 3 · 13 · 149 = 22 · 3 · 13 · 149. (22 συμβολίζει το τετράγωνο ή τη δεύτερη δύναμη του 2.)
Όπως και στο παραπάνω παράδειγμα, ο ίδιος παράγοντας πρώτου αριθμού μπορεί να συναντηθεί πολλές φορές. Μια αποσύνθεση:
n = p1 · p2 · ... · pt
ενός αριθμού n σε (πεπερασμένου πλήθους) πρώτους παράγοντες p1, p2, ..., pt ονομάζεται παραγοντοποίηση του n σε πρώτους παράγοντες. Το θεμελιώδες θεώρημα της αριθμητικής μπορεί να επαναδιατυπωθεί έτσι, ώστε να λέει ότι κάθε παραγοντοποίηση σε πρώτους αριθμούς θα είναι πανομοιότυπη εκτός από τη σειρά διάταξης των παραγόντων. Έτσι, μολονότι υπάρχουν πολλοί αλγόριθμοι παραγοντοποίησης με παράγοντες πρώτους αριθμούς για να το κάνουμε αυτό στην πράξη για μεγαλύτερους αριθμούς, στο τέλος όλοι οι αλγόριθμοι θα αποδίδουν το ίδιο αποτέλεσμα.
Αν p είναι ένας πρώτος αριθμός και ο p διαιρεί ένα γινόμενο αb , όπου α, b είναι ακέραιοι, τότε ισχύει ότι ο p διαιρεί τον α ή ο p διαιρεί τον b. Αυτή η πρόταση είναι γνωστή ως το λήμμα του Ευκλείδη. Το λήμμα του Ευκλείδη χρησιμοποιείται σε μερικές αποδείξεις για να αποδειχθεί η μοναδικότητα της παραγοντοποίησης ενός αριθμού σε πρώτους παράγοντες.
Ο αριθμός 1 δεν είναι πρώτος
Οι αρχαίοι Έλληνες δε θεωρούσαν τον 1 ούτε ως αριθμό κι έτσι δε τον θεωρούσαν ούτε ως πρώτο. Ωστόσο, στο 19ο αιώνα πολλοί μαθηματικοί θεωρούσαν τον 1 ως πρώτο αριθμό. Για παράδειγμα, η λίστα του Ντέρικ Νόρμαν Λέμερ που περιείχε πρώτους αριθμούς ως το 10,006,721 και εκδόθηκε μέχρι και το 1956, άρχιζε με τον 1 ως πρώτο αριθμό. Λέγεται ότι ο Ανρί Λεμπέσγκ είναι ο τελευταίος επαγγελματίας μαθηματικός που θεωρεί τον 1 ως πρώτο αριθμό. Παρόλο που ένα μεγάλο τμήμα των μαθηματικών είναι σωστό με τη θεωρία του 1 ως πρώτου αριθμού, το παραπάνω θεμελιώδες θεώρημα της αριθμητικής δε στέκει όπως είναι διατυπωμένο. Για παράδειγμα, ο αριθμός 15 μπορεί να παραγοντοποιηθεί ως 3 · 5 ή 1 · 3 · 5. Αν ο 1 ήταν πρώτος, τότε αυτές οι δύο εκφράσεις θα παρίσταναν διαφορετικές παραγοντοποιήσεις του 15 σε πρώτους αριθμούς κι έτσι το θεώρημα θα έπρεπε να τροποποιηθεί. Επιπρόσθετα, οι πρώτοι αριθμοί έχουν αρκετές ιδιότητες, τις οποίες ο αριθμός 1 δεν έχει, όπως τη σχέση του αριθμού με την αντίστοιχη τιμή του στη συνάρτηση του Όιλερ ή στη συνάρτηση του αθροίσματος των διαιρετών.
Ιστορία
Υπάρχουν ενδείξεις σε διασωθείσες επιγραφές των αρχαίων Αιγυπτίων ότι είχαν κάποια γνώση πρώτων αριθμών: οι επεκτάσεις του αιγυπτιακού κλάσματος στον πάπυρο του Ριντ, για παράδειγμα, έχουν αρκετά διαφορετικούς τύπους για πρώτους και για σύνθετους αριθμούς. Ωστόσο, οι πιο πρώιμες διασωθείσες επιγραφές σαφούς μελέτης των πρώτων αριθμών προέρχονται από τους αρχαίους Έλληνες. Τα στοιχεία του Ευκλείδη (περίπου στο 300 π.Χ.) περιέχουν σημαντικά θεωρήματα για τους πρώτους αριθμούς, συμπεριλαμβανομένων της απειρίας των πρώτων αριθμών και του θεμελιώδους θεωρήματος της αριθμητικής. Ο Ευκλείδης επίσης απέδειξε πώς μπορούμε να κατασκευάσουμε έναν τέλειο αριθμό από ένα πρώτο Μερσέν αριθμό. Το κόσκινο του Ερατοσθένη, το οποίο αποδίδεται στον Ερατοσθένη, είναι μια απλή μέθοδος να υπολογίσουμε τους πρώτους, παρόλο που οι μεγάλοι πρώτοι δεν υπολογίζονται σήμερα με τους υπολογιστές με αυτό τον τρόπο.
Μετά τους Έλληνες, λίγα πράγματα συνέβησαν με την έρευνα των πρώτων αριθμών μέχρι τον 17ο αιώνα. Το 1640 ο Πιέρ ντε Φερμά διατύπωσε (χωρίς απόδειξη) το μικρό θεώρημα του Φερμά (αργότερα αποδείχθηκε από τους Λάιμπνιτς και Όιλερ). Ο Φερμά υπέθεσε ότι όλοι οι αριθμοί της μορφής 22n + 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 πρώτων αριθμών. Η ιδέα - κλειδί είναι να θεωρήσουμε το γινόμενο όλων αυτών των αριθμών συν ένα:
\( N = 1 + \prod_{p\in S} p. . \)
Όπως κάθε άλλος φυσικός αριθμός, ο Ν μπορεί να διαιρεθεί από τουλάχιστον ένα πρώτο αριθμό (είναι πιθανό ο Ν να είναι πρώτος).
Κανένας από τους πρώτους αριθμούς οι οποίοι διαιρούν τον Ν δεν μπορεί να είναι στοιχείο του πεπερασμένου συνόλου S των πρώτων αριθμών με το οποίο ξεκινήσαμε, επειδή διαιρώντας τον Ν με οποιοδήποτε από αυτούς τους πρώτους αριθμούς αφήνει υπόλοιπο 1. Επομένως, οι πρώτοι από τους οποίους ο Ν διαιρείται είναι επιπλέον πρώτοι εκτός από αυτόν με τον οποίο ξεκινήσαμε. Έτσι κάθε πεπερασμένο σύνολο πρώτων αριθμών μπορεί να επεκταθεί σε ένα μεγαλύτερο πεπερασμένο σύνολο πρώτων αριθμών.
Συχνά αναφέρεται εσφαλμένα ότι ο Ευκλείδης ξεκινάει με την υπόθεση ότι αρχικά το σύνολο που θεωρούμε περιέχει όλους τους πρώτους αριθμούς, καταλήγοντας σε μια αντίφαση ή ότι το σύνολο περιέχει ακριβώς τους n μικρότερους πρώτους αριθμούς και όχι κάθε πεπερασμένο σύνολο πρώτων αριθμών. Σήμερα, το γινόμενο των μικρότερων n πρώτων αριθμών συν ένα συμβατικά ονομάζεται ο n-οστός αριθμός του Ευκλείδη.
Η αναλυτική απόδειξη του Όιλερ
Στην απόδειξη του Όιλερ χρησιμοποιείται το άθροισμα των αντίστροφων των πρώτων αριθμών,
\( S(p) = \frac 1 2 + \frac 1 3 + \frac 1 5 + \frac 1 7 + \cdots + \frac 1 p.. \)
Αυτό το άθροισμα γίνεται μεγαλύτερο από κάθε πραγματικό αριθμό με την προϋπόθεση ότι ο p είναι αρκετά μεγάλος. Αυτό δείχνει ότι υπάρχουν απείρως πολλοί πρώτοι αριθμοί, αφού ειδάλλως αυτό το άθροισμα θα μεγάλωνε μόνο μέχρι να φτάσουμε στο μεγαλύτερο πρώτο αριθμό p. Η αύξηση του S(p) υπολογίζεται από το δεύτερο θεώρημα του Μερσέν. Σε σύγκριση με το παραπάνω άθροισμα, παρατηρούμε ότι το άθροισμα
\( \frac 1 {1^2} + \frac 1 {2^2} + \frac 1 {3^2} + \cdots + \frac 1 {n^2} = \sum_{i=1}^n \frac 1 {i^2} \)
δεν τείνει στο άπειρο, καθώς το n τείνει στο άπειρο. Με αυτή την έννοια, οι πρώτοι αριθμοί εμφανίζονται πιο συχνά από τα τετράγωνα των φυσικών αριθμών. Το θεώρημα του Μπραν αναφέρει ότι το άθροισμα των αντίστροφων δύο διδύμων πρώτων αριθμών,
\( \left( {\frac{1}{3} + \frac{1}{5}} \right) + \left( {\frac{1}{5} + \frac{1}{7}} \right) + \left( {\frac{1}{{11}} + \frac{1}{{13}}} \right) + \cdots = \sum\limits_{ \begin{smallmatrix} p \text{ prime, } \\ p + 2 \text { prime} \end{smallmatrix}} {\left( {\frac{1}{p} + \frac{1}{{p + 2}}} \right)}, \)
είναι πεπερασμένο.
Αναγνώριση πρώτου αριθμού και παραγοντοποίηση ακεραίου
Υπάρχουν ποικίλες μέθοδοι για να προσδιορίσουμε αν ένας αριθμός 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} είναι της τάξης \sqrt{n} / \ln(\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 για πρακτικά μεγέθη. Οι αιτιοκρατικές μέθοδοι είναι τυπικά πιο αργές από τις πιθανοτικές κι έτσι οι τελευταίες εφαρμόζονται πρώτες πριν χρησιμοποιηθούν οι πιο χρονοβόρες αιτιοκρατικές μέθοδοι.
Ειδικοί αλγόριθμοι και ο μεγαλύτερος γνωστός πρώτος αριθμός
Κατασκευή ενός κανονικού πενταγώνου. Ο 5 είναι ένας πρώτος Fermat αριθμός.
Εκτός από τις παραπάνω δοκιμές για τους πρώτους αριθμούς για κάθε φυσικό αριθμό n, ένα πλήθος πολύ περισσότερο αποτελεσματικών μεθόδων για πρώτους αριθμούς είναι διαθέσιμο για συγκεκριμένους αριθμούς. Για παράδειγμα, για να εκτελεστεί η μέθοδος του Lucas για τους πρώτους απαιτείται η γνώση των παραγόντων που είναι πρώτοι αριθμοί του αριθμού n - 1, ενώ η μέθοδος των Λούκας-Λέμερ για τους πρώτους αριθμούς απαιτεί τους παράγοντες που είναι πρώτοι αριθμοί του αριθμού n + 1 ως δεδομένο. Για παράδειγμα, αυτές οι μέθοδοι μπορούν να εφαρμοστούν για να ελέγξουμε αν οι αριθμοί
n! ± 1 = 1 · 2 · 3 · ... · n ± 1
είναι πρώτοι. Οι πρώτοι αριθμοί αυτής της μορφής είναι γνωστοί ως παραγοντικοί πρώτοι αριθμοί. Άλλοι πρώτοι αριθμοί, όπου είτε ο p + 1 ή ο p - 1 είναι μιας συγκεκριμένης μορφής περιλαμβάνουν τους πρώτους αριθμούς Σόφι Ζερμέν (πρώτοι αριθμοί της μορφής 2p + 1, όπου p είναι πρώτος), τους αρχέγονους πρώτους αριθμούς, τους πρώτους αριθμούς του Φερμά και τους πρώτους αριθμούς του Μερσέν, οι οποίοι είναι πρώτοι αριθμοί της μορφής 2p - 1, όπου p είναι ένας τυχαίος πρώτος αριθμός. Η μέθοδος των Λούκας-Λέμερ είναι εξαιρετικά γρήγορη για τους πρώτους αριθμούς της μορφής αυτής. Για το λόγο αυτό ο μεγαλύτερος γνωστός πρώτος αριθμός έχει γίνει σχεδόν ένας πρώτος Μερσέν από τότε που ανακαλύφθηκαν οι υπολογιστές.
Οι πρώτοι αριθμοί Φερμά είναι της μορφής
\( F_k = 2^{2^k} + 1, \)
όπου k είναι ένας τυχαίος φυσικός αριθμός. Έτσι ονομάστηκαν οι αριθμοί αυτής της μορφής, αφού ο Πιέρ ντε Φερμά υπέθεσε ότι όλοι οι Fk είναι πρώτοι. Η πρόταση αυτή βασίστηκε στο γεγονός ότι οι οι πέντε πρώτοι τέτοιοι αριθμοί 3, 5, 17, 257 και 65,537 είναι πρώτοι. Ωστόσο, ο F5=4294967297=641×6700417 είναι σύνθετος και το ίδιο συμβαίνει για τους υπόλοιπους αριθμούς Φερμά, οι οποίοι έχουν ελεγχθεί από το 2011. Ένα κανονικό n-γώνιο είναι κατασκευάσιμο χρησιμοποιώντας χάρακα και διαβήτη αν και μόνο αν
n = 2i · m,
όπου m είναι ένας οποιοσδήποτε αριθμός από τους πρώτους Φερμά αριθμούς και i είναι ένας οποιοσδήποτε φυσικός αριθμός ή το μηδέν.
Ο παρακάτω πίνακας δίνει τους μεγαλύτερους γνωστούς πρώτους αριθμούς των προαναφερθέντων τύπων. Κάποιοι από αυτούς τους πρώτους βρέθηκαν χρησιμοποιώντας κατανεμημένα συστήματα πληροφορικής.
| Τύπος | Πρώτος αριθμός | Πλήθος δεκαδικών ψηφίων | Ημερομηνία | Ανακαλύφθηκε από |
|---|---|---|---|---|
| πρώτος Μερσέν | 274,207,281 − 1 | 22,338,618 | 7 Ιανουαρίου 2016 | Great Internet Mersenne Prime Search |
| όχι πρώτος Μερσέν (αριθμός Προθ) | 19,249 × 213,018,586 + 1 | 3,918,990 | 26 Μαρτίου 2007 | Seventeen or Bust |
| παραγοντικός πρώτος | 150209! + 1 | 712,355 | Οκτώβριος 2011 | PrimeGrid[1] |
| αρχέγονος πρώτος | 1098133# - 1 | 476,311 | Μάρτιος 2012 | PrimeGrid[2] |
| δίδυμοι πρώτοι αριθμοί | 3756801695685 × 2666669 ± 1 | 200,700 | Δεκέμβριος 2011 | PrimeGrid[3] |
Εύρεση πρώτων
Κόσκινο του Ερατοσθένη
Η εύρεση των πρώτων αριθμών απασχόλησε από την αρχαιότητα τους μαθηματικούς. Ένας από τους πιο απλούς αλλά και αργούς τρόπους για (μαζική) εύρεση πολλών πρώτων είναι το λεγόμενο κόσκινο του Ερατοσθένη: Στο σύνολο των φυσικών αριθμών - πρακτικά έως κάποιο μεγάλο αριθμό Ν - αρχίζουμε και αποκλείουμε πρώτα τα πολλαπλάσια του 2 μετά τα πολλαπλάσια του επόμενου μη διαγραμμένου αριθμού κ.ο.κ. έως το Ν. Παρατηρούμε ότι όλο και λιγότερους αριθμούς θα βρίσκουμε προς διαγραφή. Οι αριθμοί που θα απομείνουν είναι όλοι πρώτοι. Το κόσκινο του Ερατοσθένη είναι ένας αργός αλγόριθμος για το αν ένας συγκεκριμένος αριθμός Ν είναι πρώτος ή όχι, διότι μεταξύ άλλων απαιτεί ουσιαστικά και την εύρεση όλων των πρώτων μικρότερων ίσων του \( \sqrt{N} \) (αν ένας αριθμός Ν δεν έχει διαιρέτες μικρότερους ίσους του \sqrt{N}, τότε είναι πρώτος).
Οπτικό κόσκινο Matiyasevich-Stechkin
Στις 14/2/1999 οι Γιούρι Ματιγιάσεβιτς και Μπόρις Στέκιν δημοσίευσαν στο διαδίκτυο το οπτικό κόσκινο των πρώτων αριθμών. Τα σημεία της παραβολής x=y^2 με ακέραιες συντεταγμένες ορίζουν χορδές που τέμνουν τον οριζόντιο άξονα x΄x σε σημεία της μορφής (αβ,0) όπου α,β ακέραιοι κι επομένως σαρώνουν όλους τους σύνθετους θετικούς ακέραιους.
Αλγόριθμοι εύρεσης πρώτων
Παρατίθενται μερικοί αλγόριθμοι (κατά σειρά ταχύτητας ή και απλότητας) για την εύρεση αν ο Ν>=2 είναι πρώτος. Η σειρά επίσης αυτών των αλγορίθμων είναι παιδευτική για την εισαγωγή σε μια σειρά από προγράμματα για ηλεκτρονικούς υπολογιστές.
Απλός 1 - από τον ορισμό του πρώτου αριθμού
Εξετάζουμε διαδοχικά όλους τους ακέραιους Μ < Ν
Μόλις βρεθεί διαιρέτης του Ν σταματάμε και ο Ν δεν είναι πρώτος
Αν εξαντληθούν οι Μ χωρίς να βρεθεί διαιρέτης, τότε ο Ν είναι πρώτος
Απλός 2
Βασιζόμενοι στην παρατήρηση ότι κανένας αριθμός Ν δεν έχει διαιρέτη μεγαλύτερο του Ν/2, τροποποιούμε τον παραπάνω αλγόριθμο εξετάζοντας όλους τους αριθμούς Μ < Ν/2, διπλασιάζοντας έτσι την ταχύτητα σε σχέση με τον "Απλό 1".
Απλός 3
Παρατηρούμε ότι αν ένας αριθμός Ν δεν είναι πρώτος τότε έχει (τουλάχιστον) δύο διαιρέτες μεγαλύτερους από 1. Σε αυτήν την περίπτωση τουλάχιστον ένας διαιρέτης είναι μικρότερος από την τετραγωνική ρίζα του αριθμού. Τροποποιούμε τον αλγόριθμο 2 εξετάζοντας όλους τους αριθμούς Μ που είναι μικρότεροι από την τετραγωνική ρίζα του N, αν η τελευταία δεν είναι ακέραιος. Αλλιώς ο αριθμός δεν είναι πρώτος, επειδή τον διαιρεί και η τετραγωνική του ρίζα.
Απλός 4
Εφαρμόζοντας το Θεώρημα του Ουίλσον μπορούμε να εξετάσουμε, αν ένας αριθμός Ν είναι πρώτος ή όχι. Σύμφωνα με το θεώρημα αυτό ο Ν είναι πρώτος αν και μόνο αν ισχύει
\( (N-1)!\ \equiv\ -1\ (\mbox{mod}\ N), \)
αν δηλαδή το υπόλοιπο της διαίρεσης του Ν-1 παραγοντικό με το Ν, είναι ίσο με το υπόλοιπο της διαίρεσης του -1 με το N.
Η μέθοδος αυτή δεν εφαρμόζεται για μεγάλο Ν, αφού είναι δύσκολο να υπολογιστεί το παραγοντικό.
Ο μεγαλύτερος γνωστός πρώτος αριθμός
Μέχρι τον Μάρτιο του 2016, ο μεγαλύτερος γνωστός πρώτος αριθμός είναι ο:
\( M_{49}=2^{74,207,281}-1 \)
Ο δεύτερος μεγαλύτερος πρώτος είναι:
\( M_{48}=2^{57,885,161}-1 \)
και η ανακάλυψη του, έγινε στις 25 Ιανουαρίου 2013, μέσω του διαδικτυακού προγράμματος κατανεμημένης επεξεργασίας GIMPS (Great Internet Mersenne Prime Search).[4] Ο αριθμός αυτός έχει 17.425.179 ψηφία (ο δεύτερος με πάνω από 10 εκατομμύρια ψηφία) και έχει την πρόσθετη ιδιότητα να είναι ο 48ος Μερσέν πρώτος (Mersenne prime) που ανακαλύφθηκε. Ο 47ος Μερσέν πρώτος, ο 243,112,609 − 1, ανακαλύφθηκε στις 25 Αυγούστου του 2008.
Στο πρόσφατο παρελθόν, όλοι οι πρώτοι που ανακαλύφθηκαν ήταν Μερσέν πρώτοι.[5]
Επίσης, για τον πρώτο πρώτο αριθμό που ανακαλύφθηκε και είχε πάνω από 10.000.000 ψηφία, δόθηκαν 100.000 δολάρια!
Ιδιότητες πρώτων αριθμών
Αν ο p είναι πρώτος και διαιρεί το γινόμενο ab γιά κάποιους ακέραιους a, b τότε ο p διαιρεί το a ή το b. (Ευκλείδης)
Αν p πρώτος και a ακέραιος, τότε το ap − a διαιρείται από το p (Μικρό Θεώρημα του Φερμά).
Ένας ακέραιος p > 1 είναι πρώτος αν και μόνο αν p - 1 παραγοντικό + 1 δηλ. το (p − 1)! + 1 διαιρείται από το p (Θεώρημα του Ουίλσον).
Όλοι οι πρώτοι αριθμοί στο δεκαδικό σύστημα, εκτός του 2 και του 5, έχουν ως τελευταίο ψηφίο ένα από τα 1, 3, 7 ή 9, διότι οι αριθμοί που τελειώνουν σε 0, 2, 4, 6 και 8 είναι πολλαπλάσια του 2 ενώ οι αριθμοί που τελειώνουν σε 0 ή 5 είναι πολλαπλάσια του 5.
Κατανομή
Η κατανομή των πρώτων αριθμών γενικά, όπως η ερώτηση πόσοι πρώτοι αριθμοί είναι μικρότεροι από ένα δοθέν πρώτο αριθμό, πόσο μεγάλο είναι το όριο, περιγράφεται από το θεώρημα των πρώτων αριθμών, αλλά δεν είναι γνωστός κανένας τύπος που να είναι αποτελεσματικός για το n-οστό πρώτο αριθμό.
Υπάρχουν αυθαίρετα μεγάλες ακολουθίες διαδοχικών μη πρώτων αριθμών, όπως για κάθε θετικό ακέραιο αριθμό n οι n διαδοχικοί ακέραιοι από (n + 1)! + 2 ως (n + 1)! + n + 1 (συμπεριλαμβανομένης και της τελικής τιμής) είναι όλοι σύνθετοι αριθμοί (αφού (n + 1)! + k διαιρείται από τον k για k από 2 ως n + 1).
Το θεώρημα του Ντίριχλετ για τις αριθμητικές προόδους, στη βασική του μορφή, ισχυρίζεται ότι τα γραμμικά πολυώνυμα
p(n) = α + bn
με τους σχετικά πρώτους α και b να παίρνουν άπειρα πολλές τιμές πρώτων αριθμών. Ισχυρότερες μορφές του θεωρήματος αναφέρουν ότι το άθροισμα των τιμών που επιστρέφει το πολυώνυμο αυτών των τιμών που είναι πρώτοι αριθμοί αποκλίνει και αυτές οι διαφορές που υπάρχουν στα πολυώνυμα με το ίδιο b έχουν περίπου τις ίδιες αναλογίες των πρώτων αριθμών.
Η αντίστοιχη ερώτηση για τα τετραγωνικά πολυώνυμα είναι λιγότερο κατανοητή.
Τύποι των πρώτων αριθμών
Δεν υπάρχει κανένας γνωστός αποτελεσματικός τύπος για τους πρώτους αριθμούς. Για παράδειγμα, το θεώρημα του Μιλς και ένα θεώρημα του Ράιτ ισχυρίζονται ότι υπάρχουν πραγματικές σταθερές Α > 1 και μ, τέτοιες ώστε
\( \left \lfloor A^{3^{n}}\right \rfloor \text{ and } \left \lfloor 2^{\dots^{2^{2^\mu}}} \right \rfloor \)
να είναι πρώτοι αριθμοί για κάθε φυσικό αριθμό n. Εδώ \lfloor - \rfloor αντιπροσωπεύει ακέραιο μέρος της έκφρασης, δηλαδή το μεγαλύτερο ακέραιο που δεν είναι μεγαλύτερος από τον αριθμό που είναι στις αγκύλες. Ο τελευταίος τύπος μπορεί να αποδειχθεί χρησιμοποιώντας το αξίωμα του Μπέρτραντ (αποδεδειγμένο πρώτα από τον Παφνούτι Λβόβιτς Τσέμπισσιοφ), το οποίο αναφέρει ότι πάντα υπάρχει τουλάχιστον ένας πρώτος αριθμός p με n < p < 2n - 2, για κάθε φυσικό αριθμό n > 3. Ωστόσο, για να υπολογίσουμε τον Α ή τον μ απαιτείται η γνώση των απείρως πολλών πρώτων αριθμών με τους οποίους θα ξεκινήσουμε. Ένας άλλος τύπος βασίζεται στο θεώρημα του Ουίλσον και παράγει τον αριθμό 2 πολλές φορές και όλους τους άλλους πρώτους αριθμούς ακριβώς μία φορά.
Δεν υπάρχει κανένα μη σταθερό πολυώνυμο, ακόμη και σε αρκετές μεταβλητές, οι οποίες παίρνουν ως τιμές μόνο πρώτους αριθμούς. Ωστόσο, υπάρχει ένα σύνολο διοφαντικών εξισώσεων σε 9 μεταβλητές και μια παράμετρος με την εξής ιδιότητα: η παράμετρος είναι πρώτος αριθμός αν και μόνο αν το σύστημα που προκύπτει από τις εξισώσεις έχει μία λύση στους φυσικούς αριθμούς. Αυτό θα μπορούσε να χρησιμοποιηθεί για να αποκτήσει ένα απλό τύπο με την ιδιότητα ότι όλες οι θετικές τιμές του είναι πρώτοι αριθμοί.
Πλήθος των πρώτων αριθμών κάτω από ένα δοθέντα αριθμό
Ένα διάγραμμα που απεικονίζει την π(n) (μπλε), την n/ln(n) (πράσινη) και την Li(n) (κόκκινη)
Η συνάρτηση που καταμετράει τους πρώτους αριθμούς π(n) ορίζεται ως το πλήθος των πρώτων αριθμών μέχρι και τον n. Για παράδειγμα π(11) = 5, αφού υπάρχουν πέντε πρώτοι αριθμοί μικρότεροι ή ίσοι του 11. Υπάρχουν γνωστοί αλγόριθμοι για να υπολογίσουμε τις ακριβείς τιμές της συνάρτησης π(n) πιο γρήγορα από ότι να υπολογίζαμε αν κάθε αριθμός είναι πρώτος μέχρι και τον n. Το θεώρημα των πρώτων αριθμών αναφέρει ότι η π(n) δίνεται περίπου από τον τύπο
\( \pi(n) \approx \frac n {\ln n},, \)
με την έννοια ότι η αναλογία της π(n) με το κλάσμα του δεξιού μέλους τείνει στο 1, όταν ο n τείνει στο άπειρο. Αυτό συνεπάγεται ότι η πιθανότητα ένας αριθμός μικρότερος του n να είναι πρώτος είναι (περίπου) αντιστρόφως ανάλογη του πλήθους των ψηφίων του n. Ένας πιο ακριβής υπολογισμός για την π(n) δίνεται από το λογαριθμικό ολοκλήρωμα
\( \operatorname{Li}(n) = \int_2^n \frac{dt}{\ln t}. \)
Το θεώρημα πρώτων αριθμών συνεπάγεται ότι υπολογίζει το μέγεθος του 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.
Prime numbers (highlighted in red) in arithmetic progression modulo 9.
Το θεώρημα των Γκριν-Τάο δείχνει ότι υπάρχουν αυθαίρετα μεγάλες αριθμητικές πρόοδοι που περιέχουν πρώτους αριθμούς. Ένας περιττός πρώτος αριθμός p εκφράζεται ως το άθροισμα δύο τετραγώνων, p = x2 + y2, ακριβώς αν ο p συγκλίνει στο 1 με μέτρο 4.
Τιμές πρώτων αριθμών δευτεροβάθμιων πολυωνύμων
The Ulam spiral. Red pixels show prime numbers. Primes of the form 4n2 − 2n + 41 are highlighted in blue.
Ο Όιλερ σημείωσε ότι η συνάρτηση
n2 + n + 41
δίνει πρώτους αριθμούς για 0 ≤ n < 40, ένα γεγονός που οδηγεί βαθιά μέσα στην αλγεβρική θεωρία αριθμών και πιο συγκεκριμένα στους αριθμούς Χέεγκνερ. Για μεγαλύτερα n, η συνάρτηση δίνει σύνθετους αριθμούς. Η εικασία F των Χάρντι-Λίτλγουντ κάνει μια ασυμπτωτική πρόβλεψη για την πυκνότητα των πρώτων αριθμών μεταξύ των τιμών των δευτεροβάθμιων πολυωνύμων (με ακέραιους συντελεστές a, b και c)
\( f(n) = a x^2 + bx + c\, \)
Ωστόσο, η πρόοδος έχει αποδειχτεί δύσκολο να βρεθεί: κανένα δευτεροβάθμιο πολυώνυμο (με a ≠ 0) δεν είναι γνωστό να παίρνει απείρως πολλούς πρώτους αριθμούς ως τιμές. Η σπείρα του Ούλαμ απεικονίζει όλους τους φυσικούς αριθμούς με ένα σπειροειδές τρόπο. Οι πρώτοι αριθμοί μαζεύονται σε συγκεκριμένες διαγώνιες και όχι σε άλλες, γεγονός που υποδηλώνει ότι κάποια δευτεροβάθμια πολυώνυμα παίρνουν ως τιμές πρώτους αριθμούς πιο συχνά από άλλα.
Ανοικτά ερωτήματα
Η συνάρτηση ζήτα και η υπόθεση του Ρίμαν
Το σχέδιο της συνάρτησης ζήτα ζ(s). Στο s=1, η συνάρτηση έχει ένα πόλο, ο οποίος όπως λέμε τείνει στο άπειρο.
Η συνάρτηση ζήτα του Ρίμαν ζ(s) ορίζεται ως ένα άπειρο άθροισμα
\( \zeta(s)=\sum_{n=1}^\infin \frac{1}{n^s},\)
όπου s είναι ένας μιγαδικός αριθμός με πραγματικό μέρος μεγαλύτερο του 1. Είναι συνέπεια του θεμελιώδους θεωρήματος της αριθμητικής ότι αυτό το άθροισμα συμφωνεί με το άπειρο γινόμενο
\( \prod_{p \text{ prime}} \frac{1}{1-p^{-s}}.\)
Η συνάρτηση ζήτα είναι στενά συνδεδεμένη με τους πρώτους αριθμούς. Για παράδειγμα, το προαναφερθέν γεγονός ότι υπάρχουν άπειροι πρώτοι αριθμοί μπορεί επίσης να δειχθεί χρησιμοποιώντας τη συνάρτηση ζήτα: αν υπήρχαν πεπερασμένου του πλήθους πρώτοι αριθμοί, τότε η ζ(1) θα είχε μια πεπερασμένη τιμή. Ωστόσο, η αρμονική σειρά 1 + 1/2 + 1/3 + 1/4 + ... αποκλίνει (δηλαδή ξεπερνά κάθε δεδομένο αριθμό) κι έτσι πρέπει να υπάρχουν απείρως πολλοί πρώτοι αριθμοί. Ένα άλλο παράδειγμα της σημαντικότητας της συνάρτησης ζήτα και μια γεύση από τη σύγχρονη αλγεβρική θεωρία αριθμών είναι η παρακάτω ταυτότητα (πρόβλημα της Βασιλείας), σύμφωνα με τον Όιλερ,
\(\zeta(2) = \prod_{p} \frac{1}{1-p^{-2}}= \frac{\pi^2}{6}.\)
Η τιμή της ζ(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. Αυτές οι εικασίες είναι ειδικές περιπτώσεις της ευρείας υπόθεσης H του Σίντσελ. Η εικασία του Μπρόκαρντ λέει ότι υπάρχουν πάντα τουλάχιστον τέσσερις πρώτοι αριθμοί μεταξύ των τετραγώνων δύο διαδοχικών πρώτων αριθμών μεγαλύτερων του 2. Η εικασία του Λεγκρέντ αναφέρει ότι υπάρχει ένας πρώτος αριθμός μεταξύ n2 και (n + 1)2 για κάθε θετικό ακέραιο αριθμό n. Υπονοείται από την ισχυρότερη εικασία του Κράμερ.
Επιπλέον, ένα από τα ανοιχτά ερωτήματα της σύγχρονης θεωρίας αριθμών είναι το πρόβλημα της παραγοντοποίησης μεγάλων ακεραίων, δηλαδή της εύρεσης αλγορίθμου παραγοντοποίησης σε πολυωνυμικό χρόνο. Στην "σκιά" αυτού του προβλήματος αναπτύχθηκε η Κρυπτογράφηση Δημόσιου Κλειδιού και ειδικότερα του κρυπτοσυστήματος RSA.
Οι εικασίες του Γκόλντμπαχ
Κύριο λήμμα: Εικασία του Γκόλντμπαχ
Είναι πολύ γνωστή η πρώτη εικασία που διατύπωσε ο Κρίστιαν Γκόλντμπαχ 1690-1764, η οποία σχετίζεται με τους πρώτους αριθμούς. Ο Γκόλντμπαχ υποστήριξε ότι κάθε άρτιος αριθμός μεγαλύτερος του 2, μπορεί να γραφεί ως άθροισμα δύο πρώτων αριθμών. Η απόδειξη της παραπάνω εικασίας ταλανίζει ακόμα και σήμερα τους μαθηματικούς, καθώς παράλληλα οι υπολογιστές επιβεβαιώνουν την εικασία για όλο και μεγαλύτερους αριθμούς. Το 1998, η εικασία επιβεβαιώθηκε για αριθμούς μέχρις και της τάξης του \( 10^{14} \)
Η δεύτερη εικασία του Γκόλντμπαχ έγκειται στο ότι κάθε περιττός αριθμός μεγαλύτερος του 6 είναι άθροισμα τριών πρώτων αριθμών. Και αυτή η εικασία παραμένει αναπόδεικτη, αν και επιβεβαιώνεται από ηλεκτρονικούς υπολογιστές. Τυχόν απόδειξη της πρώτης εικασίας του Γκόλντμπαχ θα αποδείκνυε αμέσως και τη δεύτερη εικασία. Στη πρώτη εικασία γιατί <...μεγαλύτερος του 2;...> , 2=1+1 άθροισμα δύο Πρώτων ή να διατυπωθεί <.....ως άθροισμα δύο διαφορετικών Πρώτων ......>.
Εφαρμογές
Για πολύ καιρό, η θεωρία αριθμών γενικά και η μελέτη των πρώτων αριθμών συγκεκριμένα αποτελούσαν κλασικό παράδειγμα των καθαρών μαθηματικών, με καθόλου εφαρμογές έξω από το θεωρητικό κομμάτι. Πιο συγκεκριμένα, μαθηματικοί που ασχολήθηκαν με τη θεωρία αριθμών, όπως ο Βρετανός Γ. Χ. Χάρντι υπερηφανεύονταν ότι εργάζονταν πάνω σε κάτι που δεν είχε καμία στρατιωτική σημασία. Ωστόσο, αυτή η οπτική καταρρίφθηκε τη δεκαετία του 1970, όταν ανακοινώθηκε δημοσίως ότι οι πρώτοι αριθμοί μπορούσαν να χρησιμοποιηθούν ως βάση για τη δημιουργία αλγορίθμων κρυπτογραφίας δημοσίου κλειδιού. Οι πρώτοι αριθμοί επίσης χρησιμοποιήθηκαν για πίνακες κατακερματισμού και για γεννήτριες ψευδοτυχαίων αριθμών.
Μερικές μηχανές με στροφείο (rotor machines) σχεδιάστηκαν με ένα διαφορετικό πλήθος καρφιών σε κάθε στροφείο, με το πλήθος των καρφιών σε κάθε στροφείο να είτε πρώτος, ή σύνθετος στο πλήθος των καρφιών οποιουδήποτε άλλου στροφείου. Αυτό βοήθησε στη δημιουργία ενός πλήρους κύκλου πιθανών θέσεων στροφείων πριν την επανάληψη κάθε θέσης.
Ο Διεθνής Πρότυπος Αριθμός Βιβλίου δουλεύει με ένα ψηφίο ελέγχου, το οποίο εκμεταλλεύεται το γεγονός ότι ο αριθμός 11 είναι πρώτος αριθμός.
Αριθμητική modular ενός πρώτου αριθμού και πεπερασμένα σώματα
Η αριθμητική 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 και γράφουμε
\( 3 + 5 \equiv 1 \pmod 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, στην εξίσωση
\( 3 \cdot x \equiv 2 \pmod 6, \)
μια λύση του x, η οποία θα ήταν ανάλογη με 2/3, δεν μπορεί να βρεθεί, καθώς το ένα μπορεί να βρεθεί υπολογίζοντας 3 · 0, ..., 3 · 5 modulo 6. Το ιδιαίτερο χαρακτηριστικό των πρώτων αριθμών είναι το εξής: η διαίρεση είναι δυνατή στη modular αριθμητική αν και μόνο αν ο n είναι πρώτος αριθμός. Ισοδύναμα, ο n είναι πρώτος αριθμός αν και μόνο αν όλοι οι ακέραιοι m που ικανοποιούν την ανισότητα 2 ≤ m ≤ n − 1 είναι σχετικοί πρώτοι με τον n, δηλαδή ο μόνος κοινός διαιρέτης τους είναι το 1. Πράγματι, για n = 7, η εξίσωση
\( 3 \cdot x \equiv 2 \ \ (\operatorname{mod}\ 7), \)
έχει μοναδική λύση, τη x = 3. Εξαιτίας αυτού, για κάθε πρώτο αριθμό p, το Z/pZ (μερικές φορές σημειώνεται ως Fp) ονομάζεται σώμα ή πιο συγκεκριμένα πεπερασμένο σώμα, αφού περιέχει πεπερασμένου του πλήθους, δηλαδή p, στοιχεία. Ένα πλήθος θεωρημάτων μπορούν να προέρχονται από τη μελέτη του Fp με αυτό τον αφηρημένο τρόπο. Για παράδειγμα, το μικρό θεώρημα του Fermat, το οποίο αναφέρει ότι
\( a^{p-1} \equiv 1 (\operatorname{mod}\ p) \)
για κάθε ακέραιο αριθμό a που δε διαιρείται από τον p, μπορεί να αποδειχθεί χρησιμοποιώντας αυτές τις έννοιες. Αυτό συνεπάγεται ότι
\( \sum_{a=1}^{p-1} a^{p-1} \equiv (p-1) \cdot 1 \equiv -1 \pmod 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).
Κρυπτογράφηση δημόσιου κλειδιού
Αρκετοί αλγόριθμοι κρυπτογράφησης δημόσιου κλειδιού, όπως ο RSA και η ανταλλαγή κλειδιών των Ντίφι-Χέλμαν, βασίζονται στους μεγάλους πρώτους αριθμούς (για παράδειγμα πρώτοι αριθμοί μεγέθους 512 bit χρησιμοποιούνται συχνά για τον RSA και πρώτοι αριθμοί μεγέθους 1024 bit είναι συνήθεις για τον αλγόριθμο Ντίφι–Χέλμαν.). Ο RSA βασίζεται στην υπόθεση ότι είναι πολύ πιο εύκολο (δηλαδή πιο αποτελεσματικό) να εκτελέσουμε πολλαπλασιασμό δύο (μεγάλων) αριθμών x και y από το να υπολογίσουμε τους x και y (υποτίθεται ότι είναι σχετικά πρώτοι) αν μόνο το γινόμενο xy είναι γνωστό. Η ανταλλαγή κλειδιών των Ντίφι-Χέλμαν βασίζεται στο γεγονός ότι υπάρχουν αποτελεσματικοί αλγόριθμοι για modular ύψωση σε δύναμη, ενώ η αντίστροφη λειτουργία του διακριτού λογαρίθμου υποτίθεται ότι είναι ένα δύσκολο πρόβλημα.
Οι πρώτοι αριθμοί στη φύση
Αναπόφευκτα, μερικοί από τους αριθμούς που συναντώνται στη φύση είναι πρώτοι. Ωστόσο, υπάρχουν σχετικά λίγα παραδείγματα αριθμών, οι οποίοι εμφανίζονται στη φύση, επειδή είναι πρώτοι.
Ένα παράδειγμα της χρήσης των πρώτων αριθμών στη φύση είναι ως εξελικτική στρατηγική που χρησιμοποιείται από τα τζιτζίκια του γένους Magicicada. Αυτά τα έντομα περνούν τον περισσότερο χρόνο της ζωής τους ως προνύμφες υπογείως. Τα έντομα αυτά μεγαλώνουν και στη συνέχεια βγαίνουν από τις φωλιές τους μετά από 13 ή 17 χρόνια, χρονικό σημείο από το οποίο θα αρχίσουν να πετάνε, να γεννάνε και μετά από λίγες εβδομάδες το πολύ πεθαίνουν. Θεωρείται ότι η λογική για αυτό είναι ότι τα διαστήματα πρώτων αριθμών μεταξύ καταστάσεων έκτακτης ανάγκης καθιστούν πολύ δύσκολο να εξελιχθούν τα αρπακτικά, οι οποίοι θα μπορούσαν να εξειδικευτούν ως θηρευτές των Magicicada. Αν τα έντομα αυτά δεν εμφανίζονταν σε διαστήματα πρώτων αριθμών, ας πούμε κάθε 12 χρόνια, τότε οι θηρευτές τους που θα εμφανίζονταν κάθε 2, 3, 4, 6 ή 12 χρόνια θα ήταν σίγουρο ότι θα τα συναντούσαν. Για πάνω από 200 χρόνια, ο μέσος όρος του πληθυσμού των αρπακτικών κατά τη διάρκεια της πιθανής γέννησης 14 και 15 ετών των τζιτζικιών θα ήταν έως και 2% υψηλότερα από ότι κατά τη διάρκεια γέννησής τους 13 και 17 ετών. Παρόλο που είναι μικρό, το πλεονέκτημα αυτό εμφανίζεται να είναι αρκετό για να οδηγηθούν στη φυσική επιλογή υπέρ της προνομιακής αρίθμησης του κύκλου ζωής για αυτά τα έντομα.
Αυτό είναι το πρόβλημα ότι τα μηδενικά της συνάρτηση ζήτα ζήτα συνάρτησης είναι συνδεδεμένα με τα επίπεδα ενέργειας των πολύπλοκων κβαντικών συστημάτων.
Γενικεύσεις
Η έννοια του πρώτου αριθμού είναι τόσο σημαντική που έχει γενικευτεί με διάφορους τρόπους σε ποικίλους τομείς των μαθηματικών. Γενικά, ο όρος "πρώτος" προσδιορίζει την ελαχιστοποίηση ή το διαχωρισμό ενός αντικειμένου στα βασικά του στοιχεία. Για παράδειγμα, το πεδίο των πρώτων αριθμών είναι το μικρότερο υποδιάστημα ενός διαστήματος F που περιέχει το 0 και το 1. Είναι είτε το σύνολο Q ή το πεπερασμένο σύνολο με p στοιχεία, εξ ου και η ονομασία. Συχνά ένας δεύτερος, πρόσθετος ορισμός προορίζεται από τη χρήση της λέξης πρώτος, δηλαδή ότι κάθε αντικείμενο μπορεί ουσιαστικά και μοναδικά να αναλυθεί στα βασικά χαρακτηριστικά του. Για παράδειγμα, στη θεωρία των κόμπων, ένας πρώτος (βασικός) κόμπος είναι ένας κόμπος, ο οποίος είναι αδιάσπαστος, με την έννοια ότι δεν μπορεί να γραφεί ως άθροισμα δύο τετριμμένων κόμπων. Κάθε κόμπος μπορεί να εκφραστεί μοναδικά ως ένα συνδεδεμένο άθροισμα βασικών (πρώτων) κόμπων. Άλλα παραδείγματα αυτού του τύπου είναι τα μοντέλα πρώτων αριθμών και οι πρώτοι αριθμοί τριπλής πολλαπλότητας.
Πρώτα στοιχεία στους δακτύλιους
Από τους πρώτους αριθμούς προκύπτουν δύο πιο γενικές έννοιες, οι οποίες εφαρμόζονται στα στοιχεία κάθε αντιμεταθετικού δακτυλίου R, μια αλγεβρική δομή, όπου ορίζονται η πρόσθεση, η αφαίρεση και ο πολλαπλασιασμός: πρώτα στοιχεία και στοιχεία που δεν ανάγονται. Ένα στοιχείο p του R ονομάζεται πρώτο στοιχείο αν δεν είναι ούτε μηδέν ούτε μονάδα (δηλαδή δεν έχει αντίστροφο στον πολλαπλασιασμό) και ικανοποιεί την παρακάτω προϋπόθεση: δοθέντων x και y στο R, τέτοια ώστε ο p να διαιρεί το γινόμενο xy, τότε ο p διαιρεί τον x ή τον y. Ένα στοιχείο δεν ανάγεται αν δεν μπορεί να γραφεί ως γινόμενο δύο στοιχείων του δακτυλίου, τα οποία δεν είναι μονάδες. Στο δακτύλιο Ζ των ακεραίων αριθμών, το σύνολο των πρώτων στοιχείων ισούται με το σύνολο των στοιχείων που δεν ανάγονται, το οποίο είναι το
\( \{ \dots, -11, -7, -5, -3, -2, 2, 3, 5, 7, 11, \dots \}\, . \)
Σε κάθε δακτύλιο R, κάθε πρώτο στοιχείο δεν ανάγεται. Το αντίστροφο γενικά δεν ισχύει, αλλά ισχύει για τη μοναδική παραγοντοποίηση διαστημάτων.
Το θεμελιώδες θεώρημα της αριθμητικής συνεχίζει να ισχύει στη μοναδική παραγοντοποίηση διαστημάτων. Ένα παράδειγμα τέτοιου διαστήματος είναι οι ακέραιοι του Γκάους Z[i], οι οποίοι αποτελούν το σύνολο των μιγαδικών αριθμών της μορφής a + bi, όπου το i δηλώνει τη μονάδα των φανταστικών αριθμών και οι a και b είναι τυχαίοι ακέραιοι αριθμοί. Τα πρώτα στοιχεία του συνόλου αυτού είναι γνωστά ως πρώτοι αριθμοί του Gauss. Κάθε πρώτος αριθμός (ακέραιος) δεν είναι πρώτος αριθμός του Γκάους: στο μεγαλύτερο δακτύλιο Z[i], 2 παράγοντες στο γινόμενο των δύο πρώτων αριθμών του Γκάους (1 + i) και (1 - i). Λογικοί πρώτοι αριθμοί (δηλαδή πρώτα στοιχεία του Ζ) της μορφής 4k + 3 είναι πρώτοι αριθμοί του Γκάους, ενώ όλοι οι πρώτοι αριθμοί της μορφής 4k + 1 δεν είναι.
Ιδεώδη πρώτων αριθμών
Στη θεωρία των δακτυλίων, η έννοια του αριθμού αντικαθίσταται γενικά από την έννοια του ιδεώδους. Τα ιδεώδη των πρώτων αριθμών, τα οποία γενικεύουν τα πρώτα στοιχεία, υπό την έννοια ότι το βασικό ιδανικό που παράγεται από ένα πρώτο στοιχείο είναι ιδανικό πρώτου αριθμού, είναι ένα σημαντικό εργαλείο και αντικείμενο της μελέτης της αντιμεταθετικής άλγεβρας, της αλγεβρικής θεωρίας αριθμών και της αλγεβρικής γεωμετρίας. Τα ιδανικά των πρώτων αριθμών του δακτυλίου των ακεραίων αριθμών είναι τα ιδανικά (0), (2), (3), (5), (7), (11), ... Το θεμελιώδες θεώρημα της αριθμητικής γενικεύεται στο θεώρημα των Λάσκερ–Νόθερ, το οποίο εκφράζει κάθε ιδανικό σε ένα αντιμεταθετικό δακτύλιο του Noether ως την τομή βασικών ιδανικών, τα οποία αποτελούν τις κατάλληλες γενικεύσεις των δυνάμεων των πρώτων αριθμών.
Τα ιδανικά των πρώτων αριθμών είναι τα σημεία των αλγεβρογεωμετρικών αντικειμένων, μέσω της έννοιας του φάσματος ενός δακτυλίου. Η αλγεβρική γεωμετρία επίσης επωφελείται από αυτή την έννοια και πράγματι πολλές έννοιες υπάρχον ταυτόχρονα και στη γεωμετρία και στη θεωρία αριθμών. Για παράδειγμα, η παραγοντοποίηση ή η διακλάδωση των ιδανικών των πρώτων αριθμών, όταν αρθεί σε ένα επεκταμένο διάστημα, ένα βασικό πρόβλημα της αλγεβρικής θεωρίας αριθμών, έχει κάποιες ομοιότητες με διακλάδωση στη γεωμετρία. Τέτοιες ερωτήσεις διακλάδωσης, οι οποίες εμφανίζονται ακόμη και σε ερωτήσεις της θεωρίας αριθμών, αποκλειστικά ασχολούνται με ακεραίους αριθμούς. Για παράδειγμα, τα ιδανικά των πρώτων αριθμών στο δακτύλιο των ακεραίων αριθμών σε διάστημα με τα τετράγωνα των αριθμών μπορούν να χρησιμοποιηθούν στην απόδειξη της τετραγωνικής αμοιβαιότητας, μια πρόταση η οποία αφορά τη λύση των δευτεροβάθμιων εξισώσεων
\( x^2 \equiv p \ \ (\text{mod } q),\, \)
όπου ο x είναι ένας ακέραιος και p και q είναι (συνήθεις) πρώτοι αριθμοί. Οι πρόσφατες προσπάθειες για την απόδειξη του τελευταίο θεώρημα του Φερμά τελευταίου θεωρήματος του Φερμά κορυφώθηκαν, όταν ο Kummer εισήγαγε τους τακτικούς πρώτους αριθμούς, δηλαδή πρώτους αριθμούς που ικανοποιούν μια συγκεκριμένη προϋπόθεση σχετικά με την αποτυχία της μοναδικής παραγοντοποίησης στο δακτύλιο που αποτελείται από τις εκφράσεις
\( a_0 + a_1 \zeta + \cdots + a_{p-1} \zeta^{p-1}\, , \)
όπου a0, ..., ap-1 είναι ακέραιοι και ο ζ είναι ένας μιγαδικός αριθμός, τέτοιος ώστε ζp = 1.
Αποτιμήσεις
Η θεωρία των αποτιμήσεων (valuation theory) μελετά συγκεκριμένες συναρτήσεις από ένα διάστημα Κ στους πραγματικούς αριθμούς R που ονομάζονται αποτιμήσεις. Κάθε τέτοια αποτίμηση αποδίδει μια τοπολογία στο Κ και δυο αποτιμήσεις ονομάζονται ισοδύναμες, αν αποδίδουν την ίδια τοπολογία. Ένας πρώτος αριθμός του Κ (μερικές φορές λέγεται μια τοποθεσία του Κ) είναι μια κλάση ισοδυναμίας των αποτιμήσεων. Για παράδειγμα, η p-αδική αποτίμηση ενός ρητού αριθμού q ορίζεται να είναι ο ακέραιος vp(q), τέτοιος ώστε
\( q = p^{v_p(q)} \frac {r}{s}, \)
όπου οι r και s δεν είναι διαιρέσιμοι από τον p. Για παράδειγμα, v3(18/7) = 2. Ο p-αδικός τύπος ορίζεται ως[nb 1]
\( \left| q \right|_p := p^{-v_p(q)}. \, \)
Πιο συγκεκριμένα, αυτός ο τύπος γίνεται μικρότερος, όταν ένας αριθμός πολλαπλασιάζεται από τον 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, στο οποίο οι πρώτοι αριθμοί παρουσιάζονται ως "ξένοι" μεταξύ των ακεραίων αριθμών.
Δείτε ακόμη
Θεώρημα πρώτων αριθμών
Σημειώσεις
κάποιοι δίνουν τον ορισμό \( \left| q \right|_p := e^{-v_p(q)}. \,. \)
Αναφορές
Chris K. Caldwell. «The Top Twenty: Factorial». Primes.utm.edu. Ανακτήθηκε στις 2013-02-05.
Chris K. Caldwell. «The Top Twenty: Primorial». Primes.utm.edu. Ανακτήθηκε στις 2013-02-05.
Chris K. Caldwell. «The Top Twenty: Twin Primes». Primes.utm.edu. Ανακτήθηκε στις 2013-02-05.
Επίσημη σελίδα GIMPS
Ο μεγαλύτερος γνωστός πρώτος αριθμός ήταν πάντα και Μερσέν πρώτος από το 1952, εκτός του 1989 και του 1992; δείτε Κάλντγουελ, "The Largest Known Prime by Year: A Brief History" από το Πανεπιστήμιο του Τενεσί.
Apostol, Thomas M. (1976), Introduction to Analytic Number Theory, New York: Springer, ISBN 0-387-90163-9
Conway, John Horton; Guy, Richard K. (1996), The Book of Numbers, New York: Copernicus, ISBN 978-0-387-97993-9
Crandall, Richard; Pomerance, Carl (2005), Prime Numbers: A Computational Perspective (2nd έκδοση), Berlin, New York: Springer-Verlag, ISBN 978-0-387-25282-7
Derbyshire, John (2003), Prime obsession, Joseph Henry Press, Washington, DC, ISBN 978-0-309-08549-6
Eisenbud, David (1995), Commutative algebra, Graduate Texts in Mathematics, 150, Berlin, New York: Springer-Verlag, ISBN 978-0-387-94268-1
Furstenberg, Harry (1955), «On the infinitude of primes», The American Mathematical Monthly (Mathematical Association of America) 62 (5): 353, doi:10.2307/2307043
Green, Ben; Tao, Terence (2008), «The primes contain arbitrarily long arithmetic progressions», Annals of Mathematics 167 (2): 481–547, doi:10.4007/annals.2008.167.481
Gowers, Timothy (2002), Mathematics: A Very Short Introduction, Oxford University Press, ISBN 978-0-19-285361-5
Guy, Richard K. (1981), Unsolved Problems in Number Theory, Berlin, New York: Springer-Verlag, ISBN 978-0-387-90593-8
Havil, Julian (2003), Gamma: Exploring Euler's Constant, Princeton University Press, ISBN 978-0-691-09983-5
Hardy, Godfrey Harold (1908), A Course of Pure Mathematics, Cambridge University Press, ISBN 978-0-521-09227-2
Hardy, Godfrey Harold (1940), A Mathematician's Apology, Cambridge University Press, ISBN 978-0-521-42706-7
Hill, Peter Jensen, επιμ.. (1995), The Messiaen companion, Portland, Or: Amadeus Press, ISBN 978-0-931340-95-6
Hua, L. K. (2009), Additive Theory of Prime Numbers, Translations of Mathematical Monographs, 13, AMS Bookstore, ISBN 978-0-8218-4942-2
Lehmer, D. H. (1909), Factor table for the first ten millions containing the smallest factor of every number not divisible by 2, 3, 5, or 7 between the limits 0 and 10017000, Washington, D.C.: Carnegie Institution of Washington
Narkiewicz, Wladyslaw (2000), The development of prime number theory: from Euclid to Hardy and Littlewood, Springer Monographs in Mathematics, Berlin, New York: Springer-Verlag, ISBN 978-3-540-66289-1
Ribenboim, Paulo (2004), The little book of bigger primes, Berlin, New York: Springer-Verlag, ISBN 978-0-387-20169-6
Riesel, Hans (1994), Prime numbers and computer methods for factorization, Basel, Switzerland: Birkhäuser, ISBN 978-0-8176-3743-9
Sabbagh, Karl (2003), The Riemann hypothesis, Farrar, Straus and Giroux, New York, ISBN 978-0-374-25007-2
du Sautoy, Marcus (2003), The music of the primes, HarperCollins Publishers, ISBN 978-0-06-621070-4
Περαιτέρω Αναφορές
Kelly, Katherine E., επιμ.. (2001), The Cambridge companion to Tom Stoppard, Cambridge University Press, ISBN 978-0-521-64592-8
Stoppard, Tom (1993), Arcadia, London: Faber and Faber, ISBN 978-0-571-16934-4
Εξωτερικοί σύνδεσμοι
http://www.primzahlen.de/
Hellenica World - Scientific Library
Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License
