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

Πρώτοι αριθμοί είναι οι αριθμοί που διαιρούνται μόνο με το ένα και με τον εαυτό τους. Οι ιδιότητες των πρώτων αριθμών χρησιμοποιούνται συχνά, για παράδειγμα, στην κρυπτογραφία.

Ορισμός και παραδείγματα

Πρώτος αριθμός είναι ένας φυσικός αριθμός που διαιρείται ακριβώς μόνο με το ένα και με τον εαυτό του, ενώ το ίδιο το ένα δεν είναι πρώτος αριθμός. Ο μικρότερος πρώτος αριθμός είναι το δύο – διαιρείται ακριβώς με το ένα και με το δύο. Είναι επίσης ο μοναδικός πρώτος αριθμός που είναι άρτιος. Όλοι οι υπόλοιποι πρώτοι αριθμοί είναι περιττοί, επειδή κάθε άλλος άρτιος αριθμός διαιρείται, εκτός από το ένα και τον εαυτό του, και με το δύο.

Οι πρώτοι αριθμοί με τη σειρά, από τους μικρότερους: 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…

Με τους πρώτους αριθμούς σχετίζεται το θεμελιώδες θεώρημα της αριθμητικής, το οποίο λέει ότι κάθε ακέραιος αριθμός μεγαλύτερος από το 1 μπορεί να αναλυθεί σε γινόμενο πρώτων αριθμών.

Έλεγξε αν ένας αριθμός είναι πρώτος

Ιδιότητες των πρώτων αριθμών

• Οι πρώτοι αριθμοί είναι άπειροι. Η απόδειξη βρίσκεται στο άρθρο για την απαγωγή σε άτοπο.
• Για κάθε ακέραιο αριθμό z>1 ισχύει ότι στο διάστημα (z, 2z) υπάρχει τουλάχιστον ένας πρώτος αριθμός. Παράδειγμα: για z = 2 έχουμε το διάστημα (2, 4). Ο μόνος ακέραιος σε αυτό το διάστημα είναι το τρία και αυτό είναι πρώτος αριθμός. Για z = 5 παίρνουμε το διάστημα (5, 10), δηλαδή τους αριθμούς 6, 7, 8, 9. Ο αριθμός 7 είναι πρώτος. Παρόμοια και για μεγαλύτερα z.
• Πρώτος του Mersenne είναι ένας πρώτος αριθμός που είναι κατά ένα μικρότερος από κάποια ακέραια δύναμη του δύο. Ο πρώτος του Mersenne M έχει δηλαδή τη μορφή M = 2^z − 1, όπου το z είναι κάποιος φυσικός αριθμός. Παράδειγμα είναι ο πρώτος αριθμός 3, επειδή ισχύει 2² − 1 = 3. Ή το 7, επειδή 2³ − 1 = 7.
• Οι μεγαλύτεροι γνωστοί πρώτοι αριθμοί είναι συνήθως πρώτοι του Mersenne. Για παράδειγμα, στις 23 Αυγούστου 2008 βρέθηκε ο πρώτος του Mersenne M_43112609, όπου ο κάτω δείκτης δείχνει τον εκθέτη z. Πρόκειται για τον πρώτο αριθμό 2^43112609 − 1, ο οποίος έχει 12978189 ψηφία και εκείνη την εποχή ήταν ο μεγαλύτερος γνωστός πρώτος αριθμός.

Ακολουθία χωρίς πρώτους αριθμούς

Μπορούμε να βρούμε πεπερασμένη ακολουθία διαδοχικών φυσικών αριθμών οσοδήποτε μεγάλου μήκους, ανάμεσα στους οποίους δεν υπάρχει κανένας πρώτος. Μια τέτοια ακολουθία μπορεί να έχει τη μορφή k!+2, k!+3, …, k!+k και περιέχει k − 1 διαδοχικούς σύνθετους αριθμούς (το θαυμαστικό δηλώνει το παραγοντικό).

Για παράδειγμα, για k = 6 παίρνουμε πέντε διαδοχικούς σύνθετους αριθμούς της μορφής: 720 + 2, 720 + 3, 720 + 4, 720 + 5, 720 + 6. Αυτοί οι αριθμοί διαιρούνται διαδοχικά με το δύο, το τρία, το τέσσερα, το πέντε και το έξι, επειδή ο αριθμός 6! = 720 διαιρείται σίγουρα με όλους αυτούς τους αριθμούς, αφού προέκυψε ως γινόμενό τους: 6! = 6 · 5 · 4 · 3 · 2. Αν ο αριθμός 720 διαιρείται με το τρία, τότε και ο αριθμός 720 + 3 πρέπει να διαιρείται με το τρία. Παρόμοια και για τους υπόλοιπους.

Μικρό θεώρημα του Fermat

Για κάθε πρώτο αριθμό p και για κάθε ακέραιο αριθμό z ισχύει ότι ο αριθμός z^p − z διαιρείται με τον πρώτο αριθμό p.

Παράδειγμα: ας πάρουμε τον πρώτο αριθμό p = 3 και τον ακέραιο z = 4. Υπολογίζουμε την τιμή 4³ − 4. Αυτή ισούται με 60. Ισχύει όμως ότι 60/3 = 20, άρα το τρία διαιρεί το εξήντα ακριβώς, κάτι που συμφωνεί με το θεώρημα του Fermat. Ένα άλλο παράδειγμα: p = 7, z = 10. Υπολογίζουμε το ενδιάμεσο αποτέλεσμα 10⁷ − 10 = 9999990 και διαιρούμε αυτόν τον αριθμό με το επτά: 9999990/7 = 1428570. Και πάλι βγήκε διαίρεση χωρίς υπόλοιπο.

Άλυτα ερωτήματα

Με τους πρώτους αριθμούς σχετίζονται πολλές γνωστές εικασίες, που μέχρι σήμερα (2011) δεν έχουν ούτε αποδειχθεί ούτε διαψευστεί. Οι δύο πιο γνωστές είναι:

• Το άπειρο πλήθος διδύμων πρώτων: δίδυμοι πρώτοι είναι ένα ζεύγος αριθμών (z, z + 2), όπου και οι δύο αριθμοί είναι πρώτοι. Για παράδειγμα (3, 5) ή (29, 31). Το ερώτημα είναι αν υπάρχουν άπειρα τέτοια ζεύγη. Θεωρείται ότι ναι, αλλά η απόδειξη λείπει.
• Η υπόθεση του Riemann: Όλες οι μη τετριμμένες ρίζες της συνάρτησης ζήτα του Riemann έχουν πραγματικό μέρος ίσο με $\frac{1}{2}$. Η υπόθεση σχετίζεται με την κατανομή των πρώτων αριθμών και είναι ένα από τα λεγόμενα προβλήματα της χιλιετίας, και για τη λύση του σε περιμένει ένα εκατομμύριο δολάρια.