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

Εισαγωγή στους Πρώτους Αριθμούς

Οι πρώτοι αριθμοί αποτελούν τα «δομικά στοιχεία» των φυσικών αριθμών και έχουν κεντρική θέση στη Θεωρία Αριθμών. Η μελέτη τους ξεκίνησε από την αρχαιότητα και συνεχίζεται μέχρι σήμερα.

Ορισμός Πρώτου Αριθμού

Ορισμός: Ένας φυσικός αριθμός $p > 1$ λέγεται πρώτος αν έχει ακριβώς δύο διαιρέτες: το 1 και τον εαυτό του.

Ορισμός (Σύνθετος αριθμός): Ένας φυσικός αριθμός $n > 1$ λέγεται σύνθετος αν δεν είναι πρώτος, δηλαδή αν έχει τουλάχιστον έναν διαιρέτη διάφορο του 1 και του $n$.

Σημείωση: Το 1 δεν είναι ούτε πρώτος ούτε σύνθετος αριθμός.

Οι Πρώτοι Πρώτοι Αριθμοί

Οι πρώτοι 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 είναι ο μοναδικός άρτιος πρώτος αριθμός.

Θεμελιώδες Θεώρημα της Αριθμητικής

Θεώρημα: Κάθε φυσικός αριθμός $n > 1$ γράφεται μοναδικά ως γινόμενο πρώτων αριθμών:

$$n = p_1^{a_1} \cdot p_2^{a_2} \cdot \ldots \cdot p_k^{a_k}$$

όπου $p_1 < p_2 < \ldots < p_k$ πρώτοι και $a_i \geq 1$.

Αυτή η μορφή ονομάζεται ανάλυση σε πρώτους παράγοντες ή πρώτη παραγοντοποίηση.

Κόσκινο του Ερατοσθένη

Ο αλγόριθμος του Ερατοσθένη βρίσκει όλους τους πρώτους έως έναν αριθμό $n$:

1. Γράφουμε όλους τους αριθμούς από 2 έως $n$
2. Κυκλώνουμε το 2 (πρώτος) και διαγράφουμε όλα τα πολλαπλάσιά του
3. Κυκλώνουμε τον επόμενο μη διαγραμμένο (3) και διαγράφουμε τα πολλαπλάσιά του
4. Συνεχίζουμε μέχρι να φτάσουμε το $\sqrt{n}$
5. Οι κυκλωμένοι και μη διαγραμμένοι είναι όλοι οι πρώτοι

Θεώρημα του Ευκλείδη

Θεώρημα: Υπάρχουν άπειροι πρώτοι αριθμοί.

Απόδειξη (εις άτοπον): Έστω ότι υπάρχουν πεπερασμένοι πρώτοι: $p_1, p_2, \ldots, p_n$.

Θεωρούμε τον αριθμό $N = p_1 \cdot p_2 \cdot \ldots \cdot p_n + 1$.

Ο $N$ δεν διαιρείται με κανέναν από τους $p_i$ (υπόλοιπο 1).

Άρα ο $N$ είναι είτε πρώτος, είτε διαιρείται από πρώτο εκτός της λίστας.

Άτοπο, άρα οι πρώτοι είναι άπειροι. ∎

Έλεγχος Πρωτότητας

Για να ελέγξουμε αν ένας αριθμός $n$ είναι πρώτος:

1. Αρκεί να ελέγξουμε διαιρέτες μέχρι το $\sqrt{n}$
2. Αν κανένας πρώτος $p \leq \sqrt{n}$ δεν διαιρεί το $n$, τότε το $n$ είναι πρώτος

Αιτιολόγηση: Αν $n = a \cdot b$ με $a, b > 1$, τότε ένας από τους $a, b$ είναι $\leq \sqrt{n}$.

Ειδικές Κατηγορίες Πρώτων

Δίδυμοι Πρώτοι

Δύο πρώτοι λέγονται δίδυμοι αν διαφέρουν κατά 2.

Παραδείγματα: $(3,5), (5,7), (11,13), (17,19), (29,31)$

Πρώτοι Mersenne

Πρώτοι της μορφής $M_p = 2^p - 1$ όπου $p$ πρώτος.

Παραδείγματα: $M_2 = 3, M_3 = 7, M_5 = 31, M_7 = 127$

Πρώτοι Fermat

Πρώτοι της μορφής $F_n = 2^{2^n} + 1$.

Γνωστοί: $F_0 = 3, F_1 = 5, F_2 = 17, F_3 = 257, F_4 = 65537$