Take the number 2 and raise it to larger and larger powers. Divide each result by 7 and note the remainder: Power $2^1$ $2^2$ $2^3$ $2^4$ $2^5$ $2^6$ Value 2 4 8 16 32 64 Remainder mod 7 2 4 1 2 4 1 At $2^6$ the remainder is 1. Now try 3 and the prime 5: $3^4=81$, which leaves remainder 1 when divided by 5. And 10 and the prime 13: $10^{12}=1{,}000{,}000{,}000{,}000$, which also leaves remainder 1 when divided by 13.
Mathematicians have always dreamed of a formula that produces only prime numbers. In 1640 Fermat thought he had found one. Five primes in a row Fermat studied numbers of the form $$F_n=2^{2^n}+1.$$The exponent is a power of 2: $1,2,4,8,16,\ldots$ Computing the first few: $$F_0=3,\quad F_1=5,\quad F_2=17,\quad F_3=257,\quad F_4=65{,}537.$$All five are prime. Checking $65{,}537$ by hand, trying divisors up to its square root, was already hard work. Fermat wrote to Frénicle de Bessy that he was convinced all numbers of this form were prime, although he admitted he had no proof.
The function that bears Riemann’s name was studied earlier by Euler. For a real number $s$ greater than 1, the series $$\zeta(s) = 1 + \frac{1}{2^s} + \frac{1}{3^s} + \frac{1}{4^s} + \cdots = \sum_{n=1}^{\infty}\frac{1}{n^s}$$converges. Euler computed several of its values, such as $\zeta(2) = \frac{\pi^2}{6}$, the solution of the Basel problem. Euler’s product Euler’s deepest discovery, of 1737, was that the same function can be written as a product over the prime numbers:
The prime numbers seem to appear at random: 2, 3, 5, 7, 11, 13, then a gap until 17, 19, 23, another until 29. But seen from afar, they obey a rule. Call $\pi(x)$ the number of primes less than or equal to $x$. While still a teenager, Gauss noticed, looking at tables, that near a number $x$ the density of primes is about $\frac{1}{\ln x}$, and proposed the estimate $$\pi(x) \approx \operatorname{li}(x) = \int_0^x \frac{dt}{\ln t},$$the logarithmic integral. Nobody knew how to prove that it was good, nor how to explain the deviations.
In the middle of the 1859 paper on prime numbers, Riemann writes a sentence almost in passing. Speaking of a function linked to zeta, whose real roots correspond to the zeros of zeta on the critical line, he says: It is very probable that all the roots are real. One would of course wish for a rigorous proof of this; but I have, after some fleeting vain attempts, provisionally put aside the search for one, since it did not seem necessary for the next objective of my investigation. — Bernhard Riemann, On the Number of Primes Less Than a Given Magnitude (1859)
Eratosthenes and the sieve of numbers Eratosthenes lived in the 3rd century BC and is remembered for a method of finding cousins: the sieve. Think of a sieve that removes composite numbers and leaves the primes visible. Your turn to investigate: Write the numbers 2 to 20. Preserve 2 and cross out its multiples greater than it; then do the same with 3. What numbers are there? Discover the historical source on MacTutor, from the University of St Andrews.