Αναλυτική απόδειξη του θεωρήματος των πρώτων αριθμών

Abstract

Στη θεωρία αριθμών , το θεώρημα πρώτων αριθμών περιγράφει την ασυμπτωτική κατανομή των πρώτων αριθμών μεταξύ των θετικών ακεραίων. Το θεώρημα αποδείχθηκε ανεξάρτητα από τον Jacques Hadamard και τον Charles Jean de la Vallée-Poussin το 1896 χρησιμοποιώντας ιδέες που εισήγαγε ο Μπέρναρντ Ρίμαν (ειδικότερα, η συνάρτηση ζήτα του Riemann).

Η πρώτη τέτοια κατανομή που βρέθηκε είναι η π(N) ~ N / log(N), όπου π(N) είναι η συνάρτηση καταμέτρησης των πρώτων αριθμών και log(N) είναι ο φυσικός λογάριθμος του N. Αυτό σημαίνει ότι για αρκετά μεγάλα Ν, η πιθανότητα ένας τυχαίος ακέραιος που δεν είναι μεγαλύτερος από το Ν είναι πρώτος αν είναι πολύ κοντά στο 1 / log(N). Κατά συνέπεια, ένας τυχαίος ακέραιος με το πολύ 2n ψηφία ( για αρκετά μεγάλο n) έχει περίπου τις μισές πιθανότητες να είναι πρώτος από ένα τυχαίο ακέραιο με το πολύ n ψηφία. Για παράδειγμα, μεταξύ των θετικών ακεραίων με το πολύ 1000 ψηφία, περίπου ένα στους 2300 είναι πρώτος (log(101000) ≈ 2302.6), λαμβάνοντας υπόψη ότι μεταξύ των θετικών ακέραιων με το πολύ 2000 ψηφία περίπου ένα στους 4600 είναι πρώτος (log(102000) ≈ 4605.2). Με άλλα λόγια, η μέση διαφορά ανάμεσα στους διαδοχικούς πρώτους αριθμούς μεταξύ των πρώτων N ακεραίων είναι περίπου log(N).