Ετικέτες

2011-03-15

Πρώτοι Αριθμοί - Μία Εισαγωγή

Πρώτοι! Γιατί πρώτοι; Πόσοι πρώτοι υπάρχουν; Υπάρχουν τελευταίοι πρώτοι; Γιατί είναι τόσο σημαντικοί; Ποιές είναι οι κυριότερες ιδιότητές τους; Τί τους κάνει να ξεχωρίζουν και πως συνδέονται με τους υπόλοιπους ακέραιους; Πώς ξέρουμε ότι είναι άπειροι; Μία εισαγωγή σε να θέμα μαζοχιστικής εμμονής που θα απασχολήσει θα μπερδέψει και θα ταλαιπωρήσει αρκετές αναρτήσεις (και όχι μόνο...) σε αυτό το ιστολόγιο.


Πρώτος αριθμός είναι ένας θετικός ακέραιος που είναι μεγαλύτερος του \(1\) και διαιρείται τέλεια (δηλαδή χωρίς να αφήνει υπόλοιπο) μόνο με τον εαυτό του και το \(1\). Έτσι, ξεκινώντας κάποιος να μετράει και έχοντας υπόψη του τον ορισμό αυτόν θα συναντήσει τους πρώτους \(2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ldots\) (βλέπε και το παρακάτω σχήμα). Παρόλο που ο ορισμός είναι εξαιρετικά απλός, το σύνολο των πρώτων παρουσιάζει αρκετές ιδιομορφίες. Η διάταξη των πρώτων στον άξονα εμφανίζει έναν ιδιαίτερο συνδυασμό κανονικότητας και τυχαιότητας.

Για παράδειγμα, η ακολουθία όλων των άρτιων, δηλαδή των ακέραιων που είναι πολλαπλάσια του 2, μπορεί ως τέτοια να πρoκύψει από τον τύπο \(2n\), όπου το \(n\) είναι ίσο με όλους τους ακέραιους \(n = 1,\ 2,\ 3,\ \ldots\) και η αντικατάσταση των τιμών του στην παραπάνω σχέση δίνει \(2,\ 4,\ 6,\ \ldots\), όπως παρουσιάζεται στο παρακάτω σχήμα. Το ίδιο μπορούμε να κάνουμε και για τους περιττούς αριθμούς, δηλαδή εκείνους που "περισσεύουν" από την παραπάνω ακολουθία των ζυγών. Και για τους περιττούς μπορούμε να φτιάξουμε έναν τύπο που θα τους παράγει. Ο τύπος αυτός είναι το ίδιο απλός με τον τύπο που παράγει τους ζυγούς, μόνο που κάθε φορά προσθέτουμε τη μονάδα, δηλαδή είναι \(2n + 1\). Αντικαθιστώντας μία μία τις τιμές του \(n\) προκυπτει η ακολουθία των περιττών, \(1,\ 3,\ 5,\ 7,\ \ldots\ \). Όμως για την ακολουθία των πρώτων αριθμών τα πράγματα είναι κάπως διαφορετικά.



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

Χαρακτηριστικό είναι το γεγονός ότι από το σύνολο των πρώτων αριθμών μπορεί προκύψει το σύνολο όλων των ακεραίων. Με άλλα λόγια, το σύνολο των Πρώτων αρκεί για να μας δώσει ολόκληρο το σύνολο των ακεραίων. Το γεγονός αυτό είναι εντυπωσιακό, εφόσον ένα σύνολο (ακέραιοι αριθμοί) μπορεί να κατασκευαστεί εξολοκλήρου από ένα υποσύνολό του (Πρώτοι)! Ποια είναι όμως η σχέση των πρώτων αριθμών με τους υπόλοιπους ακέραιους;

Πίσω από αυτή την ερώτηση κρύβεται ένα αρκετά σημαντικό αποτέλεσμα. Είναι τόσο σημαντικό που έχει και ένα βαρύγδουπο όνομα. Τιτλοφορείται ως Θεμελιώδες θεώρημα της Αριθμητικής. Μη σας τρομάζει ο όρος "θεώρημα". Πρόκειται για ένα αποτέλεσμα, όπως τα παραπάνω που παρουσιάσαμε, αλλά συμβαίνει να κατέχει περίοπτη θέση στο οικοδόμημα ολόκληρης της σύγχρονης κρυπτογραφίας και της θεωρίας των Αριθμών (αν δεν έχετε ακούσει ποτέ αυτούς τους όρους μη σας αποτρέψει να συνεχίσετε, δεν θα μας απασχολήσουν ιδιαίτερα εδώ...). Σύμφωνα με το Θεμελιώδες θεώρημα της Αριθμητικής, κάθε ακέραιος μπορεί να εκφραστεί μέσω του συνόλου των πρώτων αριθμών. Πώς μπορεί να γίνει κάτι τέτοιο;


Σύμφωνα με το θεμελιώδες θεώρημα της Αριθμητικής, καθε ακέραιος μπορεί να εκφραστεί ως γινόμενο πρώτων αριθμών. Το γινομένο αυτό είναι μοναδικό για κάθε αριθμό. Οι αριθμοί που δεν είναι πρώτοι ονομάζονται σύνθετοι και είναι εκείνοι οι ακέραιοι που διαιρούνται τέλεια με
τον 1 τον εαυτό τους και με άλλον έναν τουλάχιστον ακέραιο.

Για παράδειγμα, ο \(4\) εκτός από τον εαυτό του και το \(1\), διαιρείται ακριβώς με τον \(2\). Ο αριθμός 6 διαιρείται (εκτός από τον εαυτό του και τον \(1\), όπως γίνεται με όλους τους ακεραίους) με τον \(2\) και με τον \(3\) και μπορεί να εκφραστεί ως \(2\times 3\). Κάθε σύνθετος αριθμός έχει μία ανάλογη έκφραση που είναι μοναδική. Ο \(4\) μπορεί να εκφραστεί ως \(2^2\) και την έκφραση αυτή δε θα τη συναντήσουμε για κανέναν άλλο ακέραιο. Πρόκειται για την ανάλυση του \(4\) σε πρώτους παράγοντες. Ο \(8\) μπορεί να εκφραστεί ως \(2\times4\), όμως λαμβάνοντας υπόψη την έκφραση του \(4\) καταλήγουμε στο \(8 = 2\times4 = 2\times(2^2) = 2^3\) που τελικά αποτελεί και την ανάλυση του \(8\)  σε πρώτους παράγοντες. Ανάλογες εκφράσεις μπορούμε να έχουμε για όλους τους σύνθετους αριθμούς. Για πιο μεγάλους ακέραιους τι γίνεται; Πώς είναι αυτά τα γινόμενα; Είναι αρκετά πολύπλοκα;
Πριν απαντήσουμε σε ανάλογα ερωτήματα θα σταθούμε σε έναν ιδιαίτερα σημαντικό ακέραιο, που δεν μας έχει απασχολήσει ιδιαίτερα μέχρι στιγμής.

Πρόκειται για τον 1. Παρατηρείστε ότι, ο 1 ικανοποιεί όλες τις συνθήκες για να θεωρηθεί πρώτος αριθμός. Διαιρείται ακριβώς με τον εαυτό του και με τον 1 (δηλαδή πάλι με τον εαυτό του - αλλά αυτός είναι ο ορισμός!). Άρα ο 1 είναι πρώτος;


Η απάντηση πρέπει να είναι καταφατική, έτσι ώστε ο ορισμός των πρώτων αριθμών να είναι συνεπής. Εντούτοις, ο 1 δεν θεωρείται πρώτος για διάφορους λόγους... Ένας λόγος έχει να κάνει με την ισχύ του θεμελιώδους θεωρήματος της Αριθμητικής.
Αν ο 1 θεωρούνταν πρώτος δεν θα ίσχυε η μοναδικότητα του αναπτύγματος σε πρώτους παράγοντες. Δεν θα επιμείνουμε πολύ σε αυτό. (Μπορείτε να σκεφτείτε όμως γιατί;)

Οι πρώτοι αριθμοί ήταν γνωστοί στους αρχαίους Έλληνες. Στον Ευκλείδη μία απόδειξη ενός θεωρήματος που αποτελεί μέχρι και σήμερα υπόδειγμα μαθηματικής κομψότητας, εξαιτίας της λιτότητας και της διαύγειας του αποτελέσματος. Το θεώρημα αυτό έχει μία τόσο απλή διατύπωση, όσο απλός είναι και ο παραπάνω ορισμός: Το πλήθος των πρώτων αριθμών είναι άπειρο. Αυτή είναι η πρόταση που απέδειξε ο Ευκλείδης. Αξίζει να παρακολουθήσουμε τον συλλογισμό του.


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


Αρχικά, ο Ευκλείδης υπέθεσε ότι το πλήθος των πρώτων δεν είναι άπειρο. Υπέθεσε ότι κάπου στον άξονα των ακεραίων υπάρχει ένας ακέραιος πέρα από τον οποίο δεν υπάρχουν άλλοι πρώτοι. Ποιος είναι αυτός ο ακέραιος; Δεν χρειάζεται να ξέρουμε. Απλά υποθέστε ότι υπάρχει και όλα τα παρακάτω έπονται ως λογικό συμπέρασμα αυτής της υπόθεσης. (Μόνο που στο τέλος αυτής της συλλογιστικής σας περιμένει μία μικρή έκπληξη.) Το ότι πέρα από αυτόν τον ακέραιο, που δεν ξέρουμε ποιος είναι, αλλά υποθέτουμε ότι υπάρχει, δεν εμφανίζεται άλλος ακέραιος που να είναι πρώτος, σημαίνει ότι η ακολουθία των πρώτων τερματίζεται κάπου. Αυτό ισοδυναμεί με τον ισχυρισμό ότι στην ακολουθία των πρώτων υπάρχει ένας πρώτος που είναι ο τελευταίος πρώτος. Ας συμβολίσουμε λοιπόν αυτόν τον "τελευταίο πρώτο" ως \(P\), έτσι ώστε το σύνολο των πρώτων μπορεί να συμβολιστεί ως \(\{2,\ 3,\ 5,\ 7,\ \ldots,\ P\}\). Αν πολλαπλασιάσουμε το πλήθος αυτών των πρώτων
, το γινόμενο θα ισούται με έναν ακέραιο, στον οποίο προσθέτουμε και τη μονάδα. Συμβολίζουμε τον ακέραιο αυτό ως \(C\) και όπως είπαμε ισχύει
\[
C = 2\cdot 3 \cdot 5 \cdot \ldots \cdot P + 1.
\]
Αν διαιρέσουμε τον \( C\) με καθέναν πρώτο, καμία από αυτή τη διαίρεση δεν είναι τέλεια και αφήνει πάντοτε υπόλοιπο 1. Αυτό συνεπάγεται ότι ο \(C\) δεν μ πορεί να διαιρεθεί με κανέναν αριθμό. Αν όμως συμβαίνει αυτό, τότε ο \(C\) είναι πρώτος αριθμός! Έτσι, καταλήγουμε σε άτοπο. Καταλήξαμε σε ένα συμπέρασμα που έρχεται σε αντιδιαστολή με τα επιμέρους λογικά βήματα που μας οδήγησαν εδώ. Τα μαθηματικά δεν αντέχουν τέτοιες ασυνέπειες. Αν κάτι δεν πάει καλά, τότε το σφάλμα υπάρχει στην αρχή, στις αρχικές μας υποθέσεις. Οι αρχικές μας υποθέσεις είναι εσφαλμένες. Ξεκινήσαμε από την υπόθεση ότι υπάρχει ένας ακέραιος αριθμός πέρα από τον οποίο δεν υπάρχουν πρώτοι αριθμοί, ή ισοδύναμα, ότι οι πρώτοι είναι πεπερασμένοι και ότι υπάρχει "τελευταίος πρώτος". Καμία από αυτές τις προτάσεις δεν είναι ορθή. Συνεπώς το σύνολο των πρώτων είναι άπειρο.

Η απόδειξη αυτή ακόμα και μετά από περίπου 2300 χρόνια θεωρείται υπόδειγμα μαθηματικής απλότητας και ομορφιάς.

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

Δεν υπάρχουν σχόλια:

Δημοσίευση σχολίου