The Distribution of Primes and What Is Still Open
Prove that the primes never run out, learn an estimate of how thinly they spread, and see what is still unknown.
What a learner can do afterwards
- Give Euclid's proof that the primes are infinite and one other proof of the same fact
- State the prime number theorem and use it to estimate a prime count
- Describe an open problem about primes precisely enough to say what a solution would need to establish
1 · Read
A prime is an integer greater than 1 with exactly two positive divisors. Every N > 1 has a prime divisor: its least divisor greater than 1 cannot be composite. For a finite nonempty prime list, form its product P and N = P + 1. Each listed prime divides P and leaves remainder 1 in N, so none divides N. A prime divisor of N lies outside the list. Thus no finite list contains every prime. N need not be prime: 2 x 7 + 1 = 15 = 3 x 5.
Starting with 2 and 7 gives 15. Its prime divisors 3 and 5 are both outside that list.
Write pi(x) for the number of primes at most x. For an exact count, exclude 1. Keep each sieving prime p and cross out its multiples starting at p squared. Every composite integer has a prime divisor at most its square root, so stop once p squared exceeds the bound. Up to 20, sieving with 2 and 3 leaves eight primes. To count primes in a < p <= b, subtract pi(a) from pi(b).
The sieve keeps 2 and 3 themselves. It removes their composite multiples.
For n >= 0, the Fermat number is F_n = 2^(2^n) + 1. These odd integers begin 3, 5, 17, 257. For n >= 1, F_0 x ... x F_(n-1) = F_n - 2. Prove this by induction, starting with 3 = 5 - 2. Multiplying the identity by F_n gives (A - 1)(A + 1) = A^2 - 1 = F_(n+1) - 2, where A = 2^(2^n).
At n = 2, the product of the earlier terms equals F_2 - 2.
For m < n, any common positive divisor d of F_m and F_n divides the product F_0 x ... x F_(n-1) = F_n - 2. Since it also divides F_n, it divides 2. Both terms are odd, so d = 1. Thus distinct terms are coprime: they share no divisor greater than 1. Choose a prime divisor of each term. No prime can divide two terms, so infinitely many terms give infinitely many distinct primes. The Fermat numbers need not all be prime.
For x > 1, ln x is the natural logarithm. The prime number theorem states that pi(x)/(x/ln x) tends to 1 as x tends to infinity. Thus x/ln x estimates the count of primes at most x, with relative error tending to zero. This limiting statement gives no numerical error bound at a chosen x. It neither gives an exact finite count nor lists the primes.
To estimate a count, enter x on a scientific calculator and use the ln function, not base-10 log. Divide x by that result and round only at the end. For x = 1000, ln x is about 6.90776, so x/ln x is about 144.765 and rounds to 145. The exact count is 168. This finite difference neither contradicts nor proves the limiting theorem.
Both bars refer to the same bound, 1000.
Divide the estimated count x/ln x by x to get 1/ln x. This estimates the fraction of integers from 1 to x that are prime. For example, ln x = 10 gives an estimated fraction of 1/10, or 10 percent. Multiply the fraction by 1000 to express it per thousand integers across the whole range. This does not predict the count in each short interval.
A whole-range fraction is not a count promised for every block of integers.
Twin primes are two primes differing by 2, such as 5 and 7. The twin prime conjecture says there are infinitely many such pairs. It remains open. A proof would show that pairs occur beyond every bound. A disproof would show that only finitely many pairs exist. More examples, however large, do not settle the infinitude claim.
This pair illustrates the definition. It does not prove that infinitely many pairs exist.
The strong Goldbach conjecture says every even integer greater than 2 is a sum of two primes. The primes may be equal. It remains open. A proof must cover every even integer greater than 2. A disproof needs one such integer with no representation as a sum of two primes. Checking many examples does not prove this universal claim.
Equal prime summands are allowed. Each displayed sum is an example, not a proof of the conjecture.
Two proofs show infinitely many primes. The prime count is asymptotic to x/ln x. Twin-prime infinitude and strong Goldbach remain open.
Original lesson, practice questions and flashcards written for this dataset.
The readings and additional practice questions were written for this dataset. The flashcards include material from the hoofer-content facts collection, with corrections.
More to read
A prime missing from any finite list
Take any finite nonempty list of primes and call their product P. Form N = P + 1. Every prime in the list divides P. It cannot also divide N, because it would then divide N - P = 1.
Why does N have a prime divisor? Among its positive divisors greater than 1, choose the least, d. If d were composite, it would have a factor strictly between 1 and d that also divides N. That contradicts the choice of d. So d is prime, and it is absent from the list.
The argument works even when N is composite. Starting with 2 and 7 gives N = 15. Both of its prime divisors, 3 and 5, are new to that list. There is no need for the constructed number itself to be prime. Since every finite list misses a prime, there are infinitely many primes.
Another infinitude proof using Fermat numbers
Define F_n = 2^(2^n) + 1 for integers n >= 0. The first terms are 3, 5, 17 and 257. For every n >= 1, the product F_0 x ... x F_(n-1) equals F_n - 2.
Induction proves the identity. The first case is 3 = 5 - 2. For the next step, multiply F_n - 2 by F_n. Writing A = 2^(2^n), this becomes (A - 1)(A + 1) = A^2 - 1 = F_(n+1) - 2.
If m < n, any common positive divisor of F_m and F_n divides both F_n - 2 and F_n, so it divides 2. Fermat numbers are odd, which forces that divisor to be 1. Thus different terms share no prime divisor.
Every term exceeds 1, so choose a prime divisor from each. The choices must all be different. Infinitely many terms therefore supply infinitely many primes. This proof does not require every Fermat number to be prime.
What prime counts can tell us
The function pi(x) counts primes at most x. A sieve can give an exact count at a finite bound. Subtracting pi(a) from pi(b) counts primes in a < p <= b.
The prime number theorem says pi(x)/(x/ln x) tends to 1 as x tends to infinity. The logarithm is natural. The theorem makes x/ln x an asymptotic estimate, not an exact finite count. Its limiting statement alone supplies no numerical error bound at a selected x. Dividing by x gives the whole-range prime fraction approximately 1/ln x, not a count guaranteed in each short interval.
Two further claims remain open. The twin prime conjecture asks for infinitely many pairs of primes differing by 2. A proof must put such pairs beyond every bound; a disproof must establish that only finitely many exist.
The strong Goldbach conjecture asks whether every even integer greater than 2 is a sum of two primes, allowing equal summands. A proof must cover every such integer. One integer with no representation would disprove it. Neither conjecture is settled by collecting examples or by the prime number theorem alone.
2 · Watch
به انگلیسیTake it off screen
Where it sits
Learn first
Optional connections
This opens up
Nothing builds on it yet.
17 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.