Η μαγεία των πρώτων αριθμών
Οι μαθηματικοί αγαπούν τους πρώτους αριθμούς, όπως οι χημικοί αγαπούν τα άτομα και οι βιολόγοι τα γονίδια. Με τον ίδιο τρόπο που τα άτομα είναι το βασικό συστατικό της ύλης, έτσι και οι πρώτοι αριθμοί είναι το κύριο «συστατικό» των μαθηματικών.
Στα μαθηματικά πρώτος αριθμός (ή απλάπρώτος) είναι ένας φυσικός αριθμός μεγαλύτερος της μονάδας με την ιδιότητα οι μόνοι φυσικοί διαιρέτες του να είναι η μονάδα και ο εαυτός του.
Το μηδέν και το ένα δεν είναι πρώτοι αριθμοί. Το μηδέν συχνά δεν θεωρείται ούτε φυσικός. Ο αριθμός 2 είναι ο μόνος άρτιος (ζυγός) πρώτος αριθμός. Όλοι οι άλλοι πρώτοι είναι περιττοί (μονοί). Η ακολουθία των 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, μετά διαγράφουμε τα πολλαπλάσια του επόμενου μη διαγραμμένου αριθμού κ.λ.π. Οι αριθμοί που θα απομείνουν είναι όλοι πρώτοι.
Είναι προφανές ότι η παραπάνω διαδικασία δεν μπορεί να εφαρμοστεί σε όλο το σύνολο των φυσικών αριθμών, αλλά σε ένα υποσύνολο της μορφής {2, 3, 4, 5, ..., ν} όπου ν οποιοσδήποτε φυσικός αριθμός.
Η εικασία του Γκόλντμπαχ (1690-1764)
Ο Κρίστιαν Γκόλντμπαχ, υποστήριξε ότι κάθε άρτιος αριθμός μεγαλύτερος του 2, μπορεί να γραφεί σαν άθροισμα δύο πρώτων αριθμών. Η απόδειξη της παραπάνω εικασίας βασανίζει ακόμα και σήμερα αρκετούς μαθηματικούς αφού συνεχώς νεώτεροι και ισχυρότεροι ηλεκτρονικοί υπολογιστές την επιβεβαιώνουν για όλο και μεγαλύτερους αριθμούς.
"Ο θείος Πέτρος και η εικασία του Γκόλντμπαχ"
Η υπόθεση Ρίμαν (1826-1866)
Ο Ρίμαν, Γερμανός μαθηματικός, έθεσε το ζήτημα του πλήθους των πρώτων αριθμών οι οποίοι είναι μικρότεροι από ένα δοσμένο φυσικό αριθμό ν.
Πόσοι πρώτοι αριθμοί είναι μικρότεροι από το 20; Η απάντηση είναι 8 και είναι οι: 2, 3, 5, 7, 11, 13, 17, 19. Πόσοι μικρότεροι από το 500; το 1000; ... κ.λ.π.
Ο Ρίμαν είχε κάνει μια υπόθεση για τα παραπάνω ερωτήματα, όμως λίγο αργότερα πέθανε. Η σπιτονοικοκυρά του δυστυχώς χωρίς να ξέρει τι έκανε έκαψε τις σημειώσεις του και έτσι δε θα μάθουμε ποτέ τι είχε βρει... Η υπόθεση Ρίμαν αποτελεί μια πρόκληση για τους μαθηματικούς έως και σήμερα.
Δίδυμοι πρώτοι αριθμοί
Δίδυμοι πρώτοι ονομάζονται οι πρώτοι αριθμοί που η διαφορά τους είναι 2, π.χ 11 και 13, 17 και 19, 1.000.037 και 1.000.039. Ένα γνωστό άλυτο πρόβλημα της θεωρίας των αριθμών είναι η εικασία των Διδύμων Πρώτων στην οποία πρέπει να αποδειχτεί πως υπάρχουν άπειροι πρώτοι p τέτοιοι ώστε και ο αριθμός p + 2 να είναι πρώτος. Σημειώνεται ότι 2 είναι η μικρότερη απόσταση μεταξύ δύο πρώτων, καθώς αν ο p είναι πρώτος τότε θα είναι περιττός (με μοναδική εξαίρεση τον αριθμό 2) και άρα ο p + 1 θα είναι άρτιος και άρα σύνθετος αριθμός.
Ιδιότητες των πρώτων αριθμών
Οι πρώτοι αριθμοί έχουν άπειρο πλήθος.
Αν ένας αριθμός ν δεν έχει διαιρέτες μικρότερους ή ίσους από την τετραγωνική του ρίζα, τότε είναι πρώτος.
Όλοι οι πρώτοι αριθμοί στο δεκαδικό σύστημα, εκτός του 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 (θεώρημα του Ουίλσον).
Πρώτοι αριθμοί και κρυπτογραφία
Το σύστημα κρυπτογράφησης δημόσιου κλειδιού (public key cryptography), βασίζεται στους πρώτους αριθμούς και ξεπερνά ένα παλιό πρόβλημα στην επικοινωνία, γνωστό ως πρόβλημα διανομής κλειδιού (key distribution problem).
Ένας αποστολέας (Alice), ο οποίος κωδικοποιεί ένα μήνυμα και το στέλνει σε έναν παραλήπτη (Bob), πρέπει επιπλέον να του δώσει και το κλειδί για την αποκωδικοποίηση του μηνύματος. Ως αναλογία, μπορεί κανείς να φανταστεί ότι η Alice θέλει να στείλει στον Bob ένα πολύτιμο κόσμημα, το οποίο βάζει σε ένα κουτί και το κλειδώνει με ένα κλειδί. Όταν το κουτί φτάσει στον Bob, εκείνος δεν μπορεί να το ανοίξει, μιας και δεν έχει το κλειδί του κουτιού. Στο παρελθόν, η Alice ήταν αναγκασμένη είτε να δώσει στον Bob ένα αντικλείδι εκ των προτέρων, είτε να χρησιμοποιήσει έναν ασφαλή τρόπο για να του παραδώσει το πρωτότυπο κλειδί στον Bob.
Η κρυπτογράφηση δημόσιου κλειδιού, αποφεύγει την οποιαδήποτε ανάγκη για κατανομή κλειδιού, ως εξής: Ο Bob στέλνει ένα ανοικτό λουκέτο στην Alice, ενώ κρατά το κλειδί του λουκέτου. Η Alice κλειδώνει με το λουκέτο, το κόσμημα στο κουτι και το στέλνει στον Bob. Όταν ο Bob παραλάβει το κουτί, μπορεί να το ανοίξει αφού έχει το κλειδί του λουκέτου. Αυτό είναι το τέλειο σύστημα προστασίας, αφού κανένα κλειδί δε χρειάστηκε να σταλεί, το κουτί ήταν πάντα κλειδωμένο και ο Bob μπόρεσε να το ανοίξει.
Η κρυπτογραφία βασισμένη στο παραπάνω σύστημα, χρησιμοποιείται σε εκατοντάδες τομείς σήμερα όπως το ηλεκτρονικό εμπόριο και η κινητή τηλεφωνία. Προφανώς δε χρησιμοποιούνται αληθινά λουκέτα, αλλά "μαθηματικά λουκέτα" τα οποία βασίζονται στον πολλαπλασιαμό πρώτων αριθμών. Ο πολλαπλασιαμός δύο πρώτων αριθμών είναι πολύ απλός (11 x 13 = ?), αλλά είναι ιδιαίτερα δύσκολο να βρεθεί το γινόμενο ποιών 2 πρώτων δίνει ένα συγκεκριμένο αριθμό (? x ? = 437). Αυτό είναι το ανάλογο ενός πραγματικού λουκέτου (εύκολο να το κλειδώσεις αλλά δύσκολο να το ανοίξεις).
Ο βαθμός δυσκολίας του παραπάνω γρίφου (το γινόμενο ποιών πρώτων δίνει ένα συγκεκριμένο αριθμό), αυξάνει ιδιαίτερα καθώς αυξάνει το μέγεθος των εμπλεκόμενων αριθμών.
Η υπόθεση Ρίμαν (1826-1866)
Ο Ρίμαν, Γερμανός μαθηματικός, έθεσε το ζήτημα του πλήθους των πρώτων αριθμών οι οποίοι είναι μικρότεροι από ένα δοσμένο φυσικό αριθμό ν.
Πόσοι πρώτοι αριθμοί είναι μικρότεροι από το 20; Η απάντηση είναι 8 και είναι οι: 2, 3, 5, 7, 11, 13, 17, 19. Πόσοι μικρότεροι από το 500; το 1000; ... κ.λ.π.
Ο Ρίμαν είχε κάνει μια υπόθεση για τα παραπάνω ερωτήματα, όμως λίγο αργότερα πέθανε. Η σπιτονοικοκυρά του δυστυχώς χωρίς να ξέρει τι έκανε έκαψε τις σημειώσεις του και έτσι δε θα μάθουμε ποτέ τι είχε βρει... Η υπόθεση Ρίμαν αποτελεί μια πρόκληση για τους μαθηματικούς έως και σήμερα.
Δίδυμοι πρώτοι αριθμοί
Δίδυμοι πρώτοι ονομάζονται οι πρώτοι αριθμοί που η διαφορά τους είναι 2, π.χ 11 και 13, 17 και 19, 1.000.037 και 1.000.039. Ένα γνωστό άλυτο πρόβλημα της θεωρίας των αριθμών είναι η εικασία των Διδύμων Πρώτων στην οποία πρέπει να αποδειχτεί πως υπάρχουν άπειροι πρώτοι p τέτοιοι ώστε και ο αριθμός p + 2 να είναι πρώτος. Σημειώνεται ότι 2 είναι η μικρότερη απόσταση μεταξύ δύο πρώτων, καθώς αν ο p είναι πρώτος τότε θα είναι περιττός (με μοναδική εξαίρεση τον αριθμό 2) και άρα ο p + 1 θα είναι άρτιος και άρα σύνθετος αριθμός.
Ιδιότητες των πρώτων αριθμών
Οι πρώτοι αριθμοί έχουν άπειρο πλήθος.
Αν ένας αριθμός ν δεν έχει διαιρέτες μικρότερους ή ίσους από την τετραγωνική του ρίζα, τότε είναι πρώτος.
Όλοι οι πρώτοι αριθμοί στο δεκαδικό σύστημα, εκτός του 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 (θεώρημα του Ουίλσον).
Πρώτοι αριθμοί και κρυπτογραφία
Το σύστημα κρυπτογράφησης δημόσιου κλειδιού (public key cryptography), βασίζεται στους πρώτους αριθμούς και ξεπερνά ένα παλιό πρόβλημα στην επικοινωνία, γνωστό ως πρόβλημα διανομής κλειδιού (key distribution problem).
Ένας αποστολέας (Alice), ο οποίος κωδικοποιεί ένα μήνυμα και το στέλνει σε έναν παραλήπτη (Bob), πρέπει επιπλέον να του δώσει και το κλειδί για την αποκωδικοποίηση του μηνύματος. Ως αναλογία, μπορεί κανείς να φανταστεί ότι η Alice θέλει να στείλει στον Bob ένα πολύτιμο κόσμημα, το οποίο βάζει σε ένα κουτί και το κλειδώνει με ένα κλειδί. Όταν το κουτί φτάσει στον Bob, εκείνος δεν μπορεί να το ανοίξει, μιας και δεν έχει το κλειδί του κουτιού. Στο παρελθόν, η Alice ήταν αναγκασμένη είτε να δώσει στον Bob ένα αντικλείδι εκ των προτέρων, είτε να χρησιμοποιήσει έναν ασφαλή τρόπο για να του παραδώσει το πρωτότυπο κλειδί στον Bob.
Η κρυπτογράφηση δημόσιου κλειδιού, αποφεύγει την οποιαδήποτε ανάγκη για κατανομή κλειδιού, ως εξής: Ο Bob στέλνει ένα ανοικτό λουκέτο στην Alice, ενώ κρατά το κλειδί του λουκέτου. Η Alice κλειδώνει με το λουκέτο, το κόσμημα στο κουτι και το στέλνει στον Bob. Όταν ο Bob παραλάβει το κουτί, μπορεί να το ανοίξει αφού έχει το κλειδί του λουκέτου. Αυτό είναι το τέλειο σύστημα προστασίας, αφού κανένα κλειδί δε χρειάστηκε να σταλεί, το κουτί ήταν πάντα κλειδωμένο και ο Bob μπόρεσε να το ανοίξει.
Η κρυπτογραφία βασισμένη στο παραπάνω σύστημα, χρησιμοποιείται σε εκατοντάδες τομείς σήμερα όπως το ηλεκτρονικό εμπόριο και η κινητή τηλεφωνία. Προφανώς δε χρησιμοποιούνται αληθινά λουκέτα, αλλά "μαθηματικά λουκέτα" τα οποία βασίζονται στον πολλαπλασιαμό πρώτων αριθμών. Ο πολλαπλασιαμός δύο πρώτων αριθμών είναι πολύ απλός (11 x 13 = ?), αλλά είναι ιδιαίτερα δύσκολο να βρεθεί το γινόμενο ποιών 2 πρώτων δίνει ένα συγκεκριμένο αριθμό (? x ? = 437). Αυτό είναι το ανάλογο ενός πραγματικού λουκέτου (εύκολο να το κλειδώσεις αλλά δύσκολο να το ανοίξεις).
Ο βαθμός δυσκολίας του παραπάνω γρίφου (το γινόμενο ποιών πρώτων δίνει ένα συγκεκριμένο αριθμό), αυξάνει ιδιαίτερα καθώς αυξάνει το μέγεθος των εμπλεκόμενων αριθμών.
Δεν υπάρχουν σχόλια:
Δεν επιτρέπονται νέα σχόλια.