Πρώτος αριθμός
Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Στα μαθηματικά πρώτος αριθμός (ή απλά πρώτος) είναι ένας φυσικός αριθμός μεγαλύτερος της μονάδας με την ιδιότητα οι μόνοι φυσικοί διαιρέτες του να είναι η μονάδα και ο εαυτός του.
Το μηδέν και το ένα δεν είναι πρώτοι αριθμοί (Το μηδέν συχνά δεν θεωρείται ούτε φυσικός).
Η ακολουθία των πρώτων ξεκινάει όπως παρακάτω
- 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 ...
Ο αριθμός 2 είναι ο μόνος άρτιος πρώτος αριθμός. Όλοι οι άλλοι πρώτοι είναι περιττοί.
Πίνακας περιεχομένων |
[Επεξεργασία] Αναπαριστώντας φυσικούς αριθμούς ως γινόμενα πρώτων παραγόντων
Το θεμελιώδες θεώρημα της αριθμητικής βεβαιώνει ότι κάθε θετικός ακέραιος γράφεται ως γινόμενο πρώτων παραγόντων με μοναδικό τρόπο. Για παράδειγμα:
[Επεξεργασία] Πλήθος πρώτων
Οι πρώτοι αριθμοί έχουν άπειρο πλήθος. Αυτό μπορεί να αποδειχτεί με τον ακόλουθο τρόπο:
Έστω ότι οι πρώτοι έχουν πεπερασμένο πλήθος n και είναι οι p1,p2,p3,...,pn. Ορίζουμε τον ακέραιο
αυτός ο αριθμός δεν διαιρείται με κανένα πρώτο και αυτό είναι άτοπο ΟΕΔ.
Η απόδειξη αυτή προέρχεται από τον Ευκλείδη.
[Επεξεργασία] Εύρεση πρώτων
Η εύρεση των πρώτων αριθμών απασχόλησε από την αρχαιότητα τους μαθηματικούς. Ένας από τους πιο απλούς αλλά και αργούς τρόπους για (μαζική) εύρεση πολλών πρώτων είναι το λεγόμενο κόσκινο του Ερατοσθένη: Στο σύνολο των φυσικών αριθμών - πρακτικά έως κάποιο μεγάλο αριθμό Ν - αρχίζουμε και αποκλείουμε πρώτα τα πολλαπλάσια του 2 μετά τα πολλαπλάσια του επόμενου μη διαγραμμένου αριθμού κ.ο.κ. έως το Ν. Παρατηρούμε ότι όλο και λιγότερους αριθμούς θα βρίσκουμε προς διαγραφή. Οι αριθμοί που θα απομείνουν είναι όλοι πρώτοι. Το κόσκινο του Ερατοσθένη είναι ένας αργός αλγόριθμος για το άν ένας συγκεκριμένος αριθμός Ν είναι πρώτος ή όχι, διότι μεταξύ άλλων απαιτεί ουσιαστικά και την εύρεση όλων των πρώτων μικρότερων ίσων του (αν ένας αριθμός Ν δεν έχει διαιρέτες μικρότερους ίσους του
, τοτε έναι πρώτος).
[Επεξεργασία] Αλγόριθμοι για την πιστοποίηση πρώτων αριθμών
Παρατίθενται μερικοί αλγόριθμοι (κατά σειρά ταχύτητας ή και απλότητας) για την εύρεση άν ο Ν>=2 είναι πρώτος. Η σειρά επίσης αυτών των αλγορίθμων είναι παιδευτική για την εισαγωγή σε μια σειρά από προγράμματα για ηλεκτρονικούς υπολογιστές.
[Επεξεργασία] Απλός 1 - από τον ορισμό του πρώτου αριθμού
- Εξετάζουμε διαδοχικά όλους τους ακέραιους Μ<Ν
- Μόλις βρεθεί διαιρέτης του Ν σταματάμε και ο Ν δεν είναι πρώτος
- Αν εξαντληθούν οι Μ χωρίς να βρεθεί διαιρέτης, τότε ο Ν είναι πρώτος
[Επεξεργασία] Απλός 2
Βασιζόμενοι στην παρατήρηση ότι κανένας αριθμός Ν δεν έχει διαιρέτη μεγαλύτερο του Ν/2, τροποποιούμε τον παραπάνω αλγόριθμο εξετάζοντας όλους τους αριθμούς Μ<Ν/2.
[Επεξεργασία] Απλός 3
Παρατηρούμε ότι αν ένας αριθμός Ν δεν είναι πρώτος τότε έχει (τουλάχιστον) δύο διαιρέτες μεγαλύτερους από 1. Παρατηρούμε ότι σε αυτή την περίπτωση τουλάχιστον ένας διαιρέτης είναι μικρότερος από την τετραγωνική ρίζα του αριθμού. Τροποποιούμε τον παραπάνω αλγόριθμο εξετάζοντας όλους τους αριθμούς Μ <
[Επεξεργασία] Ο μεγαλύτερος γνωστός πρώτος αριθμός
Στις 15 Δεκεμβρίου 2005 ανακαλύφθηκε ο μεγαλύτερος γνωστός αριθμός. Είναι ο 230.402.457 − 1 και έχει 9.152.052 ψηφία. Τον ανακάλυψαν οι Κέρτις Κούπερ και Στίβεν Μπουν, καθηγητές του Κρατικού Πανεπιστημίου του Κεντρικού Μιζούρι, μέσω του προγράμματος GIMPS (Great Internet Mersenne Prime Search).
[Επεξεργασία] Ιδιότητες πρώτων
- Αν ο p είναι πρώτος και διαιρεί το γινόμενο ab γιά κάποιους ακέραιους a, b τότε ο p διαιρεί το a ή το b. (Ευκλείδης)
- Αν p πρώτος και a ακέραιος, τότε το ap − a διαιρείται από το p (Μικρό Θεώρημα του Φερμά).
- Ένας ακέραιος p > 1 είναι πρώτος αν και μόνο αν p - 1 παραγοντικό + 1 δηλ. το (p − 1)! + 1 διαιρείται από το p (Θεώρημα του Ουίλσον).
[Επεξεργασία] Ανοικτά ερωτήματα
Ένα από τα ανοιχτά ερωτήματα της σύγχρονης θεωρίας αριθμών είναι το πρόβλημα της παραγοντοποίησης μεγάλων ακεραίων, δηλαδή της εύρεσης αλγορίθμου παραγοντοποίησης σε πολυωνυμικό χρόνο. Στην "σκιά" αυτού του προβλήματος αναπτύχθηκε η κρυπτογραφία δημόσιου κλειδιού και ειδικότερα του κρυπτοσυστήματος RSA.
[Επεξεργασία] Oι εικασίες του Γκόλντμπαχ
Είναι πολύ γνωστή η πρώτη εικασία που διατύπωσε ο Κρίστιαν Γκόλντμπαχ 1690-1764, η οποία σχετίζεται με τους πρώτους αριθμούς. Ο Γκόλντμπαχ υποστήριξε οτι κάθε άρτιος αριθμός μεγαλύτερος του 2, μπορεί να γραφεί σαν άθροισμα δύο πρώτων αριθμών. Η απόδειξη της παραπάνω εικασίας ταλανίζει ακόμα και σήμερα τους μαθηματικούς, καθώς παράλληλα οι υπολογιστές επιβεβαιώνουν την εικασία για όλο και μεγαλύτερους αριθμούς. το 1998, η εικασία επιβεβαιώθηκε για αριθμούς μέχρις και της τάξης του 1014
Η δεύτερη εικασία του Γκόλντμπαχ έγκειται στο ότι κάθε περιττός αριθμός μεγαλύτερος του 6 είναι άθροισμα τριών πρώτων αριθμών. Και αυτή η εικασία παραμένει αναπόδειχτη, αν και επιβεβαιώνεται από ηλεκτρονικούς υπολογιστές.