.
Πρώτος αριθμός
Στα μαθηματικά πρώτος αριθμός (ή απλά πρώτος) (Prime Number) είναι ένας φυσικός αριθμός μεγαλύτερος της μονάδας με την ιδιότητα οι μόνοι φυσικοί διαιρέτες του να είναι η μονάδα και ο εαυτός του.
Το μηδέν και το ένα δεν είναι πρώτοι αριθμοί. Το μηδέν συχνά δεν θεωρείται ούτε φυσικός.
Η ακολουθία των 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 είναι ο μόνος άρτιος (ζυγός) πρώτος αριθμός. Όλοι οι άλλοι πρώτοι είναι περιττοί (μονοί).
Οι πρώτοι αριθμοί είναι ένα από τα αντικείμενα της θεωρίας αριθμών και είναι μια πολύ ενεργή ερευνητικά περιοχή των μαθηματικών. Διάσημες και άλυτες εικασίες, όπως η Εικασία του Ρίμαν και η Εικασία του Γκόλντμπαχ εμπλέκουν ή αφορούν πρώτους αριθμούς.
Σχέση φυσικών με πρώτους
Το θεμελιώδες θεώρημα της αριθμητικής βεβαιώνει ότι κάθε θετικός ακέραιος γράφεται ως γινόμενο πρώτων παραγόντων με μοναδικό τρόπο. Για παράδειγμα:
\( 2184 = 2^{3}\times 3\times 7\times 13 \)
Πλήθος πρώτων
Οι πρώτοι αριθμοί έχουν άπειρο πλήθος. Η πρόταση αυτή έχει αποδειχτεί με διάφορους τρόπους. Η πρώτη γνωστή απόδειξη είναι του Ευκλείδη:
Έστω ότι οι πρώτοι έχουν πεπερασμένο πλήθος n και είναι οι \( p_1,p_2,p_3,...,p_n. \) Ορίζουμε τον ακέραιο
\( q = 1 + \prod_{i=1}^n p_i \)
αυτός ο αριθμός δεν διαιρείται με κανένα πρώτο και αυτό είναι άτοπο ΟΕΔ.
Εύρεση πρώτων
Κόσκινο του Ερατοσθένη
Η εύρεση των πρώτων αριθμών απασχόλησε από την αρχαιότητα τους μαθηματικούς. Ένας από τους πιο απλούς αλλά και αργούς τρόπους για (μαζική) εύρεση πολλών πρώτων είναι το λεγόμενο κόσκινο του Ερατοσθένη: Στο σύνολο των φυσικών αριθμών - πρακτικά έως κάποιο μεγάλο αριθμό Ν - αρχίζουμε και αποκλείουμε πρώτα τα πολλαπλάσια του 2 μετά τα πολλαπλάσια του επόμενου μη διαγραμμένου αριθμού κ.ο.κ. έως το Ν. Παρατηρούμε ότι όλο και λιγότερους αριθμούς θα βρίσκουμε προς διαγραφή. Οι αριθμοί που θα απομείνουν είναι όλοι πρώτοι. Το κόσκινο του Ερατοσθένη είναι ένας αργός αλγόριθμος για το αν ένας συγκεκριμένος αριθμός Ν είναι πρώτος ή όχι, διότι μεταξύ άλλων απαιτεί ουσιαστικά και την εύρεση όλων των πρώτων μικρότερων ίσων του \( \sqrt{N} \) (αν ένας αριθμός Ν δεν έχει διαιρέτες μικρότερους ίσους του \sqrt{N}, τότε είναι πρώτος).
Αλγόριθμοι εύρεσης πρώτων
Παρατίθενται μερικοί αλγόριθμοι (κατά σειρά ταχύτητας ή και απλότητας) για την εύρεση αν ο Ν>=2 είναι πρώτος. Η σειρά επίσης αυτών των αλγορίθμων είναι παιδευτική για την εισαγωγή σε μια σειρά από προγράμματα για ηλεκτρονικούς υπολογιστές.
Απλός 1 - από τον ορισμό του πρώτου αριθμού
Εξετάζουμε διαδοχικά όλους τους ακέραιους Μ < Ν
Μόλις βρεθεί διαιρέτης του Ν σταματάμε και ο Ν δεν είναι πρώτος
Αν εξαντληθούν οι Μ χωρίς να βρεθεί διαιρέτης, τότε ο Ν είναι πρώτος
Απλός 2
Βασιζόμενοι στην παρατήρηση ότι κανένας αριθμός 'Ν' δεν έχει διαιρέτη μεγαλύτερο του 'Ν'/2, τροποποιούμε τον παραπάνω αλγόριθμο εξετάζοντας όλους τους αριθμούς 'Μ' < 'Ν'/2.
Απλός 3
Παρατηρούμε ότι αν ένας αριθμός Ν δεν είναι πρώτος τότε έχει (τουλάχιστον) δύο διαιρέτες μεγαλύτερους από 1. Σε αυτήν την περίπτωση τουλάχιστον ένας διαιρέτης είναι μικρότερος από την τετραγωνική ρίζα του αριθμού. Τροποποιούμε τον αλγόριθμο 2 εξετάζοντας όλους τους αριθμούς Μ που είναι μικρότεροι από την τετραγωνική ρίζα του N, αν η τελευταία δεν είναι ακέραιος. Αλλιώς ο αριθμός δεν είναι πρώτος, επειδή τον διαιρεί και η τετραγωνική του ρίζα.
Απλός 4
Εφαρμόζοντας το Θεώρημα του Ουίλσον μπορούμε να εξετάσουμε, αν ένας αριθμός Ν είναι πρώτος ή όχι. Σύμφωνα με το θεώρημα αυτό ο Ν είναι πρώτος αν και μόνο αν ισχύει
\( (N-1)!\ \equiv\ -1\ (\mbox{mod}\ N), \)
αν δηλαδή το υπόλοιπο της διαίρεσης του Ν-1 παραγοντικό με το Ν, είναι ίσο με το υπόλοιπο της διαίρεσης του -1 με το N.
Η μέθοδος αυτή δεν εφαρμόζεται για μεγάλο Ν, αφού είναι δύσκολο να υπολογιστεί το παραγοντικό.
Ο μεγαλύτερος γνωστός πρώτος αριθμός
Μέχρι τον Μάιο του 2012, ο μεγαλύτερος γνωστός πρώτος αριθμός είναι ο:
243.112.609 − 1.
Η ανακάλυψη του έγινε στις 23 Αυγούστου 2008, μέσω του διαδικτυακού προγράμματος κατανεμημένης επεξεργασίας GIMPS (Great Internet Mersenne Prime Search).[1] Ο αριθμός αυτός έχει 12.978.189 ψηφία (ο πρώτος πρώτος με πάνω από 10 εκατομμύρια ψηφία) και έχει την πρόσθετη ιδιότητα να είναι ο 45ος Μερσέν πρώτος (Mersenne prime) που ανακαλύφθηκε. Ο 46ος Μερσέν πρώτος, ο 237.156.667 − 1, ανακαλύφθηκε δύο βδομάδες αργότερα—είναι πρώτος, αλλά μικρότερος.
Στο πρόσφατο παρελθόν, όλοι οι πρώτοι που ανακαλύφθηκαν ήταν Μερσέν πρώτοι.[2]
Ιδιότητες πρώτων
Αν ο 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.
Ανοικτά ερωτήματα
Ένα από τα ανοιχτά ερωτήματα της σύγχρονης θεωρίας αριθμών είναι το πρόβλημα της παραγοντοποίησης μεγάλων ακεραίων, δηλαδή της εύρεσης αλγορίθμου παραγοντοποίησης σε πολυωνυμικό χρόνο. Στην "σκιά" αυτού του προβλήματος αναπτύχθηκε η κρυπτογραφία δημόσιου κλειδιού και ειδικότερα του κρυπτοσυστήματος RSA.
Οι εικασίες του Γκόλντμπαχ
Κύριο λήμμα: Εικασία του Γκόλντμπαχ
Είναι πολύ γνωστή η πρώτη εικασία που διατύπωσε ο Κρίστιαν Γκόλντμπαχ 1690-1764, η οποία σχετίζεται με τους πρώτους αριθμούς. Ο Γκόλντμπαχ υποστήριξε ότι κάθε άρτιος αριθμός μεγαλύτερος του 2, μπορεί να γραφεί ως άθροισμα δύο πρώτων αριθμών. Η απόδειξη της παραπάνω εικασίας ταλανίζει ακόμα και σήμερα τους μαθηματικούς, καθώς παράλληλα οι υπολογιστές επιβεβαιώνουν την εικασία για όλο και μεγαλύτερους αριθμούς. Το 1998, η εικασία επιβεβαιώθηκε για αριθμούς μέχρις και της τάξης του \( 10^{14} \)
Η δεύτερη εικασία του Γκόλντμπαχ έγκειται στο ότι κάθε περιττός αριθμός μεγαλύτερος του 6 είναι άθροισμα τριών πρώτων αριθμών. Και αυτή η εικασία παραμένει αναπόδεικτη, αν και επιβεβαιώνεται από ηλεκτρονικούς υπολογιστές. Τυχόν απόδειξη της πρώτης εικασίας του Γκόλντμπαχ θα αποδείκνυε αμέσως και τη δεύτερη εικασία. Στη πρώτη εικασία γιατί <...μεγαλύτερος του 2;...> , 2=1+1 άθροισμα δύο Πρώτων ή να διατυπωθεί <.....ως άθροισμα δύο διαφορετικών Πρώτων ......>.
Δείτε ακόμη
Θεώρημα πρώτων αριθμών
Αναφορές
↑ Επίσημη σελίδα GIMPS
↑ Ο μεγαλύτερος γνωστός πρώτος αριθμός ήταν πάντα και Μερσέν πρώτος από το 1952, εκτός του 1989 και του 1992; δείτε Caldwell, "The Largest Known Prime by Year: A Brief History" από το Πανεπιστήμιο του Τενεσί.
Retrieved from "http://el.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
