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

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

Επομένως το 0 και το 1 δεν είναι πρώτοι αριθμοί.

Ο αριθμός 2 είναι ο μόνος άρτιος πρώτος αριθμός ενώ όλοι οι άλλοι άρτιοι είναι σύνθετοι. Οι περιττοί άλλοτε είναι πρώτοι και άλλοτε σύνθετοι.

Οι πρώτοι αριθμοί είναι ένα από τα αντικείμενα της θεωρίας αριθμών. Διάσημες και άλυτες εικασίες, όπως η Υπόθεση του Ρίμαν και η Εικασία του Γκόλντμπαχ αφορούν πρώτους αριθμούς.

Το κόσκινο του Ερατοσθένη
Η πρόβλημα της εύρεσης πρώτων αριθμών απασχόλησε από τους αρχαίους χρόνους τους μαθηματικούς. Ένας απλός τρόπους για την εύρεση πρώτων αριθμών είναι το κόσκινο του Ερατοσθένη.

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

Είναι προφανές ότι η παραπάνω διαδικασία δεν μπορεί να εφαρμοστεί σε όλο το σύνολο των φυσικών αριθμών, αλλά σε ένα υποσύνολο της μορφής {2,3,4,5, … ,ν} όπου ν οποιοσδήποτε φυσικός αριθμός.

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

• Οι πρώτοι αριθμοί έχουν άπειρο πλήθος.
• Αν ένας αριθμός ν δεν έχει διαιρέτες μικρότερους ή ίσους από την τετραγωνική του ρίζα, τότε είναι πρώτος.
• Όλοι οι πρώτοι αριθμοί στο δεκαδικό σύστημα, εκτός του 2 και του 5, έχουν ως τελευταίο ψηφίο κάποιο από τα 1, 3, 7 ή 9 (διότι οι αριθμοί που τελειώνουν σε 0, 2, 4, 6 και 8 είναι πολλαπλάσια του 2 ενώ οι αριθμοί που τελειώνουν σε 0 ή 5 είναι πολλαπλάσια του 5).
• Αν ο p είναι πρώτος και διαιρεί το γινόμενο αβ για κάποιους ακέραιους α και β, τότε ο p διαιρεί το α ή το β. (Ευκλείδης)
• Αν p πρώτος και α ακέραιος, τότε το α^p−α διαιρείται από το p. (Μικρό Θεώρημα του Φερμά)
• Ένας ακέραιος p>1 είναι πρώτος αν και μόνο αν (p−1)!+1 διαιρείται από το p. (Θεώρημα του Ουίλσον)

Εφαρμογή

Για πολύ καιρό, η θεωρία αριθμών γενικά και η μελέτη των πρώτων αριθμών συγκεκριμένα αποτελούσαν κλασικό παράδειγμα των θεωρητικών μαθηματικών, με καθόλου εφαρμογές έξω από το θεωρητικό κομμάτι. 
Ωστόσο, αυτή η οπτική καταρρίφθηκε τη δεκαετία του 1970, όταν ανακοινώθηκε δημοσίως ότι οι πρώτοι αριθμοί μπορούσαν να χρησιμοποιηθούν ως βάση για τη δημιουργία αλγορίθμων κρυπτογραφίας δημοσίου κλειδιού. 

Αρκετοί αλγόριθμοι κρυπτογράφησης δημόσιου κλειδιού, όπως ο RSA και το πρωτόκολλο ανταλλαγής κλειδιών των Ντίφι-Χέλμαν, βασίζονται στους μεγάλους πρώτους αριθμούς (για παράδειγμα πρώτοι αριθμοί μεγέθους 512 bit χρησιμοποιούνται συχνά για τον RSA και πρώτοι αριθμοί μεγέθους 1024 bit είναι συνήθεις για τον αλγόριθμο Ντίφι–Χέλμαν.). Ο RSA βασίζεται στην υπόθεση ότι είναι πολύ πιο εύκολο (δηλαδή πιο αποτελεσματικό) να εκτελέσουμε πολλαπλασιασμό δύο (μεγάλων) αριθμών x και y από το να υπολογίσουμε τους x και y (υποτίθεται ότι είναι σχετικά πρώτοι) αν μόνο το γινόμενο xy είναι γνωστό.