Θεώρημα του Ευκλείδη

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Άγαλμα του Ευκλείδη στο Μουσείο του Πανεπιστημίου της Οξφόρδης

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

Η απόδειξη του Ευκλείδη[Επεξεργασία | επεξεργασία κώδικα]

Ο Ευκλείδης προσέφερε μια απόδειξη, που δημοσιεύτηκε στο έργο του Στοιχεία⁰ (Βιβλίο IX, Πρόταση 20), [1] που παραφράζεται εδώ. [2]

Εξετάστε οποιαδήποτε πεπερασμένη λίστα πρώτων αριθμών 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 πρέπει επίσης να διαιρέσει τη διαφορά [3] των δύο αριθμών, που είναι (P + 1) - P = 1. Δεδομένου ότι κανένας πρώτος αριθμός δεν διαιρεί 1, το p δεν μπορεί να είναι στη λίστα. Αυτό σημαίνει, ότι υπάρχει τουλάχιστον ένας ακόμη πρώτος αριθμός πέραν εκείνων της λίστας.

Αυτό αποδεικνύει, ότι για κάθε πεπερασμένη λίστα πρώτων αριθμών, υπάρχει ένας πρώτος αριθμός, που δεν βρίσκεται στη λίστα. [4] Στην αρχική απόδειξη, καθώς ο Ευκλείδης δεν είχε κανένα τρόπο να γράφει μια αυθαίρετη λίστα των πρώτων, χρησιμοποίησε μια μέθοδο που εφάρμοζε συχνά, δηλαδή τη μέθοδο του γενικευμένου παραδείγματος. Δηλαδή, επιλέγει μόνο τρεις πρώτους και χρησιμοποιώντας τη γενική μέθοδο που περιγράφεται παραπάνω, αποδεικνύει ότι μπορεί πάντα να βρει ένα επιπλέον πρώτο. Ο Eυκλείδης υποθέτει πιθανώς, ότι οι αναγνώστες του είναι πεπεισμένοι, ότι μια παρόμοια απόδειξη θα λειτουργήσει, ανεξάρτητα από το πόσοι πρώτοι αρχικά επιλέγονται. [5]

Για τον Ευκλείδη συχνά αναφέρεται εσφαλμένα, ότι έχει αποδείξει αυτό το αποτέλεσμα με απαγωγή σε άτοπο, ξεκινώντας από την υπόθεση, ότι το πεπερασμένο σύνολο που εξετάστηκε αρχικά, περιέχει όλους τους πρώτους αριθμούς, [6] αν και στην πραγματικότητα είναι μια απόδειξη με περιπτώσεις, μια μέθοδος άμεσης απόδειξης. Ο φιλόσοφος Torkel Franzén σε ένα βιβλίο σχετικά με τη λογική δηλώνει, ότι "η απόδειξη του Eυκλείδη, ότι υπάρχουν άπειροι πολλοί πρώτοι, δεν αποτελεί έμμεση απόδειξη [. . . ]. Το επιχείρημα μερικές φορές διατυπώνεται ως έμμεση απόδειξη, αντικαθιστώντας το με την υπόθεση «Ας υποθέσουμε ότι το q1, ... qn είναι όλοι οι πρώτοι». Ωστόσο, δεδομένου ότι αυτή η υπόθεση δεν χρησιμοποιείται καν στην απόδειξη, η αναδιατύπωση είναι άσκοπη." [7]

Παραλλαγές[Επεξεργασία | επεξεργασία κώδικα]

Υπάρχουν αρκετές παραλλαγές στην απόδειξη του Eυκλείδη, συμπεριλαμβανομένων των εξής:

Το παραγοντικό n! ενός θετικού ακέραιου n διαιρείται από κάθε ακέραιο από το 2 ως το n, καθώς είναι το γινόμενο όλων αυτών. Ως εκ τούτου, το n! + 1 δεν διαιρείται με κανέναν από τους ακέραιους αριθμούς από 2 έως n, συμπεριλαμβανομένων (δίνει υπόλοιπο 1, όταν διαιρείται με τον κάθε ένα). Ως εκ τούτου n! + 1 είναι είτε πρώτος, είτε διαιρείται από έναν πρώτο μεγαλύτερο από το n. Σε κάθε περίπτωση, για κάθε θετικό ακέραιο n, υπάρχει τουλάχιστον ένας πρώτος μεγαλύτερος από n . Το συμπέρασμα είναι, ότι ο αριθμός των πρώτων είναι άπειρος. [8]

Η απόδειξη του Euler[Επεξεργασία | επεξεργασία κώδικα]

Μια άλλη απόδειξη από τον Ελβετό μαθηματικό Λέοναρντ Όιλερ βασίζεται στο Θεμελιώδες Θεώρημα της Αριθμητικής: ότι κάθε ακέραιος έχει μία μοναδική ανάλυση σε πρώτους παράγοντες. Εάν το P είναι το σύνολο όλων των πρώτων αριθμών, ο Όιλερ έγραψε ότι:

Η πρώτη ισότητα δίνεται από τον τύπο για μια γεωμετρική σειρά σε κάθε όρο του προϊόντος. Η δεύτερη ισότητα είναι μια ειδική περίπτωση του τύπου γινομένου Όιλερ για τη συνάρτηση ζ του Ρήμαν. Για να το δείξετε αυτό, αναλύστε το πιο πάνω γινόμενο:

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

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

Η απόδειξη των Bertrand – Chebyshev[Επεξεργασία | επεξεργασία κώδικα]

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

Το θεώρημα Μπέρτραντ-Τσεμπύσεφ μπορεί επίσης να δηλωθεί ως σχέση με , όπου είναι η συνάρτηση μέτρησης πρώτων (πλήθος των πρώτων αριθμών μικρότερων ή ίσων με ):

, για όλα .

Αυτή η δήλωση διατυπώθηκε ως εικασία για πρώτη φορά το 1845 από τον Γιόζεφ Μπέρτραντ[9] (1822–1900). Ο ίδιος ο Μπέρτραντ επαλήθευσε τη δήλωσή του για όλους τους αριθμούς στο διάστημα [2, 3 × 106]. Η εικασία του αποδείχθηκε πλήρως από τον Τσεμπύσεφ (1821–1894) το 1852 [10] και έτσι η πρόταση ονομάζεται θεώρημα Μπέρτραντ–Τσεμπύσεφ ή θεώρημα Τσεμπύσεφ.

Η απόδειξη του Erdős[Επεξεργασία | επεξεργασία κώδικα]

Ο Πωλ Έρντος έδωσε μια απόδειξη [11], που επίσης βασίζεται στο Θεμελιώδες Θεώρημα της Αριθμητικής. Κάθε θετικός ακέραιος έχει μια μοναδική ανάλυση σε γινόμενο σε έναν αριθμό όχι της μορφής rs2 και σε έναν αριθμό της μορφής rs2 . Για παράδειγμα, 75,600 = 24 33 52 71 = 21 ⋅ 602 .

Έστω N θετικός ακέραιος και έστω k ο αριθμός των πρώτων αριθμών μικρότερος ή ίσος του N . Ονομάστε αυτούς τους πρώτους p1, ..., pk . Οποιοσδήποτε θετικός ακέραιος αριθμός που είναι μικρότερος ή ίσος του N, μπορεί στη συνέχεια να γραφτεί στη μορφή

όπου κάθε ei είναι είτε 0 είτε 1. Υπάρχουν 2k τρόποι σχηματισμού του μη τετραγώνου τμήματος r. Και to s2 μπορεί να είναι το πολύ N, άρα sN . Έτσι, με αυτή τη μορφή μπορούν να γραφτούν το πολύ 2k N αριθμοί. Με άλλα λόγια,

Ή, αναδιάταξη, k, ο αριθμός των πρώτων αριθμών μικρότερος ή ίσος του N, είναι μεγαλύτερος ή ίσος με 1 / 2log2N. Μια και το Ν είναι αυθαίρετο, το k μπορεί να είναι όσο θέλουμε μεγάλο, διαλέγοντας το Ν κατάλληλα.

Η απόδειξη του Furstenberg[Επεξεργασία | επεξεργασία κώδικα]

Στη δεκαετία του 1950, ο Hillel Furstenberg εισήγαγε μια απόδειξη με απαγωγή σε άτοπο, χρησιμοποιώντας τοπολογία συνόλου σημείου. [12]

Ορίζουμε μια τοπολογία στους ακέραιους Z, που ονομάζεται τοπολογία ακέραιων αριθμών ομοιόμορφης απόστασης, δηλώνοντας ένα υποσύνολο U ⊆ Z να είναι ανοικτό σύνολο αν και μόνο αν είναι είτε το κενό σύνολο (το ∅), είτε είναι ένωση αριθμητικών σειρών S (aβ) (για α ≠ 0), όπου

Τότε προκύπτει άτοπο, από την ιδιότητα ότι ένα πεπερασμένο σύνολο ακεραίων δεν μπορεί να είναι ανοικτό και από την ιδιότητα ότι τα σύνολα S (aβ) είναι ανοιχτά και κλειστά, αφού το

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

Μερικές πρόσφατες αποδείξεις[Επεξεργασία | επεξεργασία κώδικα]

Απόδειξη με χρήση της αρχής συμπερίληψης-αποκλεισμού[Επεξεργασία | επεξεργασία κώδικα]

Ο Χουάν Πάμπλο Πινάσκο (Juan Pablo Pinasco) έχει γράψει την παρακάτω απόδειξη. [13]

Έστω p1 , ..., pN είναι οι Ν μικρότεροι πρώτοι. Στη συνέχεια, σύμφωνα με την αρχή συμπερίληψης-αποκλεισμού, ο αριθμός των θετικών ακεραίων μικρότερων ή ίσων με x που διαιρούνται με έναν από αυτούς τους πρώτους είναι

Διαιρώντας με x και αφήνοντας το x → ∞ προκύπται

Αυτό μπορεί να γραφτεί ως

Αν δεν υπάρχουν άλλοι πρώτοι εκτός από τους p1 , ..., pN, τότε η έκφραση στο (1) είναι ίση με  και η έκφραση στο (2) ισούται με 1, αλλά σαφώς η έκφραση στο (3) δεν είναι ίση με 1. Επομένως, πρέπει να υπάρχουν περισσότεροι πρώτοι από p1 , ..., pN .

Απόδειξη χρησιμοποιώντας τον τύπο του de Polignac[Επεξεργασία | επεξεργασία κώδικα]

Το 2010, ο Γιούνο Πέτερ Γουάνγκ (Junho Peter Whang) δημοσίευσε την ακόλουθη απόδειξη με απαγωγή σε άτοπο. [14] Έστω k οποιοσδήποτε θετικός ακέραιος αριθμός. Στη συνέχεια, σύμφωνα με τον τύπο του ντε Πολινιάκ (στην πραγματικότητα είναι του Λεζάντρ)

,

όπου

Αλλά αν υπήρχαν μόνο πεπερασμένοι πολλοί πρώτοι, τότε

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

Απόδειξη με κατασκευή[Επεξεργασία | επεξεργασία κώδικα]

Ο Filip Saidak έδωσε την ακόλουθη απόδειξη με κατασκευή, η οποία δεν χρησιμοποιεί απαγωγή σε άτοπο (reductio ad absurdum) [15] ή το Λήμμα του Ευκλείδη (ότι αν ένας πρώτος p διαιρεί το ab τότε πρέπει να διαιρεί το a ή το β).

Δεδομένου ότι κάθε φυσικός αριθμός (> 1) έχει τουλάχιστον έναν πρώτο παράγοντα, και δύο διαδοχικοί αριθμοί n και (n + 1) δεν έχουν κοινό παράγοντα, το γινόμενο n (n + 1) έχει περισσότερους διαφορετικούς πρώτους παράγοντες από τον ίδιο τον αριθμό n . Άρα η αλυσίδα των προνικών αριθμών :1×2 = 2 {2},  2×3 = 6 {2, 3},  6×7 = 42 {2, 3, 7},  42×43 = 1806 {2, 3, 7, 43},  1806×1807 = 3263442 {2, 3, 7, 43, 13, 139}, · · ·παρέχει μια ακολουθία απεριόριστων αυξανόμενων συνόλων πρώτων.

Απόδειξη με χρήση του ότι το π είναι άρρητος[Επεξεργασία | επεξεργασία κώδικα]

Η αναπαράσταση του τύπου Leibniz για το π ως γινόμενο Euler δίνει το [16]

Οι αριθμητές αυτού του γινόμενου είναι οι περιττοί πρώτοι αριθμοί και κάθε παρονομαστής είναι εκείνο το πολλαπλάσιο του 4 που είναι πλησιέστερα στον αριθμητή.

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

Απόδειξη με χρήση θεωρίας πληροφοριών[Επεξεργασία | επεξεργασία κώδικα]

Ο Alexander Shen και άλλοι παρουσίασαν μια απόδειξη, που χρησιμοποιεί τη μη συμπίεση: [17]

Ας υποθέσουμε, ότι υπήρχαν μόνο k πρώτοι (p 1 ... p k). Με το Θεμελιώδες Θεώρημα της Αριθμητικής, οποιοσδήποτε θετικός ακέραιος αριθμός n θα μπορούσε τότε να αναπαρασταθεί ως:

όπου οι μη αρνητικοί ακέραιοι εκθέτες e i μαζί με την πεπερασμένη λίστα πρώτων αριθμών είναι αρκετοί για την ανασύσταση του αριθμού. Επειδή για όλα τα i, προκύπτει ότι όλα τα (όπου δηλώνει τον λογάριθμο με βάση το 2).

Αυτό αποδίδει μια κωδικοποίηση για n του ακόλουθου μεγέθους (χρησιμοποιώντας συμβολισμό κεφαλαίου O):

bits.

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

Επομένως, ο αριθμός των πρώτων δεν πρέπει να είναι πεπερασμένος.

Πιο δυνατά αποτελέσματα[Επεξεργασία | επεξεργασία κώδικα]

Τα θεωρήματα σε αυτή την ενότητα υπονοούν ταυτόχρονα το θεώρημα του Ευκλείδη και άλλα αποτελέσματα.

Το θεώρημα του Dirichlet για τις αριθμητικές προόδους[Επεξεργασία | επεξεργασία κώδικα]

Το θεώρημα του Ντιριλέ δηλώνει, ότι για οποιουσδήποτε δύο θετικούς, πρώτους μεταξύ τους, ακέραιους αριθμούς a και d, υπάρχουν άπειροι πρώτοι της μορφής a + nd, όπου το n είναι επίσης θετικός ακέραιος αριθμός. Με άλλα λόγια, υπάρχουν άπειροι πρώτοι, που είναι ισότιμοι με a modulo d .

Το Θεώρημα Πρώτων Αριθμών[Επεξεργασία | επεξεργασία κώδικα]

Ας είναι π(x) η συνάρτηση μέτρησης πρώτων, που δίνει τον αριθμό των πρώτων αριθμών μικρότερο ή ίσο του x, για οποιονδήποτε πραγματικό αριθμό x. Το θεώρημα των πρώτων αριθμών δηλώνει τότε, ότι το x / log x είναι μια καλή προσέγγιση του π(x), με την έννοια ότι το όριο του πηλίκου των δύο συναρτήσεων π(x) και x / log x, καθώς το x αυξάνεται χωρίς όριο, είναι 1:

Χρησιμοποιώντας ασυμπτωτικό συμβολισμό, αυτό το αποτέλεσμα μπορεί να επαναδιατυπωθεί ως

Αυτό αποδίδει το θεώρημα του Ευκλείδη, αφού

Σημειώσεις και παραπομπές[Επεξεργασία | επεξεργασία κώδικα]

  1. James Williamson (translator and commentator), The Elements of Euclid, With Dissertations, Clarendon Press, Oxford, 1782, page 63.
  2. Ore, Oystein (1988), Number Theory and its History, Dover, σελ. 65 
  3. In general, for any integers a, b, c if and , then . For more information, see Divisibility.
  4. The exact formulation of Euclid's assertion is: "The prime numbers are more numerous than any proposed multitude of prime numbers".
  5. Katz, Victor J. (1998), A History of Mathematics/ an Introduction (2nd έκδοση), Addison Wesley Longman, σελ. 87 
  6. Michael Hardy and Catherine Woodgold, "Prime Simplicity", Mathematical Intelligencer, volume 31, number 4, fall 2009, pages 44–52.
  7. Franzén, Torkel (2004), Inexhaustibility: A Non-exhaustive Treatment, A K Peters, Ltd, σελ. 101 
  8. Bostock, Linda· Chandler, Suzanne (1 Νοεμβρίου 2014). Further Pure Mathematics (στα Αγγλικά). Nelson Thornes. σελ. 168. ISBN 9780859501033. 
  9. Bertrand, Joseph (1845), «Mémoire sur le nombre de valeurs que peut prendre une fonction quand on y permute les lettres qu'elle renferme.», Journal de l'École Royale Polytechnique 18 (Cahier 30): 123–140, //books.google.com/books?id=WTa-qRIWckoC&pg=PA123 .
  10. Tchebychev, P. (1852), «Mémoire sur les nombres premiers.», Journal de mathématiques pures et appliquées, Série 1: 366–390, http://sites.mathdoc.fr/JMPA/PDF/JMPA_1852_1_17_A19_0.pdf . (Proof of the postulate: 371-382). Also see Mémoires de l'Académie Impériale des Sciences de St. Pétersbourg, vol. 7, pp.15-33, 1854
  11. Havil, Julian (2003). Gamma: Exploring Euler's Constant. Princeton University Press. σελίδες 28-29. ISBN 0-691-09983-9. 
  12. Furstenberg, Harry (1955). «On the infinitude of primes». American Mathematical Monthly 62 (5): 353. doi:10.2307/2307043. MR 0068566. https://archive.org/details/sim_american-mathematical-monthly_1955-05_62_5/page/353. 
  13. Juan Pablo Pinasco, "New Proofs of Euclid's and Euler's theorems", American Mathematical Monthly, volume 116, number 2, February, 2009, pages 172–173.
  14. Junho Peter Whang, "Another Proof of the Infinitude of the Prime Numbers", American Mathematical Monthly, volume 117, number 2, February 2010, page 181.
  15. Saidak, Filip (December 2006). A New Proof of Euclid's Theorem. 113. doi:10.2307/27642094. http://fermatslibrary.com/s/a-new-proof-of-euclids-theorem. 
  16. Debnath, Lokenath (2010), The Legacy of Leonhard Euler: A Tricentennial Tribute, World Scientific, σελ. 214, ISBN 9781848165267, https://books.google.com/books?id=K2liU-SHl6EC&pg=PA214 .
  17. Shen, Alexander (2016), Kolmogorov complexity and algorithmic randomness, AMS, σελ. 245, http://www.lirmm.fr/~ashen/kolmbook-eng.pdf 

Εξωτερικοί σύνδεσμοι[Επεξεργασία | επεξεργασία κώδικα]