4.5 ΠΡΩΤΟΙ ΑΡΙΘΜΟΙ

Εισαγωγή

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

"Εάν ελάχιστος αριθμός υπό πρώτων αριθμών μετρήται, υπ' ουδενός άλλου πρώτου αριθμού μετρηθήσεται παρέξ των εξ αρχής μετρούντων".

Στα "Στοιχεία" επίσης, το γεγονός ότι υπάρχουν άπειροι πρώτοι αριθμοί εμφανίζεται ως εξής (βιβλίο IX, πρόταση 20):

"Οι πρώτοι αριθμοί πλείους εισί παντός του προτεθέντος πλήθους πρώτων αριθμών".

Το αποτέλεσμα αυτό και η απόδειξή του από τον Ευκλείδη θεωρούνται ένα από τα αριστουργήματα της θεωρητικής μαθηματικής σκέψης. Ο G. Hardy (1877-1947) έγραψε ότι "… είναι τόσο σύγχρονο και σημαντικό όπως και όταν ανεκαλύφθη-εδώ και 2000 χρόνια παρέμεινε ανέπαφο".

Ο μεγαλύτερος πρώτος αριθμός που έχει εντοπιστεί μέχρι σήμερα είναι ο 2^2.967.221 − 1 , ένας "γίγαντας" με 895.932 ψηφία. Πρόκειται για τον 36ο από τους πρώτους αριθμούς της μορφής 2^v − 1 που γνωρίζουμε και ο οποίος οδήγησε στην ανακάλυψη του 36ου τέλειου αριθμού (βλπ. προηγούμενο ιστορικό σημείωμα). Οι τεράστιοι αυτοί αριθμοί εντοπίστηκαν με τη βοήθεια κριτηρίων αναγνώρισης πρώτων, που απαιτούν πολύωρη χρήση ηλεκτρονικών υπολογιστών.

Άλλοι πρώτοι αριθμοί με ιδιαίτερο ενδιαφέρον είναι αυτοί της μορφής p=2^v+1 , όπου v=2^κ , από τους οποίους όμως γνωρίζουμε μόνο 5, αυτούς που προκύπτουν για κ=0,1,2,3,4 και είναι αντίστοιχα οι 3,5,17,257,65537 (όσοι από τους υπόλοιπους έχουν ελεγχθεί αποδείχτηκαν σύνθετοι). Ο C.F. Gauss σε πολύ νεαρή ηλικία έδειξε ότι ένα κανονικό πολύγωνο κατασκευάζεται με κανόνα και διαβήτη, μόνο αν το πλήθος των πλευρών του είναι πρώτος αριθμός αυτής της μορφής ή γινόμενο πρώτων αυτής της μορφής πολλαπλασιασμένο επί μια δύναμη του 2 ή απλώς μια δύναμη του 2.

Το σημαντικότερο όμως ζήτημα σχετικά με τους πρώτους αριθμούς αφορά την κατανομή τους μέσα στην ακολουθία των φυσικών. Η κατανομή αυτή είναι πολύ ακανόνιστη, γιατί από τη μια μεριά υπάρχουν εκατομμύρια ζεύγη των λεγόμενων δίδυμων πρώτων, όπως ,για παράδειγμα, οι (29,31),(1451,1453),(299477,299479), ενώ από την άλλη υπάρχουν τεράστια κενά χωρίς κανέναν πρώτο. Μια σχετική τάξη στο χάος βάζει το "Θεώρημα των πρώτων αριθμών", σύμφωνα με το οποίο το πλήθος των πρώτων αριθμών που είναι μικρότεροι ή

ίσοι από τον φυσικό ν δίνεται κατά προσέγγιση (καθώς το ν γίνεται πολύ μεγάλο) από τον τύπο ν / lnν. Αυτό το διαπίστωσαν εμπειρικά, μελετώντας πίνακες πρώτων αριθμών, οι A.M. Legendre και C.F. Gauss στα τέλη του 18ου αιώνα, ενώ η πρώτη αυστηρή απόδειξη δόθηκε 100 χρόνια αργότερα.

Έννοια Πρώτου Αριθμού

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

ΟΡΙΣΜΟΣ

Κάθε ακέραιος λέγεται πρώτος αριθμός ή απλώς πρώτος, αν οι μόνοι θετικοί διαιρέτες του είναι οι 1 και .

Για παράδειγμα, οι ακέραιοι 2 και -7 είναι πρώτοι, ενώ ο και ο δεν είναι πρώτοι.

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

Οι αριθμοί 1 και -1 δε χαρακτηρίζονται ούτε ως πρώτοι ούτε ως σύνθετοι.

Κάθε πρώτος που διαιρεί ένα δοθέντα ακέραιο λέγεται πρώτος διαιρέτης του ακεραίου αυτού. Είναι φανερό ότι ο -α είναι πρώτος, αν και μόνο αν ο α είναι πρώτος. Γι' αυτό στη συνέχεια θα περιοριστούμε μόνο σε θετικούς πρώτους. Ανάμεσα στους δέκα αριθμούς 1,2,3,...,10 οι 2,3,5 και 7 είναι πρώτοι, ενώ οι 4,6,8 και 10 είναι σύνθετοι. Ο αριθμός 2 είναι ο μοναδικός άρτιος που είναι πρώτος, όλοι οι άλλοι πρώτοι είναι περιττοί.

Ένα εύλογο ερώτημα είναι το εξής:

"Αν δοθεί ένας θετικός ακέραιος α , πώς μπορούμε να αποφανθούμε αν είναι πρώτος ή σύνθετος και, στην περίπτωση που είναι σύνθετος, πώς μπορούμε πρακτικά να βρούμε ένα διαιρέτη διαφορετικό από τους 1 και α ";

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

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

ΘΕΩΡΗΜΑ 6

Κάθε θετικός ακέραιος μεγαλύτερος του 1 έχει έναν τουλάχιστον πρώτο διαιρέτη.

ΑΠΟΔΕΙΞΗ

Έστω ο θετικός ακέραιος και p ο μικρότερος από τους θετικούς διαιρέτες του με . Θα αποδείξουμε ότι ο p είναι πρώτος αριθμός. Αν ο p ήταν σύνθετος, θα είχε ένα θετικό διαιρέτη, έστω β με . Αφού όμως , τότε θα ισχύει (θεώρημα 2). Βρήκαμε έτσι ένα θετικό διαιρέτη β του α που είναι μικρότερος του p . Αυτό όμως είναι άτοπο, αφού ο p θεωρήθηκε ως ο ελάχιστος διαιρέτης του α. Έτσι ο μικρότερος από τους θετικούς διαιρέτες ενός ακεραίου είναι πρώτος αριθμός. ■

ΠΟΡΙΣΜΑ 4

Αν α είναι ένας σύνθετος ακέραιος με , τότε υπάρχει ένας τουλάχιστον πρώτος αριθμός p , τέτοιος, ώστε .

ΑΠΟΔΕΙΞΗ

Επειδή ο α είναι σύνθετος, γράφεται στη μορφή

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

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

Έστω, για παράδειγμα, ο ακέραιος α=271 . Επειδή , χρειάζεται μόνο να εξετάσουμε αν οι πρώτοι που δεν υπερβαίνουν τον 16 είναι διαιρέτες του 271. Οι πρώτοι αυτοί είναι οι 2,3,5,7,11 και 13 και κανένας τους δε διαιρεί τον 271. Άρα, ο 271 είναι πρώτος.

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

Μια έξυπνη τεχνική για τον προσδιορισμό των πρώτων που δεν υπερβαίνουν ένα θετικό ακέραιο στηρίζεται στο προηγούμενο θεώρημα και την οφείλουμε στον Αρχαίο Έλληνα μαθηματικό Ερατοσθένη (περίπου 250 π.Χ.). Η τεχνική λέγεται κόσκινο του Ερατοσθένη και είναι η εξής:

Γράφουμε σε έναν πίνακα με αύξουσα σειρά τους ακεραίους από 2 μέχρι v . Αφήνουμε τον πρώτο 2 και διαγράφουμε όλα τα πολλαπλάσιά του. Ο επόμενος πρώτος στον πίνακα μετά τον 2 είναι ο 3. Αφήνουμε τον 3 και διαγράφουμε όλα τα πολλαπλάσιά του κτλ. Συνεχίζουμε την ίδια διαδικασία μέχρι τον πρώτο p με . Οι ακέραιοι που απομένουν, δηλαδή όσοι δεν "έπεσαν" από το "κόσκινο", είναι οι πρώτοι μεταξύ 2 και v . Όλοι οι άλλοι "έπεσαν", διότι, ως σύνθετοι, είχαν διαιρέτη κάποιον πρώτο μικρότερο ή ίσο της και ως πολλαπλάσια του διαγράφηκαν.

Στον παρακάτω πίνακα έχουν προσδιοριστεί οι πρώτοι μεταξύ 1 και 100. Έχουν διαγραφεί τα πολλαπλάσια των πρώτων 2,3,5 και 7 , αφού ο επόμενος πρώτος είναι ο αριθμός 11 και ισχύει .

Στο σημείο αυτό πιθανόν να αναρωτηθεί κάποιος: Τελειώνουν κάπου οι πρώτοι; Υπάρχει δηλαδή μέγιστος πρώτος ή οι πρώτοι συνεχίζονται "επ'άπειρον";

ΘΕΩΡΗΜΑ 7 (του Ευκλείδη)

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

ΑΠΟΔΕΙΞΗ

Έστω ότι υπάρχει πεπερασμένο πλήθος πρώτων αριθμών p₁,p₂,...,p_v . Θα αποδείξουμε ότι αυτό οδηγεί σε άτοπο. Σχηματίζουμε τον αριθμό . Ο αριθμός όμως αυτός, επειδή είναι μεγαλύτερος του 1, θα έχει έναν τουλάχιστον πρώτο διαιρέτη, έστω τον p_i με . Αλλά αν ο p_i διαιρεί τον A , επειδή διαιρεί και τον p₁p₂...p_v, θα πρέπει να διαιρεί και τον 1. Αυτό όμως είναι άτοπο, γιατί . ■

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

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

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

ΘΕΩΡΗΜΑ 8

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

ΑΠΟΔΕΙΞΗ

Έστω ότι . Επειδή ο αριθμός p είναι πρώτος, οι μοναδικοί διαιρέτες του είναι οι 1 και p . Επομένως, ο Μ.Κ.Δ. των α και p είναι (p,α)=1 , δηλαδή ο p είναι πρώτος προς τον α . Αφού λοιπόν και (p,α)=1 , σύμφωνα με το Πόρισμα 3, . ■

Το θεώρημα ισχύει και για γινόμενο περισσότερων ακεραίων. Δηλαδή:

"Αν p πρώτος και , τότε ο p διαιρεί έναν, τουλάχιστον, από τους παράγοντες του γινομένου".

ΘΕΩΡΗΜΑ 9

Κάθε θετικός ακέραιος αναλύεται κατά μοναδικό τρόπο ως γινόμενο πρώτων παραγόντων (αν παραβλέψουμε τη σειρά των παραγόντων).

ΑΠΟΔΕΙΞΗ *

• Αν ο α είναι πρώτος, τότε προφανώς το θεώρημα ισχύει.

Αν ο α είναι σύνθετος, τότε, σύμφωνα με το θεώρημα 6, θα ισχύει , όπου p₁ πρώτος και β₁ ακέραιος με .

Αν ο β₁ είναι πρώτος, τότε ο α είναι γινόμενο πρώτων παραγόντων και το θεώρημα αληθεύει.

Αν ο β₁ είναι σύνθετος, τότε θα έχουμε , με p₂ πρώτο και .

Αν ο β₂ είναι πρώτος, τότε και ο α είναι γινόμενο πρώτων παραγόντων.

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

• Ας υποθέσουμε ότι ο α αναλύεται και με άλλο τρόπο σε γινόμενο πρώτων παραγόντων, ότι δηλαδή υπάρχουν και οι πρώτοι q₁,q₂,...,q_λ , τέτοιοι, ώστε

και έστω ότι . Ο πρώτος p₁ είναι διαιρέτης του α άρα και του γινομένου . Επομένως, σύμφωνα με το θεώρημα 8, ο p₁ θα είναι διαιρέτης ενός τουλάχιστον από τους παράγοντες q₁,q₂,...,q_λ , έστω , όπου .

Ο q_μ όμως είναι πρώτος και έχει ως διαιρέτες μόνο το 1 και τον εαυτό του. Άρα, επειδή , θα είναι . Ύστερα από τη διαγραφή των δυο αυτών ίσων παραγόντων, με ανάλογο συλλογισμό συμπεραίνουμε ότι ο p₂ πρέπει να είναι ίσος με έναν, τουλάχιστον από τους υπόλοιπους παράγοντες του δεύτερου μέλους της (1) π.χ. τον q_τ . Αφού διαγράψουμε τους p₂ και q_r , συνεχίζουμε ομοίως με τους p₃,...,p_κ . Στο τέλος της διαδικασίας όλοι οι παράγοντες p₁,p₂p₃,...,p_κ θα έχουν διαγραφεί, αφήνοντας μόνο τον αριθμό 1 στο πρώτο μέλος της ισότητας (1). Κανένας όμως και από τους παράγοντες q₁,q₂,...,q_λ δε θα έχει απομείνει και στο δεύτερο μέλος της (1), αφού όλοι αυτοί οι παράγοντες είναι μεγαλύτεροι από το 1. Έτσι, οι παράγοντες p₁,p₂,p₃,...,p_κ του πρώτου μέλους σχηματίζουν ζεύγη ίσων αριθμών με τους παράγοντες του δεύτερου μέλους. Αυτό αποδεικνύει ότι, με εξαίρεση ίσως τη σειρά των παραγόντων, οι δύο αναλύσεις του αριθμού είναι ταυτόσημες. ■

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

Κάθε θετικός ακέραιος μπορεί να γραφεί κατά μοναδικό τρόπο στη μορφή: όπου οι p₁,p₂,...,p_κ είναι θετικοί πρώτοι με και α₁,α₂,...,α_κ θετικοί ακέραιοι.

Η μορφή λέγεται και κανονική μορφή του .

Μ.Κ.Δ. και Ε.Κ.Π. Αριθμών σε Κανονική Μορφή

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

Έστω η κανονική μορφή του α και d ένας θετικός διαιρέτης του. Αν p είναι ένας πρώτος που εμφανίζεται στην κανονική μορφή του d , τότε και επομένως, πρέπει p=p_i με . Επίσης ο p_i δεν μπορεί να εμφανίζεται στον αριθμό d περισσότερο από α_i φορές. Παρατηρούμε δηλαδή ότι ένας διαιρέτης d του α έχει στην κανονική του μορφή παράγοντες μόνο από τους p₁,p₂,...,p_κ και με εκθέτες ίσους ή μικρότερους των α₁,α₂,...,α_κ αντιστοίχως. Για παράδειγμα, επειδή , οι διαιρέτες του 12 είναι οι και .

Με βάση την παρατήρηση αυτή μπορούμε εύκολα να βρούμε Μ.Κ.Δ. και το Ε.Κ.Π. αριθμών που έχουν αναλυθεί σε πρώτους παράγοντες. Συγκεκριμένα:

• Ο Μ.Κ.Δ. θετικών ακεραίων που είναι γραμμένοι σε κανονική μορφή είναι ίσος με το γινόμενο των κοινών τους παραγόντων και με τον κάθε παράγοντα υψωμένο στο μικρότερο εμφανιζόμενο εκθέτη.

• Το Ε.Κ.Π. θετικών ακεραίων που είναι γραμμένοι σε κανονική μορφή είναι ίσο με το γινόμενο των κοινών και μη κοινών τους παραγόντων και με τον κάθε παράγοντα υψωμένο στο μεγαλύτερο εμφανιζόμενο εκθέτη.

Για παράδειγμα, επειδή , έχουμε .

ΕΦΑΡΜΟΓΕΣ

1. Να αποδειχτεί ότι αν ο αριθμός , είναι πρώτος, τότε και ο v είναι πρώτος.

ΑΠΟΔΕΙΞΗ

Αν ο v δεν είναι πρώτος, τότε v=α,β με α,β θετικούς ακέραιους και , οπότε έχουμε . Ο αριθμός αυτός, όμως, έχει ως παράγοντα τον 2^α -1 , για τον οποίο ισχύει . Επομένως, ο είναι σύνθετος που είναι άτοπο.

2. Αν ο φυσικός αριθμός v δεν είναι τετράγωνο φυσικού, να αποδειχτεί ότι ο αριθμός είναι άρρητος.

ΑΠΟΔΕΙΞΗ

Έστω ότι ο αριθμός είναι ρητός. Τότε , όπου α και β θετικοί ακέραιοι. Οι ακέραιοι α και β μπορούν να θεωρηθούν πρώτοι μεταξύ τους, γιατί αν δε συμβαίνει αυτό, τους διαιρούμε με το Μ.Κ.Δ. τους, οπότε μετατρέπονται σε πρώτους μεταξύ τους. Από την ισότητα έχουμε . Επειδή ο v δεν είναι τετράγωνο φυσικού θα είναι . Επομένως, ο ακέραιος β θα έχει έναν πρώτο διαιρέτη p , οπότε θα ισχύει , δηλαδή και άρα (Θεώρημα 10). Επομένως, και , που είναι άτοπο, αφού οι α και β είναι πρώτοι μεταξύ τους.

Ασκήσεις

Α' ΟΜΑΔΑΣ
1.	Ποιοι από τους παρακάτω αριθμούς είναι πρώτοι;