Primes and the Sieve
Tonight's idea
A prime is a whole number bigger than 1 whose only factors are 1 and itself. 7 is prime. 15 is not, because \(15 = 3 \times 5\).
The big fact: every whole number bigger than 1 is either prime, or can be written as a product of primes in exactly one way (apart from the order). \(360 = 2 \times 2 \times 2 \times 3 \times 3 \times 5\), and there is no other recipe. That is why mathematicians call primes the atoms of arithmetic.
Why isn't 1 prime? If it were, the "exactly one way" part would break: \(6 = 2\times3 = 1\times2\times3 = 1\times1\times2\times3\ldots\) So we leave 1 out on purpose.
Watch one: is 91 prime?
You only need to test prime divisors, and you can stop once the divisor squared is bigger than the number. Here \(10^2 = 100 > 91\), so test only 2, 3, 5, 7.
2? No, 91 is odd. 3? Digits add to 10, not a multiple of 3, so no. 5? Doesn't end in 0 or 5. 7? \(7 \times 13 = 91\). Not prime.
Why can you stop at 10? If \(91 = a \times b\) with both \(a\) and \(b\) bigger than 10, the product would be bigger than 100. So at least one factor is 10 or less.
Your turn
- Run the sieve. In the grid below: cross out 1. Circle 2, then cross out all the other multiples of 2 (4, 6, 8, …). Circle 3 and cross out its remaining multiples. Do the same for 5 and 7. Then stop, because \(11^2 = 121\) is off the grid. Everything left is prime. How many primes are there under 100?
12345678910 11121314151617181920 21222324252627282930 31323334353637383940 41424344454647484950 51525354555657585960 61626364656667686970 71727374757677787980 81828384858687888990 919293949596979899100
- Is 221 prime? Use the stopping trick: which primes do you actually need to test?
- Write each as a product of primes: \(360\), \(1001\), \(2^{10}\) (that last one is a trick question).
- Twin primes are primes that differ by 2, like 11 and 13. List every twin-prime pair under 50.
- Explain in one sentence why 2 is the only even prime.
- Find six numbers in a row under 100 with no prime among them. (Your sieve grid will show you.)
Stretch: do the primes ever run out?
Euclid proved they don't, 2,300 years ago, and his argument fits in four lines. Suppose you had a complete list of primes: \(2, 3, 5, 7, \ldots, p\). Multiply them all together and add 1. Call that number \(N\).
Divide \(N\) by any prime on your list. What remainder do you get? So what can you say about the prime factors of \(N\)? Why does that mean your list was never complete?
Try it with the list \(2, 3, 5\): \(N = 31\). Now try \(2, 3, 5, 7, 11, 13\): \(N = 30031\). Is 30031 prime? (Hint: it isn't. Try 59.) Does that break Euclid's argument?
Answers
- 25 primes under 100: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.
- \(15^2 = 225 > 221\), so test only 2, 3, 5, 7, 11, 13. \(221 = 13 \times 17\). Not prime.
- \(360 = 2^3 \times 3^2 \times 5\). \(1001 = 7 \times 11 \times 13\). \(2^{10}\) is already a product of primes: ten 2s.
- (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43).
- Every even number is a multiple of 2, so any even number other than 2 has 2 as an extra factor.
- 90, 91, 92, 93, 94, 95, 96. (Also 74–78 is a run of five.)
Stretch. Dividing \(N\) by any prime on the list leaves remainder 1, so none of them divides \(N\). But \(N\) must have at least one prime factor (every number bigger than 1 does). That prime is not on the list, so the list was incomplete. This works for any finite list, so there is no finite list: infinitely many primes. \(30031 = 59 \times 509\) is not prime, and that is fine: the argument never claimed \(N\) is prime, only that it has a prime factor missing from the list. Here 59 and 509 are both missing.