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

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

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

Η απόδειξη του Ευκλείδη

Ο Ευκλείδης έδωσε την παρακάτω απόδειξη στο έργο του Στοιχεία (Βιβλίο IX, Πρόταση 20),^[1][2][3]

Θεωρούμε μία οποιαδήποτε πεπερασμένη λίστα πρώτων αριθμών ${\displaystyle p_{1},p_{2},\ldots ,p_{n}}$. Θα αποδειχθεί, ότι υπάρχει τουλάχιστον ένας ακόμα πρώτος αριθμός, που δεν υπάρχει στη λίστα. Έστω ${\displaystyle P}$ το γινόμενο όλων των πρώτων αριθμών στη λίστα, δηλ. ${\displaystyle P=p_{1}\cdot p_{2}\cdot \ldots \cdot p_{n}}$ και έστω ${\displaystyle q=P+1}$. Το ${\displaystyle q}$ είναι μεγαλύτερο από όλα τα άλλα στοιχεία, καθώς, ${\displaystyle q=P+1>p_{i}}$. Διακρίνουμε δύο περιπτώσεις σχετικά με το αν ο ${\displaystyle q}$ είναι πρώτος ή όχι: Εάν το ${\displaystyle q}$ είναι πρώτος, τότε υπάρχει τουλάχιστον ένας ακόμη πρώτος, που δεν περιλαμβάνεται στη λίστα. Εάν το ${\displaystyle q}$ δεν είναι πρώτος, τότε κάποιος πρώτος παράγοντας ${\displaystyle p}$ διαιρεί το ${\displaystyle q}$. Εάν αυτός ο παράγοντας ${\displaystyle p}$ ήταν στη λίστα μας, τότε θα διαιρούσε το ${\displaystyle P}$ (αφού το ${\displaystyle P}$ είναι το γινόμενο κάθε αριθμού στη λίστα). Αλλά το ${\displaystyle p}$ διαιρεί επίσης το ${\displaystyle P+1=q}$, όπως μόλις αναφέρθηκε. Εάν το ${\displaystyle p}$ διαιρεί το ${\displaystyle P}$ και το ${\displaystyle q}$, τότε το ${\displaystyle p}$ πρέπει επίσης να διαιρέσει τη διαφορά των δύο αριθμών,[Σημείωση 1] που είναι ${\displaystyle (P+1)-P=1}$. Δεδομένου ότι κανένας πρώτος αριθμός δεν διαιρεί ${\displaystyle 1}$, το ${\displaystyle p}$ δεν μπορεί να είναι στη λίστα. Αυτό σημαίνει, ότι υπάρχει τουλάχιστον ένας ακόμη πρώτος αριθμός πέραν εκείνων της λίστας. Αυτό αποδεικνύει, ότι για κάθε πεπερασμένη λίστα πρώτων αριθμών, υπάρχει ένας πρώτος αριθμός, που δεν υπάρχει στη λίστα.[Σημείωση 2]

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

Για τον Ευκλείδη συχνά αναφέρεται εσφαλμένα, ότι έχει αποδείξει αυτό το αποτέλεσμα με απαγωγή σε άτοπο, ξεκινώντας από την υπόθεση, ότι το πεπερασμένο σύνολο που εξετάστηκε αρχικά, περιέχει όλους τους πρώτους αριθμούς,^[5] αν και στην πραγματικότητα είναι μια απόδειξη με περιπτώσεις, μια μέθοδος ευθείας απόδειξης. Ο φιλόσοφος Torkel Franzén σε ένα βιβλίο σχετικά με τη λογική δηλώνει, ότι "η απόδειξη του Eυκλείδη, ότι υπάρχουν άπειροι πολλοί πρώτοι, δεν αποτελεί έμμεση απόδειξη [...]. Το επιχείρημα μερικές φορές διατυπώνεται ως έμμεση απόδειξη, αντικαθιστώντας το με την υπόθεση «Ας υποθέσουμε ότι οι ${\displaystyle p_{1},\ldots ,p_{n}}$ είναι όλοι οι πρώτοι». Ωστόσο, δεδομένου ότι αυτή η υπόθεση δεν χρησιμοποιείται καν στην απόδειξη, η αναδιατύπωση είναι άσκοπη." ^[6]

Παραλλαγές

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

Το παραγοντικό ${\displaystyle n!}$ ενός θετικού ακέραιου ${\displaystyle n}$ διαιρείται από κάθε ακέραιο από το ${\displaystyle 2}$ ως το ${\displaystyle n}$, καθώς είναι το γινόμενο όλων αυτών. Ως εκ τούτου, το ${\displaystyle n!+1}$ δεν διαιρείται με κανέναν από τους ακέραιους αριθμούς από ${\displaystyle 2}$ έως ${\displaystyle n}$, καθώς δίνει υπόλοιπο 1, όταν διαιρείται με τον κάθε ένα. Συνεπώς, το ${\displaystyle n!+1}$ είναι είτε πρώτος, είτε διαιρείται από έναν πρώτο μεγαλύτερο από το ${\displaystyle n}$. Σε κάθε περίπτωση, για κάθε θετικό ακέραιο ${\displaystyle n}$, υπάρχει τουλάχιστον ένας πρώτος μεγαλύτερος από ${\displaystyle n}$. Το συμπέρασμα είναι ότι το πλήθος των πρώτων είναι άπειρο.[7]

Άλλες αποδείξεις

Η απόδειξη του Όιλερ

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

Εάν το P είναι το σύνολο όλων των πρώτων αριθμών, ο Όιλερ έγραψε ότι: ${\displaystyle \prod _{p\in P}{\frac {1}{1-{\frac {1}{p}}}}=\prod _{p\in P}\sum _{k\geq 0}{\frac {1}{p^{k}}}=\sum _{n}{\frac {1}{n}}.}$ Η πρώτη ισότητα δίνεται από τον τύπο για το άθροισμα μίας γεωμετρικής σειρά για κάθε όρο του γινομένου. Η δεύτερη ισότητα είναι μια ειδική περίπτωση του τύπου γινομένου Όιλερ για τη συνάρτηση ζ του Ρήμαν. Για να το δείξουμε αυτό, αναλύουμε το παραπάνω γινόμενο ως εξής: ${\displaystyle {\begin{aligned}\prod _{p\in P}\sum _{k\geq 0}{\frac {1}{p^{k}}}&=\sum _{k\geq 0}{\frac {1}{2^{k}}}\times \sum _{k\geq 0}{\frac {1}{3^{k}}}\times \sum _{k\geq 0}{\frac {1}{5^{k}}}\times \sum _{k\geq 0}{\frac {1}{7^{k}}}\times \cdots \\[8pt]&=\sum _{k,\ell ,m,n,\ldots \geq 0}{\frac {1}{2^{k}3^{\ell }5^{m}7^{n}\cdots }}=\sum _{n}{\frac {1}{n}}\end{aligned}}}$ Τελικά, κάθε γινόμενο των πρώτων εμφανίζεται ακριβώς μία φορά και έτσι από το Θεμελιώδες Θεώρημα της Αριθμητικής το άθροισμα είναι ίσο με το άθροισμα σε όλους τους ακέραιους αριθμούς. Το άθροισμα στα δεξιά είναι η αρμονική σειρά, η οποία αποκλίνει. Έτσι, το γινόμενο στα αριστερά πρέπει επίσης να αποκλίνει. Δεδομένου ότι κάθε όρος του γινομένου είναι πεπερασμένος, το πλήθος των όρων πρέπει να είναι άπειρος. Επομένως, υπάρχει ένας άπειρος αριθμός πρώτων.

Η απόδειξη των Μπέρτραντ – Τσεμπισιόφ

Στη θεωρία αριθμών, το αίτημα του Bertrand είναι ένα θεώρημα, που δηλώνει, ότι για οποιονδήποτε ακέραιο ${\displaystyle n>1}$ υπάρχει πάντα τουλάχιστον ένας πρώτος αριθμός, έτσι ώστε

${\displaystyle n<p<2n.}$

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

${\displaystyle \pi (x)-\pi ({\tfrac {x}{2}})\geq 1}$, για όλα ${\displaystyle x\geq 2}$.

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

Η απόδειξη του Έρντος

Ο Πολ Έρντος έδωσε μια απόδειξη ^[10], που επίσης βασίζεται στο θεμελιώδες θεώρημα της αριθμητικής. Κάθε θετικός ακέραιος έχει μια μοναδική ανάλυση ως το γινόμενο ${\displaystyle rs^{2}}$, όπου ${\displaystyle r}$ ένας ακέραιος ελεύθερος τετραγώνου και ${\displaystyle s^{2}}$ ένα τετράγωνο . Για παράδειγμα, ${\displaystyle 75.600=2^{4}\cdot 3^{3}\cdot 5^{2}\cdot 7^{1}=21\cdot 60^{2}}$ .

Έστω ${\displaystyle N}$ ένας θετικός ακέραιος και έστω ${\displaystyle p_{1},\ldots ,p_{k}}$ οι πρώτοι αριθμοί μικρότεροι ή ίσοι του ${\displaystyle N}$. Οποιοσδήποτε θετικός ακέραιος αριθμός που είναι μικρότερος ή ίσος του ${\displaystyle N}$, μπορεί στη συνέχεια να γραφτεί στη μορφή ${\displaystyle \underbrace {\left(p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots p_{k}^{e_{k}}\right)} _{r}\cdot s^{2}}$, όπου κάθε ${\displaystyle e_{i}}$ είναι είτε ${\displaystyle 0}$ είτε ${\displaystyle 1}$. Υπάρχουν ${\displaystyle 2^{k}}$ τρόποι σχηματισμού του ${\displaystyle r}$. Και to ${\displaystyle s^{2}}$ μπορεί να είναι το πολύ ${\displaystyle N}$, άρα ${\displaystyle s\leq {\sqrt {N}}}$. Έτσι, με αυτή τη μορφή μπορούν να γραφτούν το πολύ ${\displaystyle 2^{k}\cdot {\sqrt {N}}}$ αριθμοί. Με άλλα λόγια, ${\displaystyle N\leq 2^{k}{\sqrt {N}}.}$ Αναδιατάσσοντας, το ${\displaystyle k}$, δηλαδή το πλήθος των πρώτων αριθμών μικρότερων ή ίσων του ${\displaystyle N}$, είναι μεγαλύτερο ή ίσο με ${\textstyle {\frac {1}{2}}\log _{2}N}$. Αυτό ισχύει για κάθε ${\displaystyle N}$ άρα το ${\displaystyle k}$ μπορεί να είναι οσοδήποτε μεγάλο, αποδεικνύοντας ότι υπάρχουν άπειροι πρώτοι.

Η απόδειξη του Furstenberg

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

Ορίζουμε μια τοπολογία στους ακέραιους ${\displaystyle \mathbb {Z} }$, που ονομάζεται τοπολογία ακέραιων αριθμών ομοιόμορφης απόστασης, δηλώνοντας ένα υποσύνολο ${\displaystyle U\subseteq \mathbb {Z} }$ να είναι ανοικτό σύνολο αν και μόνο αν είναι είτε το κενό σύνολο (το ${\displaystyle \varnothing }$), είτε είναι ένωση αριθμητικών σειρών S (a , β) (για α ≠ 0), όπου ${\displaystyle S(a,b)=\{an+b\mid n\in \mathbb {Z} \}=a\mathbb {Z} +b.}$ Τότε προκύπτει άτοπο, από την ιδιότητα ότι ένα πεπερασμένο σύνολο ακεραίων δεν μπορεί να είναι ανοικτό και από την ιδιότητα ότι τα σύνολα ${\displaystyle S(a,b)}$ είναι ανοιχτά και κλειστά, αφού το ${\displaystyle \mathbb {Z} \setminus \{-1,+1\}=\bigcup _{p{\text{ πρώτος}}}S(p,0)}$ δεν μπορεί να είναι κλειστό, διότι το συμπλήρωμά του είναι πεπερασμένο, αλλά είναι κλειστό, αφού είναι μια πεπερασμένη ένωση κλειστών συνόλων.

Μερικές πρόσφατες αποδείξεις

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

Ο Χουάν Πάμπλο Πινάσκο (Juan Pablo Pinasco) δημοσίευσε το 2009 την παρακάτω απόδειξη.^[12]

Έστω ${\displaystyle p_{1},p_{2},\ldots ,p_{N}}$ είναι οι ${\displaystyle N}$ μικρότεροι πρώτοι αριθμοί. Στη συνέχεια, σύμφωνα με την αρχή εγκλεισμού-αποκλεισμού, ο αριθμός των θετικών ακεραίων μικρότερων ή ίσων με ${\displaystyle x}$ που διαιρούνται με έναν από αυτούς τους πρώτους είναι ${\displaystyle {\begin{aligned}1+\sum _{i}\left\lfloor {\frac {x}{p_{i}}}\right\rfloor -\sum _{i<j}\left\lfloor {\frac {x}{p_{i}p_{j}}}\right\rfloor &+\sum _{i<j<k}\left\lfloor {\frac {x}{p_{i}p_{j}p_{k}}}\right\rfloor -\cdots \\&\cdots \pm (-1)^{N+1}\left\lfloor {\frac {x}{p_{1}\cdots p_{N}}}\right\rfloor .\qquad (1)\end{aligned}}}$ Διαιρώντας με ${\displaystyle x}$ και θέτοντας το ${\displaystyle x\to \infty }$ προκύπτει ${\displaystyle \sum _{i}{\frac {1}{p_{i}}}-\sum _{i<j}{\frac {1}{p_{i}p_{j}}}+\sum _{i<j<k}{\frac {1}{p_{i}p_{j}p_{k}}}-\cdots \pm (-1)^{N+1}{\frac {1}{p_{1}\cdots p_{N}}}.\qquad (2)}$ Αυτό μπορεί να γραφτεί ως ${\displaystyle 1-\prod _{i=1}^{N}\left(1-{\frac {1}{p_{i}}}\right).\qquad (3)}$ Αν δεν υπάρχουν άλλοι πρώτοι αριθμοί εκτός από τους ${\displaystyle p_{1},p_{2},\ldots ,p_{N}}$, τότε το (1) είναι ίσο με ${\displaystyle \lfloor x\rfloor }$ και η έκφραση στο (2) ισούται με ${\displaystyle 1}$, αλλά σαφώς η έκφραση στο (3) δεν είναι ίση με 1. Επομένως, πρέπει να υπάρχουν και άλλοι πρώτοι αριθμοί.

Απόδειξη χρησιμοποιώντας τον τύπο του de Polignac

Το 2010, ο Γιούνο Πέτερ Γουάνγκ (Junho Peter Whang) δημοσίευσε την ακόλουθη απόδειξη με απαγωγή σε άτοπο.^[13]

Έστω ${\displaystyle N}$ ένας οποιοσδήποτε θετικός ακέραιος. Σύμφωνα με τον τύπο του Λεζάντρ ${\displaystyle N!=\prod _{p{\text{ πρώτος}}}p^{f(p,N)}}$, όπου ${\displaystyle f(p,N)=\left\lfloor {\frac {N}{p}}\right\rfloor +\left\lfloor {\frac {N}{p^{2}}}\right\rfloor +\cdots .}$ ${\displaystyle f(p,N)<{\frac {N}{p}}+{\frac {N}{p^{2}}}+\cdots ={\frac {N}{p-1}}\leq N}$. Αλλά αν υπήρχε πεπερασμένο πλήθος πρώτων αριθμών, τότε ${\displaystyle \lim _{N\to \infty }{\frac {\left(\prod _{p}p\right)^{N}}{N!}}=0,}$ καθώς ο αριθμητής του κλάσματος θα αυξανόταν εκθετικά, ενώ με τον τύπο του Στίρλινγκ ο παρονομαστής μεγαλώνει πιο γρήγορα από μεμονωμένα εκθετικά. Αυτό είναι σε αντίθεση με το γεγονός ότι για κάθε ${\displaystyle N}$ ο αριθμητής είναι μεγαλύτερος ή ίσος με τον παρονομαστή.

Κατασκευαστική απόδειξη

Ο Filip Saidak έδωσε την ακόλουθη κατασκευαστική απόδειξη, η οποία δεν χρησιμοποιεί απαγωγή σε άτοπο^[14] ή το Λήμμα του Ευκλείδη (ότι αν ένας πρώτος ${\displaystyle p}$ διαιρεί το ${\displaystyle ab}$ τότε πρέπει να διαιρεί το ${\displaystyle a}$ ή το ${\displaystyle b}$).

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

Απόδειξη με χρήση θεωρίας πληροφοριών

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

Ας υποθέσουμε, ότι υπήρχαν μόνο ${\displaystyle k}$ πρώτοι αριθμοί, έστω οι ${\displaystyle p_{1},p_{2},\ldots ,p_{k}}$. Σύμφωνα με θεμελιώδες θεώρημα της αριθμητικής, οποιοσδήποτε θετικός ακέραιος αριθμός ${\displaystyle n}$ μπορεί να αναπαρασταθεί ως: ${\displaystyle n={p_{1}}^{e_{1}}{p_{2}}^{e_{2}}\cdots {p_{k}}^{e_{k}}}$, όπου οι μη αρνητικοί ακέραιοι εκθέτες ${\displaystyle e_{i}}$ μαζί με την πεπερασμένη λίστα πρώτων αριθμών είναι αρκετοί για την αναπαράσταση (και αναπαραγωγή) του αριθμού. Επειδή ${\displaystyle p_{i}\geq 2}$ για όλα τα i, προκύπτει ότι όλα τα ${\displaystyle e_{i}\leq \log _{2}n}$. Αυτό μας δίνει μια κωδικοποίηση για το ${\displaystyle n}$ χρησιμοποιώντας : ${\displaystyle O({\text{μέγεθος λίστας πρώτων αριθμών}}+k\log _{2}\log _{2}n)=O(\log _{2}\log _{2}n)}$ μπιτ (χρησιμοποιώντας συμβολισμό κεφαλαίου O). Αυτή είναι μια πολύ πιο αποτελεσματική κωδικοποίηση από την αναπαράσταση του ${\displaystyle n}$ απευθείας σε δυαδικό, το οποίο χρησιμοποιεί ${\displaystyle N=O(\log _{2}n)}$ μπιτ. Ένα βασικό αποτέλεσμα στη συμπίεση δεδομένων χωρίς απώλειες λέει ότι δεν είναι δυνατόν να συμπιεστούν ${\displaystyle N}$ μπιτ πληροφορίας σε λιγότερα από ${\displaystyle N}$ μπιτ. Η παραπάνω αναπαράσταση το παραβιάζει κατά πολύ, καθώς όταν το ${\displaystyle n}$ είναι αρκετά μεγάλο, αφού ${\displaystyle \log _{2}\log _{2}n=o(\log _{2}n)}$. Επομένως, το πλήθος των πρώτων αριθμών δεν μπορεί να είναι πεπερασμένο.

Πιο ισχυρά αποτελέσματα

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

Το θεώρημα του Ντίριχλετ για τις αριθμητικές προόδους

Το θεώρημα του Ντίριχλετ δηλώνει, ότι για οποιουσδήποτε δύο θετικούς, σχετικά πρώτους μεταξύ τους, ακέραιους αριθμούς ${\displaystyle a}$ και ${\displaystyle d}$, υπάρχουν άπειροι πρώτοι της μορφής ${\displaystyle a+nd}$, όπου το ${\displaystyle n}$ είναι θετικός ακέραιος. Δηλαδή υπάρχουν άπειροι πρώτοι, που είναι ισοϋπόλοιποι με ${\displaystyle a{\bmod {d}}}$.

Το θεώρημα πρώτων αριθμών

Έστω ${\displaystyle \pi (x)}$ η συνάρτηση μέτρησης πρώτων, που δίνει τον αριθμό των πρώτων αριθμών μικρότερο ή ίσο του ${\displaystyle x}$, για οποιονδήποτε πραγματικό αριθμό ${\displaystyle x}$. Το θεώρημα των πρώτων αριθμών δηλώνει τότε, ότι το ${\displaystyle \pi (x)}$ προσεγγίζει το ${\displaystyle x/\ln(x)}$, δηλαδή

${\displaystyle \lim _{x\rightarrow \infty }{\frac {\pi (x)}{x/\ln(x)}}=1.}$

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

${\displaystyle \pi (x)\sim {\frac {x}{\log x}}.}$

Αυτό δίνει το θεώρημα του Ευκλείδη, αφού ${\displaystyle \lim _{x\rightarrow \infty }{\frac {x}{\log x}}=\infty .}$

Εξωτερικοί σύνδεσμοι

• Weisstein, Eric W., "Euclid's Theorem" από το MathWorld.
• Euclid's Elements, Book IX, Prop. 20 (Euclid's proof, on David Joyce's website at Clark University)

Σημειώσεις

1. Γενικά ισχύει ότι, για φυσικούς αριθμούς ${\displaystyle \alpha ,\beta ,\gamma }$ αν ${\displaystyle \alpha \mid \beta }$ and ${\displaystyle \alpha \mid \gamma }$, τότε ${\displaystyle \alpha \mid (\beta -\gamma )}$. Για περισσότερες πληροφορίες δείτε το λήμμα για τη διαιρετότητα.
2. Η ακριβής διατύπωση του Ευκλείδη είναι η εξής: "Οἱ πρῶτοι ἀριθμοὶ πλείους εἰσὶ παντὸς τοῦ προτεθέντος πλήθους πρώτων ἀριθμῶν.".

Παραπομπές

1. Ευκλείδης (2024). Ροκοπάνος, Νίκος· Σακελλάρη, Στέλλα· Τσολομύτης, Αντώνης, επιμ. Στοιχεία (PDF). Σάμος. σελ. 219. ISBN 9786180052046. 
2. The Elements of Euclid, With Dissertations. Μτφρ. Williamson, James. Oxford: Clarendon Press. 1782. σελ. 63. 
3. Ore, Oystein (1988) [1948]. Number Theory and its History. Dover. σελ. 65. 
4. Katz, Victor J. (1998), A History of Mathematics/ an Introduction (2nd έκδοση), Addison Wesley Longman, σελ. 87 
5. Michael Hardy and Catherine Woodgold, "Prime Simplicity", Mathematical Intelligencer, volume 31, number 4, fall 2009, pages 44–52.
6. Franzén, Torkel (2004), Inexhaustibility: A Non-exhaustive Treatment, A K Peters, Ltd, σελ. 101 
7. Bostock, Linda· Chandler, Suzanne (1 Νοεμβρίου 2014). Further Pure Mathematics (στα Αγγλικά). Nelson Thornes. σελ. 168. ISBN 9780859501033. 
8. 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 .
9. 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
10. Havil, Julian (2003). Gamma: Exploring Euler's Constant. Princeton University Press. σελίδες 28-29. ISBN 0-691-09983-9. 
11. Furstenberg, Harry (1955). «On the infinitude of primes». American Mathematical Monthly 62 (5): 353. doi:10.2307/2307043. https://archive.org/details/sim_american-mathematical-monthly_1955-05_62_5/page/353. 
12. Pinasco, Juan Pablo (February 2009). «New Proofs of Euclid's and Euler's theorems». American Mathematical Monthly 116 (2): 172–173. 
13. Whang, Junho Peter (February 2010). Another Proof of the Infinitude of the Prime Numbers. 117. American Mathematical Monthly, σελ. 181. 
14. 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. 
15. Shen, Alexander (2016), Kolmogorov complexity and algorithmic randomness, AMS, σελ. 245, http://www.lirmm.fr/~ashen/kolmbook-eng.pdf