Μετάβαση στο περιεχόμενο
Topos Uranos
Ελληνικά

Πρώτοι αριθμοί και το θεμελιώδες θεώρημα της αριθμητικής

Περίληψη

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

Μαθησιακοί στόχοι

  1. Να διακρίνει τους πρώτους αριθμούς από τους σύνθετους και να αποδεικνύει ότι κάθε φυσικός μεγαλύτερος από τον 11 έχει πρώτο διαιρέτη.
  2. Να εφαρμόζει το κόσκινο του Ερατοσθένη και να αιτιολογεί γιατί αρκεί να διαγραφούν τα πολλαπλάσια των πρώτων που δεν υπερβαίνουν την τετραγωνική ρίζα του ορίου.
  3. Να αποδεικνύει ότι οι πρώτοι είναι άπειροι, το λήμμα του Ευκλείδη και την ύπαρξη και τη μοναδικότητα της ανάλυσης σε πρώτους παράγοντες.
  4. Να χρησιμοποιεί την ανάλυση σε πρώτους παράγοντες για να μετρά και να απαριθμεί διαιρέτες, να αναγνωρίζει τέλεια τετράγωνα και να αποδεικνύει την αρρητότητα τετραγωνικών ριζών.

Πρώτοι αριθμοί και σύνθετοι αριθμοί

Στο μάθημα για τη διαιρετότητα και τη διαίρεση με υπόλοιπο είδαμε ότι κάθε φυσικός nn διαιρείται με τον 11 και με τον εαυτό του. Ορισμένοι φυσικοί δεν δέχονται άλλους διαιρέτες εκτός από αυτούς τους δύο· είναι τα κομμάτια από τα οποία, με πολλαπλασιασμό, συντίθενται όλοι οι άλλοι.

Ορισμός (πρώτος αριθμός). Ένας φυσικός pp είναι πρώτος αν p>1p > 1 και οι μόνοι διαιρέτες του είναι ο 11 και ο pp. Ένας φυσικός n>1n > 1 που δεν είναι πρώτος λέγεται σύνθετος: γράφεται ως n=abn = ab, με 1<a<n1 < a < n και 1<b<n1 < b < n. Ο αριθμός 11 δεν είναι ούτε πρώτος ούτε σύνθετος.

Οι πρώτοι που είναι μικρότεροι από τον 5050 είναι οι δεκαπέντε που ακολουθούν:

2,3,5,7,11,13,17,19,23,29,31,37,41,43,472, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

Ο 22 είναι ο μόνος άρτιος πρώτος, επειδή κάθε άλλος άρτιος αριθμός έχει τον διαιρέτη 22, διαφορετικό από τον 11 και από τον εαυτό του. Ο αποκλεισμός του 11 δεν είναι ιδιοτροπία του ορισμού: αν ο 11 ήταν πρώτος, η ανάλυση σε πρώτους παράγοντες θα έπαυε να είναι μοναδική, επειδή 6=2⋅3=1⋅2⋅36 = 2 \cdot 3 = 1 \cdot 2 \cdot 3, και το κεντρικό θεώρημα αυτού του μαθήματος θα έπρεπε να διατυπωθεί με μια εξαίρεση.

Η αρχή της καλής διάταξης

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

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

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

ΠρότασηΟ μικρότερος διαιρέτης που είναι μεγαλύτερος από τον 1 είναι πρώτος

Κάθε φυσικός n>1n > 1 έχει πρώτο διαιρέτη: ο μικρότερος διαιρέτης του nn που είναι μεγαλύτερος από τον 11 είναι πρώτος. Αν επιπλέον ο nn είναι σύνθετος, ο μικρότερος πρώτος διαιρέτης του pp ικανοποιεί p2≤np^2 \leq n. Το σχήμα σημειώνει πάνω στην ευθεία τους διαιρέτες του n=91=7⋅13n = 91 = 7 \cdot 13.

Απόδειξη

  1. D={d∈N:d∣n∧d>1},n∈D,m=min⁡D\dato{D}{D = \{ d \in \mathbb{N} : d \mid n \wedge d > 1 \}}, \quad n \in D, \quad m = \min D

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

  2. a∣m∧m∣n→a∈D,a<ma \mid m \wedge m \mid n \rightarrow \resaltar{a \in D}, \quad \resaltar{a < m}

    Αν ο mm ήταν σύνθετος, m=abm = ab με 1<a<m1 < a < m, ο παράγοντας aa θα διαιρούσε τον mm και, από τη μεταβατικότητα της διαιρετότητας, τον nn: θα ήταν στοιχείο του DD μικρότερο από τον mm, αντίθετα προς την επιλογή του mm. Επομένως, ο mm είναι πρώτος.

  3. n=pk,k∈D\dato{k}{n = pk, \quad k \in D}

    Έστω τώρα ο nn σύνθετος, και έστω pp ο μικρότερος πρώτος διαιρέτης του, που είναι το ελάχιστο στοιχείο του DD. Γράφουμε n=pkn = pk· επειδή ο nn δεν είναι πρώτος, k≠1k \neq 1, και ο kk διαιρεί επίσης τον nn.

  4. p2=p⋅p≤p⋅k=np^2 = p \cdot p \leq \resaltar{p \cdot k} = n

    Από την ελαχιστότητα του pp έχουμε k≥pk \geq p, και από τη μονοτονία του γινομένου προκύπτει το φράγμα.

Επομένως, για να κρίνουμε αν ένας φυσικός nn είναι πρώτος, αρκεί να δοκιμάσουμε τους πρώτους pp με p2≤np^2 \leq n: αν κανένας δεν τον διαιρεί, ο nn είναι πρώτος. Για παράδειγμα, για τον 221221 αρκεί να δοκιμάσουμε τους πρώτους έως τον 1313, επειδή 172=289>22117^2 = 289 > 221: δεν διαιρείται με τους 22, 33, 55, 77 ούτε με τον 1111, αλλά διαιρείται με τον 1313, και 221=13⋅17221 = 13 \cdot 17. Αντίθετα, ο 211211 δεν διαιρείται με κανέναν από τους πρώτους 22, 33, 55, 77, 1111 και 1313, και επειδή 172=289>21117^2 = 289 > 211, ο αριθμός 211211 είναι πρώτος.