Πρώτοι και σύνθετοι αριθμοί: Το κόσκινο του Ερατοσθένη και μια απόδειξη του Ευκλείδη

 

Πρώτος καλείται ένας φυσικός αριθμός που διαιρείται μόνο με το 1 και τον εαυτό του. Για παράδειγμα οι αριθμοί 2, 3, 11, 17 είναι πρώτοι. Ένας αριθμός που δεν είναι πρώτος καλείται σύνθετος. Για παράδειγμα, ο αριθμός 9 είναι σύνθετος, αφού εκτός της μονάδας και του εαυτού του έχει διαιρέτη και το 3.

Επειδή το 1 έχει μόνο έναν διαιρέτη (το 1, που είναι και ο εαυτός του), δεν είναι ούτε πρώτος ούτε σύνθετος αριθμός. Το 2 είναι ο μοναδικός άρτιος πρώτος, ενώ όλοι οι υπόλοιποι πρώτοι αριθμοί είναι περιττοί.

Μπορούμε να βρούμε όλους τους πρώτους αριθμούς με ένα «κόσκινο»: Το κόσκινο του Ερατοσθένη κρατάει όλους τους σύνθετους αριθμούς και αφήνει να περάσουν όλοι οι πρώτοι.

Το κόσκινο του Ερατοσθένη: Από το βιβλίο Μαθηματικών της Α΄ Γυμνασίου, εκδόσεις Διόφαντος, 2023

Για να βρούμε τους πρώτους αριθμούς, εργαζόμαστε ως εξής:

1. Αφήνουμε απέξω το 1 (είπαμε: δεν είναι ούτε πρώτος, ούτε σύνθετος).

2. Παίρνουμε τον επόμενο αριθμό (το 2). Τον κρατάμε και σβήνουμε όλα τα πολλαπλάσιά του.

3. Παίρνουμε τον επόμενο άσβηστο αριθμό (το 3).
Τον κρατάμε και σβήνουμε όλα τα πολλαπλάσιά του (όσα δεν έχουν σβηστεί από πριν, ως πολλαπλάσια του 2).

​4. Παίρνουμε τον επόμενο άσβηστο αριθμό (το 5).
Τον κρατάμε και σβήνουμε όλα τα πολλαπλάσιά του (όσα έχουν σβηστεί από πριν).

5. Παίρνουμε τον επόμενο αριθμό που έμεινε (το 7).
Τον κρατάμε και σβήνουμε όλα τα πολλαπλάσιά του (όσα δεν είναι σβησμένα από πριν).

Με τον ίδιο τρόπο συνεχίζουμε για πάντα (αφού οι αριθμοί δεν τελειώνουν ποτέ)!

 

Αν όμως θέλουμε να βρούμε τους πρώτους αριθμούς μέχρι το 120 (όπως κάνουμε τώρα), δεν χρειάζεται να προχωρήσουμε παραπάνω από το 7, αφού...
​
...οι αριθμοί που έχουν μείνει, (αυτοί που είναι μέσα στα κυκλάκια) είναι οι πρώτοι αριθμοί.

 

Οι πρώτοι αριθμοί μέχρι το 120 δίνονται παρακάτω:

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.

Γεννάται λοιπόν το ερώτημα: Πόσοι είναι οι πρώτοι αριθμοί; Την απάντηση έδωσε ο Ευκλείδης στα "Στοιχεία" του (Πρόταση ΙΧ.20) αποδεικνύοντας ότι το πλήθος τους είναι άπειρο. Η απόδειξη παραφράζεται εδώ και είναι η εξής:

Εξετάστε οποιαδήποτε πεπερασμένη λίστα πρώτων αριθμών p1, p2 , ... , pn. Θα αποδειχθεί, ότι υπάρχει τουλάχιστον ένας πρόσθετος πρώτος αριθμός, που δεν υπάρχει στη λίστα. Έστω P το γινόμενο όλων των πρώτων αριθμών στη λίστα, δηλ. 

P =p1 · p2 ·  ... ·  pn 

 Ας είναι q = P + 1. Τότε ο q είναι είτε πρώτος ή όχι:

• Εάν ο q είναι πρώτος, τότε υπάρχει τουλάχιστον ένας ακόμη πρώτος, που δεν περιλαμβάνεται στη λίστα.
• Εάν ο q δεν είναι πρώτος, τότε κάποιος πρώτος παράγοντας p διαιρεί τον q. Εάν αυτός ο παράγοντας p ήταν στη λίστα μας, τότε θα διαιρούσε το P (αφού το P είναι το γινόμενο κάθε αριθμού στη λίστα). Αλλά ο p διαιρεί επίσης το P + 1 = q, όπως μόλις αναφέρθηκε. Εάν ο p διαιρεί το P και το q, τότε το p πρέπει επίσης να διαιρεί τη διαφορά των δύο αριθμών, που είναι  (P + 1) - P = 1. Δεδομένου ότι κανένας πρώτος αριθμός δεν διαιρεί το 1, ο p δεν μπορεί να είναι στη λίστα. Αυτό σημαίνει, ότι υπάρχει τουλάχιστον ένας ακόμη πρώτος αριθμός πέραν εκείνων της λίστας.

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

Η απόδειξη αυτή του Ευκλείδη θεωρείται από τις κομψότερες αποδείξεις στην ιστορία των μαθηματικών.

 

Ένα κομμάτι παπύρου των Στοιχείων του Ευκλείδη, που χρονολογείται περίπου στο 75-125 μ.Χ.

Πηγές: 

Σημειώσεις Θεωρίας Αριθμών, Α. Θωμά, Πανεπιστήμιο Ιωαννίνων

Wikipedia.org