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.
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.