Uwaga. Ciąg arytmetyczny liczb naturalnych zawiera powyższy, ale ma tylko jedną więcej liczbę pierwszą, mianowicie
Ciąg arytmetyczny liczb naturalnych Dowód, że ten ciąg zawiera nieskończenie wiele liczb pierwszych podobny jest do wcześniejszego, powyżej, dla przypadku mod 6. Taki prosty dowód działa tylko dla reszty -1, i tylko mod n: =3 lub 4 lub 6, kiedy to jedynymi resztami mod n, względnie pierwszymi z n, są liczby -1 oraz 1 (mod n). Ciąg arytmetyczny liczb naturalnych Euler pokazał, że nieparzysty dzielnik pierwszy liczby naturalnej postaci musi dać resztę 1 z dzielenia przez 4. Niech więc będzie niepustym zbiorem skończonym liczb naszego ciągu. Niech będzie ich iloczynem. Wtedy musi mieć dzielnik pierwszy z naszego ciągu. Ale dzielnik taki nie może należeć do co oznacza, że zbiór wszystkich liczb pierwszych w naszym ciągu jest nieskończony.
Twierdzenie o liczbach pierwszych
Podstawowe twierdzenie o rozmieszczeniu liczb pierwszych wśród liczb naturalnych sformułował Gauss, który na podstawie badań empirycznych zasugerował, że liczba π(n) liczb pierwszych w przedziale opisana jest zależnością: