Write down the primes in order: $2, 3, 5, 7, 11, 13, 17, \ldots$ They get rarer as you go. Between $1$ and $100$ there are $25$ of them; between $1{,}000{,}000$ and $1{,}000{,}100$ there are $6$. So it's a fair question whether they ever run out, whether there's a last prime and after it nothing but composites. Euclid settled it around 300 BC, and his proof is so short it fits on a napkin.
This page proves it, then proves it again three more times, because each new proof tells you something the first one doesn't: how fast the primes grow, where they hide in a progression like $4n + 3$, and how dense they are. On this page $p$ is any prime, $2$ included, and $\log$ is the natural logarithm. Practice sits right after each idea, and the Mixed Practice at the bottom takes that hint away.
Everything here rests on one fact you already have: every integer bigger than $1$ is a product of primes.
A prime is an integer $p > 1$ whose only positive divisors are $1$ and $p$, and the Fundamental Theorem of Arithmetic says every $n > 1$ factors into primes in exactly one way. All we need today is the easy half: $n$ has at least one prime factor.
Euclid's idea is to take any finite list of primes and build a number that none of them divides. Its prime factors then have to be somewhere off the list. Try it yourself before you open the proof: what number is guaranteed not to be divisible by $2$, $3$, or $5$?
There are infinitely many primes.
Proof. Suppose there were only finitely many, say $p_1, p_2, \ldots, p_k$. Let $$N = p_1 p_2 \cdots p_k + 1.$$ Since $N > 1$, it has a prime factor $q$. Since $q$ is prime, it is one of the $p_i$, so $q \mid p_1 \cdots p_k$. Then $q$ divides the difference $N - p_1 \cdots p_k = 1$, which no prime does. $\blacksquare$
Read it as a machine, not just a contradiction: feed in any finite list of primes, and out comes a prime that isn't on it. Run the machine again on the longer list, and again, and the list grows forever.
That list, $2, 3, 7, 43, 13, 53, 5, \ldots$, is the Euclid–Mullin sequence. Nobody knows whether every prime eventually shows up in it. Notice the order, too: the new prime can be smaller than primes already on the list.
Run Euclid's construction on the list $3, 5$, with both $P + 1$ and $P - 1$. Which new primes come out?
$P = 3 \cdot 5 = 15$. Then $P + 1 = 16 = 2^4$, so the new prime is $2$, smaller than both primes on the list. And $P - 1 = 14 = 2 \cdot 7$, which gives $2$ and $7$. Neither $3$ nor $5$ divides $16$ or $14$: each leaves remainder $\pm 1$. The minus sign works just as well, as long as $P - 1 > 1$.
The one thing the proof never claims is that $N$ itself is prime. It's the most common way to misremember it.
"Multiply the first $k$ primes and add $1$; that's a new prime" is false. $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \cdot 509$. Euclid only needs $N$'s prime factors to be new.
Build your own Euclid numbers. Every prime factor that drops out is new, whatever list you pick.
The third mission is the surprising one: the list $3, 5$ gives back $2$. Euclid's machine doesn't hand you the next prime, just a missing one.
Every time somebody announces a record prime, I want to multiply all the known primes, add $1$, and claim a bigger one. Then I remember $N$'s prime factors might be tiny, and I'd have to factor a number with millions of digits to find out.
Your turn. Trial division by small primes is all you need.
Loading practice engine...
Euclid's trick also says where to look for a new prime: no further out than $n! + 1$. Try it before you open the proof.
Show that for every $n \ge 1$ there is a prime $p$ with $n < p \le n! + 1$.
Proof. $n! + 1 \ge 2$, so it has a prime factor $p$, and $p \le n! + 1$. If $p \le n$, then $p$ is one of the factors $1, 2, \ldots, n$ of $n!$, so $p \mid n!$, and then $p$ divides $(n! + 1) - n! = 1$, which is impossible. So $p > n$. $\blacksquare$
That's a second proof of Euclid's theorem in one line: no $n$ is bigger than every prime. There's an even stranger proof, from a course you might not expect.
Furstenberg's proof (1955): call a set of integers open if it's a union of progressions $a + b\mathbb{Z}$ with $b \ge 1$. That's a topology, every nonempty open set is infinite, and each $a + b\mathbb{Z}$ is closed too (its complement is the other $b - 1$ classes). Now $\mathbb{Z} \setminus \{-1, 1\} = \bigcup_p p\mathbb{Z}$. With finitely many primes this would be a finite union of closed sets, so closed, so $\{-1, 1\}$ would be open. But it's finite.
"Infinitely many" is the start of the story. The real question is how many primes there are up to a given size, and that count gets its own name.
For a real number $x$, the prime-counting function $\pi(x)$ is the number of primes $p \le x$.
So $\pi(10) = 4$ (the primes $2, 3, 5, 7$), $\pi(10.5) = 4$ too, and $\pi(100) = 25$. The letter has nothing to do with $3.14159\ldots$; it always comes with its argument, so the two never get confused. We also write $p_n$ for the $n$th prime: $p_1 = 2$, $p_2 = 3$, $p_3 = 5$, and $\pi(p_n) = n$. Here's $\pi(x)$ drawn up to $200$, next to Gauss's guess.
The staircase climbs by one at each prime, and its steps get wider. Count a few yourself; watch out for $1$, which isn't prime, and for numbers like $91 = 7 \cdot 13$ that look prime and aren't.
Loading practice engine...
Euclid's argument already gives a lower bound on how fast the primes come. Apply it to the first $n$ primes: $p_1 \cdots p_n + 1$ has a prime factor off the list, so that factor is at least $p_{n+1}$. Push that through an induction.
For every $n \ge 1$, $p_n \le 2^{2^{n-1}}$. Consequently $\pi(x) > \log_2 \log_2 x$ for every $x \ge 2$.
Proof. Strong induction on $n$. For $n = 1$, $p_1 = 2 = 2^{2^0}$. Suppose $p_j \le 2^{2^{j-1}}$ for $j = 1, \ldots, n$. A prime factor $q$ of $N = p_1 \cdots p_n + 1$ is none of $p_1, \ldots, p_n$, so $q \ge p_{n+1}$, and $q \le N$. Hence $$p_{n+1} \le p_1 p_2 \cdots p_n + 1 \le 2^{1 + 2 + 4 + \cdots + 2^{n-1}} + 1 = 2^{2^n - 1} + 1 \le 2^{2^n}.$$
For the second claim, let $n = \lfloor \log_2 \log_2 x \rfloor + 1$, so $n \ge 1$ and $n - 1 \le \log_2 \log_2 x$. Then $p_n \le 2^{2^{n-1}} \le 2^{2^{\log_2 \log_2 x}} = x$, so the $n$ primes $p_1, \ldots, p_n$ are all $\le x$, and $\pi(x) \ge n > \log_2 \log_2 x$. $\blacksquare$
That bound is laughably weak: it says $\pi(10^9) > 4.9$, when the truth is over fifty million. But it's honest, and it only used Euclid. A cleverer count does much better, and it's worth trying yourself.
(Erdős.) Show that $\pi(N) \ge \frac{1}{2} \log_2 N$ for every integer $N \ge 1$. (Hint: write each $n \le N$ as $m^2 s$ with $s$ squarefree, and count the choices of $m$ and of $s$.)
Proof. For $1 \le n \le N$, let $m^2$ be the largest square dividing $n$ and $s = n / m^2$. Then $s$ is squarefree (if $q^2 \mid s$, then $(qm)^2 \mid n$, contradicting the choice of $m$), so $s$ is a product of distinct primes, all $\le N$. There are at most $2^{\pi(N)}$ such products, one for each subset of the primes up to $N$. And $m^2 \le n \le N$ gives at most $\sqrt N$ choices of $m$. Since $n$ is determined by the pair $(m, s)$, $$N \le 2^{\pi(N)} \sqrt N, \quad \text{so} \quad 2^{\pi(N)} \ge \sqrt N, \quad \pi(N) \ge \tfrac{1}{2} \log_2 N. \ \blacksquare$$
Remember that squarefree-times-square split. The Spicy Bonus uses it again.
The graph's dashed curve is $x / \log x$. Chebyshev proved $\pi(x)$ stays between two constant multiples of it, and the Prime Number Theorem (1896) says the ratio tends to $1$. Both get full proofs later in this course.
So the primes thin out, but how unevenly? Look at the gaps between consecutive primes. Sieve the numbers up to $200$ and hunt for long runs of composites.
Below $200$ the longest run is $114, \ldots, 126$, thirteen composites between $113$ and $127$. The runs grow, slowly, and here's the reason they have to: you can build a run as long as you like on purpose.
For every $k \ge 1$, the $k$ consecutive integers $(k + 1)! + 2, \ (k + 1)! + 3, \ \ldots, \ (k + 1)! + (k + 1)$ are all composite. So there are gaps between consecutive primes as long as you like.
Proof. Let $2 \le j \le k + 1$. Then $j$ is a factor of $(k + 1)! = 1 \cdot 2 \cdots (k + 1)$, and $j \mid j$, so $j \mid (k + 1)! + j$. Since $1 < j < (k + 1)! + j$, that's a proper divisor, so $(k + 1)! + j$ is composite. $\blacksquare$
The construction is correct and wildly wasteful. Compare its run to the first run that actually occurs.
Seven composites in a row first happen at $90, \ldots, 96$; the factorial trick puts them past $40{,}000$. Here's that comparison worked out.
Use the theorem to write down $7$ consecutive composite numbers, and compare with the first such run.
With $k = 7$, $(k + 1)! = 8! = 40320$, and $40322, 40323, \ldots, 40328$ are divisible by $2, 3, \ldots, 8$ in turn. The primes $89$ and $97$, though, already have $90, 91, \ldots, 96$ between them: $7$ composites, more than $400$ times closer to $0$.
Long gaps and infinitely many primes live together fine. What nobody can prove is the other direction: whether gaps of exactly $2$ (twin primes like $101, 103$) keep happening forever.
If primes go on forever, maybe a formula spits them out. Euler noticed that $n^2 + n + 41$ is prime for $n = 0, 1, 2, \ldots, 39$: forty primes in a row. It can't last, and the reason works for every polynomial.
Let $f$ be a nonconstant polynomial with integer coefficients. Then $f(n)$ is not prime for some $n \ge 1$.
Proof. Suppose $f(n)$ is prime for every $n \ge 1$, and let $p = f(1)$. For every $k \ge 0$, $1 + kp \equiv 1 \pmod p$, and a polynomial with integer coefficients respects congruences, so $f(1 + kp) \equiv f(1) \equiv 0 \pmod p$. A prime divisible by $p$ is $p$, so $f(1 + kp) = p$ for every $k$. Then $f - p$ has infinitely many roots $1, 1 + p, 1 + 2p, \ldots$, so it is the zero polynomial, and $f$ is constant. $\blacksquare$
The proof is constructive: once you know a prime value $f(a) = p$, the input $a + p$ gives a multiple of $p$. Here it is on Euler's polynomial.
$f(n) = n^2 + n + 41$ gives $f(1) = 43$. Find a composite value, and find the first one.
The proof says try $n = 1 + 43 = 44$: $f(44) = 1936 + 44 + 41 = 2021 = 43 \cdot 47$. Composite, as promised. The first failure comes sooner, at $n = 40$, where $f(40) = 1600 + 40 + 41 = 1681 = 41^2$. (That one comes from $f(0) = 41$: mod $41$, $f(n) \equiv n(n + 1)$, which is $0$ at $n \equiv 0$ and at $n \equiv -1 \equiv 40$.)
Break five famous prime-makers. Step $n$ by hand if you like, or jump straight to $a + p$.
Your turn. Any $n$ that makes $f(n)$ a multiple of $p$ (and bigger than $p$) is right when you type it.
Loading practice engine...
Polynomials are out. Fermat tried exponentials instead, numbers of the form $2^m + 1$. Most of them are obviously composite: $2^3 + 1 = 9$ and $2^6 + 1 = 65$, and in general an odd factor of $m$ gives away a factor.
If $2^m + 1$ is prime, with $m \ge 1$, then $m$ is a power of $2$.
Proof. If $m$ isn't a power of $2$, it has an odd factor $b > 1$: $m = ab$. With $x = 2^a$, since $b$ is odd, $$2^m + 1 = x^b + 1 = (x + 1)(x^{b-1} - x^{b-2} + \cdots - x + 1),$$ and $1 < 2^a + 1 < 2^m + 1$ because $1 \le a < m$. So $2^a + 1$ is a proper factor and $2^m + 1$ isn't prime. $\blacksquare$
The proof is a recipe for a factor. Here it is on a number whose exponent hides an odd factor.
Show that $2^{12} + 1 = 4097$ is not prime.
$12 = 4 \cdot 3$ has the odd factor $b = 3$, so take $a = 4$ and $x = 2^4 = 16$. Then $$2^{12} + 1 = 16^3 + 1 = (16 + 1)(16^2 - 16 + 1) = 17 \cdot 241.$$ The factor is $2^a + 1 = 17$, exactly as the proof promises.
That leaves only the exponents $m = 2^n$, and those numbers get their own name.
For $n \ge 0$, the $n$th Fermat number is $F_n = 2^{2^n} + 1$.
$F_0 = 3$, $F_1 = 5$, $F_2 = 17$, $F_3 = 257$, $F_4 = 65537$: all prime. In 1640 Fermat wrote that he believed every $F_n$ is prime.
Fermat checked $F_0$ through $F_4$, saw five primes, and called it a law. Euler checked $F_5$. I choose to believe Fermat was just tired.
Euler found $F_5 = 4294967297 = 641 \cdot 6700417$ in 1732, and no Fermat prime past $F_4$ has ever been found. But the Fermat numbers still prove something: no two of them share a factor. The key is that their product telescopes.
For every $n \ge 1$, $F_0 F_1 \cdots F_{n-1} = F_n - 2$.
Proof. Induction on $n$. For $n = 1$: $F_0 = 3 = 5 - 2 = F_1 - 2$. If $F_0 \cdots F_{n-1} = F_n - 2 = 2^{2^n} - 1$, then $$F_0 \cdots F_{n-1} F_n = (2^{2^n} - 1)(2^{2^n} + 1) = 2^{2^{n+1}} - 1 = F_{n+1} - 2. \ \blacksquare$$
Watch the telescoping happen: each new factor is $x + 1$ standing next to $x - 1$.
Now any common factor of $F_m$ and $F_n$ divides both $F_n$ and $F_n - 2$, so it divides $2$, and Fermat numbers are odd. That's Goldbach's proof of Euclid's theorem (1730).
If $m \ne n$, then $\gcd(F_m, F_n) = 1$. Consequently there are infinitely many primes.
Proof. Say $m < n$ and let $d = \gcd(F_m, F_n)$. By the theorem, $F_m \mid F_n - 2$, so $d \mid F_n - 2$, and $d \mid F_n$. Then $d \mid F_n - (F_n - 2) = 2$. Since $F_n$ is odd, $d = 1$. Now pick a prime factor $q_n$ of each $F_n$. No prime divides two different Fermat numbers, so $q_0, q_1, q_2, \ldots$ are all different: infinitely many primes. $\blacksquare$
Euler's factor $641$ wasn't luck. Here's a slick way to check it without dividing a ten-digit number.
Show that $641 \mid F_5 = 2^{32} + 1$.
The trick: $641 = 5 \cdot 2^7 + 1$ and also $641 = 5^4 + 2^4$. From the first, $5 \cdot 2^7 \equiv -1 \pmod{641}$; raise to the fourth power: $5^4 \cdot 2^{28} \equiv 1$. From the second, $5^4 \equiv -2^4$. Substitute: $-2^4 \cdot 2^{28} = -2^{32} \equiv 1$, so $2^{32} \equiv -1$, and $641 \mid 2^{32} + 1$.
Notice $641 = 5 \cdot 128 + 1$ is one more than a multiple of $2^7$. Prime factors of Fermat numbers always look like that, and proving it is a nice workout with orders.
Show that every prime factor $q$ of $F_n$ satisfies $q \equiv 1 \pmod{2^{n+1}}$. Deduce that for every $k \ge 1$ there are infinitely many primes $q \equiv 1 \pmod{2^k}$.
Proof. $F_n$ is odd, so $q$ is odd. From $q \mid F_n$, $2^{2^n} \equiv -1 \pmod q$, and squaring, $2^{2^{n+1}} \equiv 1$. So the order of $2$ in $(\mathbb{Z}/q\mathbb{Z})^\times$ divides $2^{n+1}$; it doesn't divide $2^n$, because $2^{2^n} \equiv -1 \not\equiv 1$ ($q$ is odd). So the order is exactly $2^{n+1}$. By Lagrange (or Fermat's little theorem), the order divides $|(\mathbb{Z}/q\mathbb{Z})^\times| = q - 1$, so $q \equiv 1 \pmod{2^{n+1}}$.
For the second part, fix $k$. For each $n \ge k - 1$, a prime factor of $F_n$ is $\equiv 1 \pmod{2^{n+1}}$, hence $\equiv 1 \pmod{2^k}$. The Fermat numbers are pairwise coprime, so these primes are all different. $\blacksquare$
The minus-sign cousins $2^m - 1$ behave the same way, with "power of $2$" replaced by "prime."
A Mersenne prime is a prime of the form $2^p - 1$, and every even perfect number comes from one. You showed there that if $2^k - 1$ is prime, then $k$ is prime: $2^a - 1$ divides $2^{ab} - 1$.
So the only candidates are the exponents that are prime, and like the Fermat numbers, they get a name whether or not they turn out prime.
For a prime $p$, the Mersenne number $M_p$ is $2^p - 1$.
$M_2 = 3$, $M_3 = 7$, $M_5 = 31$, $M_7 = 127$ are prime, but $M_{11} = 2047 = 23 \cdot 89$ is not. Prime $p$ is necessary, not enough. Still, look at those factors: $23 = 2 \cdot 11 + 1$ and $89 = 8 \cdot 11 + 1$. That's a theorem, and it's another proof that the primes never end.
Let $p$ be an odd prime. Every prime $q$ dividing $M_p = 2^p - 1$ satisfies $q \equiv 1 \pmod{2p}$. In particular $q > p$, so there are infinitely many primes.
Proof. $M_p$ is odd, so $q$ is odd. From $q \mid 2^p - 1$, $2^p \equiv 1 \pmod q$, so the order of $2$ mod $q$ divides $p$. It isn't $1$, since $2 \not\equiv 1 \pmod q$, so the order is $p$. By Fermat's little theorem $2^{q-1} \equiv 1 \pmod q$, so $p \mid q - 1$. Since $q - 1$ is even and $p$ is odd, $2p \mid q - 1$. Then $q \ge 2p + 1 > p$.
For the last claim: given any prime $p$, $M_p > 1$ has a prime factor $q$, and $q > p$ (for $p = 2$, $q = 3$). So no prime is the largest. $\blacksquare$
The theorem is how people actually hunt for Mersenne factors: you only test numbers $2kp + 1$. Here's the check on $M_{11}$.
Find a prime factor of $M_{11} = 2047$ using the theorem.
The candidates are $q \equiv 1 \pmod{22}$: $23, 45, 67, 89, \ldots$, and $45$ isn't prime. Test $23$: $2^{11} = 2048 = 89 \cdot 23 + 1$, so $2^{11} \equiv 1 \pmod{23}$ and $23 \mid 2047$. Then $2047 = 23 \cdot 89$, and $89 \equiv 1 \pmod{22}$ as well.
Try it on bigger ones. The candidates go in steps of $2p$; tap one to test it.
Your turn: find where the theorem says to start looking. Some versions ask about a Fermat number instead, using the exercise above.
Loading practice engine...
One more way to see that different Mersenne numbers share nothing: the gcd of two of them is another number of the same shape.
Show that $\gcd(2^a - 1, 2^b - 1) = 2^{\gcd(a, b)} - 1$ for all $a, b \ge 1$. Deduce that $\gcd(M_p, M_q) = 1$ for different primes $p, q$.
Proof. Write $a = tb + r$ with $0 \le r < b$. Then $$2^a - 1 = 2^r(2^{tb} - 1) + (2^r - 1),$$ and $2^b - 1 \mid 2^{tb} - 1$ (put $x = 2^b$ in $x^t - 1 = (x - 1)(x^{t-1} + \cdots + 1)$). So $\gcd(2^a - 1, 2^b - 1) = \gcd(2^b - 1, 2^r - 1)$. This is the Euclidean algorithm run on the exponents: repeating it replaces $(a, b)$ by $(b, r)$ until the remainder is $0$, at which point the pair is $(\gcd(a, b), 0)$ and $\gcd(2^{\gcd(a, b)} - 1, 2^0 - 1) = \gcd(2^{\gcd(a,b)} - 1, 0) = 2^{\gcd(a, b)} - 1$. For different primes, $\gcd(p, q) = 1$ and $2^1 - 1 = 1$. $\blacksquare$
Every odd prime is $\equiv 1$ or $\equiv 3 \pmod 4$. Are there infinitely many of each kind? Euclid's proof adapts to the $3$s with one twist: multiply by $4$ and subtract $1$.
There are infinitely many primes $p \equiv 3 \pmod 4$.
Proof. $3$ is one. Suppose $q_1, \ldots, q_k$ were all of them, and let $N = 4 q_1 \cdots q_k - 1$. Then $N \equiv 3 \pmod 4$, so $N$ is odd and every prime factor of $N$ is $\equiv 1$ or $3 \pmod 4$. A product of primes that are all $\equiv 1 \pmod 4$ is $\equiv 1 \pmod 4$, so some prime factor $r$ of $N$ is $\equiv 3 \pmod 4$. Then $r = q_i$ for some $i$, and $r$ divides $4 q_1 \cdots q_k - N = 1$, which is impossible. $\blacksquare$
The "minus $1$" is what makes $N \equiv 3$ rather than $\equiv 1$, and that's what forces a $3$-type factor. Here it is on a real list.
Run the proof on the list $3, 7, 11$.
$N = 4 \cdot 3 \cdot 7 \cdot 11 - 1 = 923 = 13 \cdot 71$. Here $13 \equiv 1 \pmod 4$, which the proof doesn't care about, and $71 \equiv 3 \pmod 4$: a new prime of the right kind, as promised.
Now try the same trick on the other team, with $4P + 1$. Predict first whether it'll work.
$4 \cdot 17 + 1 = 69 = 3 \cdot 23$: no factor $\equiv 1$ at all. That's the trap in copying the proof.
The trick only works when the forced class can't be faked by products. Primes $\equiv 1 \pmod 4$ multiply to $1$, but so do pairs of primes $\equiv 3$ ($3 \cdot 3 = 9 \equiv 1$), so $N \equiv 1 \pmod 4$ forces nothing. The same goes for $6P - 1$ (fine) versus $6P + 1$ (no good).
Your turn. Factor $N$ and pick out the prime the argument promises.
Loading practice engine...
The primes $\equiv 1 \pmod 4$ need a different idea, and you've already seen it.
An Exercise there proved infinitely many primes $p \equiv 1 \pmod 4$: a prime factor $p$ of $(2p_1 \cdots p_k)^2 + 1$ has $-1$ as a square mod $p$, and that forces $p \equiv 1 \pmod 4$.
The same shape of proof handles $6n + 5$; write it out yourself.
Show that there are infinitely many primes $p \equiv 5 \pmod 6$.
Proof. $5$ is one. Suppose $q_1, \ldots, q_k$ were all of them, and let $N = 6 q_1 \cdots q_k - 1$. Then $N \equiv 5 \pmod 6$, so $2 \nmid N$ and $3 \nmid N$, and every prime factor of $N$ is $\equiv 1$ or $5 \pmod 6$. A product of primes $\equiv 1 \pmod 6$ is $\equiv 1$, so some prime factor $r \equiv 5 \pmod 6$. Then $r = q_i$ for some $i$ and $r \mid 6q_1 \cdots q_k - N = 1$, which is impossible. $\blacksquare$
So far: $4n + 1$, $4n + 3$, $6n + 5$, each by its own trick. Dirichlet proved the whole family at once in 1837. First, though, notice when a progression has no chance: every term of $6n + 3$ is divisible by $3$, so the only prime in it is $3$ itself.
Let $k \ge 1$ and $a$ be integers with $\gcd(a, k) = 1$. Then there are infinitely many primes $p \equiv a \pmod k$.
No proof here: Dirichlet's argument needs characters and the functions $L(s, \chi)$, and Euclid-style tricks are known for only some progressions, never all. The condition $\gcd(a, k) = 1$ is exactly what's needed, since if $d = \gcd(a, k) > 1$ then every $p \equiv a \pmod k$ is divisible by $d$. Watch both effects at once: pick a modulus, raise $x$, and see which classes grow.
The coprime classes come out nearly even, and that's a theorem too (the Prime Number Theorem for progressions). Nearly even isn't exactly even, though. Here's the race between $1$ and $3$ mod $4$, counted one prime at a time.
The $1$s don't get ahead even once until $26{,}861$. That's a warning about trusting a pattern in a table, and a hint of Chebyshev's bias: classes of non-squares ($3$ isn't a square mod $4$) tend to stay in front.
A bonus there proved infinitely many primes $p \equiv 1 \pmod n$, for every $n$: prime factors of $\Phi_n(mN)$ are $\equiv 1 \pmod n$. So the class $1$ has a Euclid-style proof for every modulus.
One last fact about progressions: you only ever need one prime to get infinitely many. Try to see why before you open it.
Suppose you knew only that every progression $a, a + k, a + 2k, \ldots$ with $\gcd(a, k) = 1$ contains at least one prime. Show that every such progression contains infinitely many primes.
Proof. Fix $a, k$ with $\gcd(a, k) = 1$, and let $p_1, \ldots, p_m$ be any finitely many primes $\equiv a \pmod k$. None of them divides $k$ (a prime $p_i \mid k$ would divide $a$ too). So $k$ and $Q = p_1 \cdots p_m$ are coprime, and by the Chinese Remainder Theorem there is an $a'$ with $a' \equiv a \pmod k$ and $a' \equiv 1 \pmod Q$. Then $\gcd(a', kQ) = 1$, so by assumption some prime $p \equiv a' \pmod{kQ}$. This $p$ is $\equiv a \pmod k$, and $p \equiv 1 \pmod{p_i}$ for each $i$, so $p$ is none of the $p_i$. No finite list holds them all. $\blacksquare$
Here's a sharper way to ask "how many primes": add up their reciprocals. The squares are infinite too, but $\frac{1}{1} + \frac{1}{4} + \frac{1}{9} + \cdots$ converges (to $\frac{\pi^2}{6}$), because squares are sparse. Euler proved the primes are not that sparse.
The series $\displaystyle\sum_p \frac{1}{p} = \frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \frac{1}{7} + \cdots$, over all primes, diverges.
Proof (Clarkson). Suppose it converges. Then its tails go to $0$, so there is a $k$ with $\sum_{i > k} \frac{1}{p_i} < \frac{1}{2}$. Let $Q = p_1 \cdots p_k$, and look at the numbers $1 + nQ$ for $n = 1, 2, 3, \ldots$ None of $p_1, \ldots, p_k$ divides $1 + nQ$, so every prime factor of $1 + nQ$ is one of $p_{k+1}, p_{k+2}, \ldots$. If $1 + nQ$ has $t$ prime factors (counted with repeats), then $\frac{1}{1 + nQ}$ is one of the terms you get by multiplying out $\left(\sum_{i > k} \frac{1}{p_i}\right)^t$. Different $n$ give different terms, and all terms are positive, so for every $r$, $$\sum_{n=1}^{r} \frac{1}{1 + nQ} \le \sum_{t=1}^{\infty} \left(\sum_{i > k} \frac{1}{p_i}\right)^t \le \sum_{t=1}^{\infty} \frac{1}{2^t} = 1.$$ But $\frac{1}{1 + nQ} \ge \frac{1}{(1 + Q)n}$, and $\sum \frac{1}{n}$ diverges, so the partial sums on the left are unbounded. Contradiction. $\blacksquare$
Divergence of $\sum \frac{1}{p}$ includes Euclid's theorem for free: a finite sum can't diverge. It says more, too. If $\pi(x)$ were at most $C\sqrt{x}$, the primes would be about as sparse as the squares and the sum would converge. Euler's own argument was different, and it measures how fast the sum grows. It starts from a product.
Find $\displaystyle\sum \frac{1}{n}$ over every $n \ge 1$ whose only prime factors are $2$ and $3$.
Each such $n$ is $2^a 3^b$ in exactly one way, so the sum splits into a product of two geometric series: $$\left(1 + \tfrac{1}{2} + \tfrac{1}{4} + \cdots\right)\left(1 + \tfrac{1}{3} + \tfrac{1}{9} + \cdots\right) = \frac{1}{1 - \frac12} \cdot \frac{1}{1 - \frac13} = 2 \cdot \frac{3}{2} = 3.$$ Unique factorization is what makes each $\frac{1}{n}$ appear exactly once.
Use all the primes up to $x$ instead of just $2$ and $3$, and every $n \le x$ shows up in the product. Watch the tiles fill in.
So the product over $p \le x$ is at least $1 + \frac12 + \cdots + \frac1x$, which is bigger than $\log x$. Take logarithms and the product becomes a sum over primes.
For every $x \ge 2$, $$\sum_{p \le x} \frac{1}{p} > \log \log x - 1.$$
Proof. Each factor below is a convergent geometric series, and multiplying them out gives $\frac{1}{n}$ for every $n$ whose prime factors are all $\le x$, each exactly once (unique factorization). That includes every $n \le x$, so $$\prod_{p \le x} \left(1 - \frac{1}{p}\right)^{-1} = \prod_{p \le x} \left(1 + \frac{1}{p} + \frac{1}{p^2} + \cdots\right) \ge \sum_{n \le x} \frac{1}{n} \ge \int_1^{\lfloor x \rfloor + 1} \frac{dt}{t} > \log x.$$ Take logarithms: $\sum_{p \le x} -\log\left(1 - \frac{1}{p}\right) > \log \log x$. For $0 < u \le \frac12$, $$-\log(1 - u) = u + \frac{u^2}{2} + \frac{u^3}{3} + \cdots \le u + u^2(1 + u + u^2 + \cdots) = u + \frac{u^2}{1 - u},$$ and with $u = \frac1p$ that's $\frac1p + \frac{1}{p(p - 1)}$. Finally $\sum_{p} \frac{1}{p(p-1)} \le \sum_{n \ge 2} \left(\frac{1}{n - 1} - \frac{1}{n}\right) = 1$. So $\sum_{p \le x} \frac{1}{p} + 1 > \log \log x$. $\blacksquare$
Your turn with Euler's product. Each prime contributes its own geometric series, and they multiply.
Loading practice engine...
So the sum grows at least like $\log \log x$, and (Mertens, below) no faster. Drag the slider to see how slow that is.
At $x = 10^6$ the prime sum is about $2.89$, and $\log \log 10^6 \approx 2.63$. The gap stays near $0.26$ the whole way.
It "diverges." Add $\frac{1}{p}$ over every prime up to $10^{80}$, about one per atom in the universe, and you're still under $6$. "Diverges" is doing a lot of work here.
That constant gap is Mertens' theorem, the next step after this page.
Mertens proved $\sum_{p \le x} \frac{1}{p} = \log \log x + M + O\!\left(\frac{1}{\log x}\right)$ with $M \approx 0.2615$, the gap you just watched.
Every question so far came right after its idea, which is a hint. Down here the hint is gone. First, true or false: a claim about anything on this page, some of them the kind that sounds right and isn't. Decide, then read why.
Loading practice engine...
Next, a proof from this page with one piece missing. Every wrong choice is false or doesn't follow.
Loading practice engine...
Next, the mixed set. Every question type on this page except true or false goes into one hat, and each click draws a new one at random. Flip the switch to type your answer; a few types need their answer choices, and they'll say so.
Loading practice engine...
Last, the Spicy Bonus: Erdős's proof that $\sum \frac{1}{p}$ diverges, built from the squarefree-times-square count in the Counting Primes exercise.
Prove that $\sum_p \frac{1}{p}$ diverges without Euler's product. Suppose it converges, and pick $k$ with $\sum_{i > k} \frac{1}{p_i} < \frac{1}{2}$. For a large integer $N$, split $1, 2, \ldots, N$ into the small numbers, whose prime factors are all among $p_1, \ldots, p_k$, and the big ones, divisible by some $p_i$ with $i > k$. Count both kinds and reach a contradiction.
Proof (Erdős). Big numbers. The multiples of $p_i$ up to $N$ number $\lfloor N / p_i \rfloor \le N / p_i$, so the big numbers number at most $$\sum_{i > k} \frac{N}{p_i} < \frac{N}{2}.$$
Small numbers. Write a small $n$ as $m^2 s$ with $s$ squarefree, as in the Erdős exercise. Every prime factor of $s$ is among $p_1, \ldots, p_k$, and $s$ is squarefree, so $s$ is the product of one of the $2^k$ subsets of $\{p_1, \ldots, p_k\}$. And $m \le \sqrt N$. So there are at most $2^k \sqrt N$ small numbers.
Every $n \le N$ is small or big, so $N < \frac{N}{2} + 2^k \sqrt N$, which says $\sqrt N < 2^{k+1}$. Taking $N = 2^{2k+2}$ gives $\sqrt N = 2^{k+1}$, a contradiction. So the series diverges. $\blacksquare$