# The Prime Page

First, the basic definition:

A prime number is a natural number with exactly two positive divisors: itself and 1.

Some examples are 2, 7, 97, and 2729. (Note that with only one divisor, 1 is not a prime.)

Prime numbers are fascinating on their own, but have lots of cool and scary applications!

## How do you tell "primes" from "non-primes"?

If I give you a small number, like 15, you can tell it's not prime because 15 = 3 × 5, so that 15 has divisors other than 1 and 15 itself. Numbers like this are called composite numbers.

If you have a larger number like 91 or 97 you have to work a little; try dividing in small primes in order:

2, 3, 5, 7, 11, . . . (see table below).

If any of them go into your number evenly, it's composite.

With 91 you try 2, 3, and 5; they don't go in evenly (they leave a remainder); but 91 ÷ 7 = 13.

This means 91 = 7 × 13, so it's not a prime after all.

What about 97? None of those little primes 2, 3, 5, or 7 go into 97. When can we stop? At 97? 50?

Well, the next prime is 11 and if 11 went into 97, then 11 × m = 97. But 11 × 11 = 121 97, and we already tested all the numbers m 11. So 97 must be prime; we can stop!

A number is prime if no prime, whose square is less than the number, goes into the number.

This trick is sometimes called The Sieve of Erasthosthenes after its inventor, the ancient Greek mathematician Erasthosthenes of Cyrene (276-194 B.C.).

## Table of the First 400 Prime Numbers:

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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741

## Do the primes ever stop? They seem to be getting farther apart...

There are 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

But there are only 21 in the next 100:

101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199

And just 16 in the third 100:

211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293.

Here's some heavy math, if you're interested:

## The Prime Number Theorem

Let π(n) represent the number of primes less than a number n. (So, for example, π(10) = 4 since there are four primes less than ten: 2, 3, 5, and 7.)

Then

where ≈ means that for big numbers n, the left side and the right side are close, and ln n means the natural logarithm of n.

This theorem can be used to approximate the number of primes less than a certain number. (There are better estimates, but we're getting into some serious college-level stuff here.)

Note this is a completely different use of the symbol π than the usual 3.14159... one.

## Infinitely Many Primes

Euclid proved over 2400 years ago that there are an infinite number of primes. He used the following proof by contradiction.

Suppose there are a finite number of primes. Then let p1, p2, p3, . . . , pk be the whole list.

Define N = (p1 × p2 × p3× . . . × pk) + 1.

Then none of the known primes goes into N because they all leave a remainder of 1.

So either N is a new prime or else it factors into primes that are not on our list!

This contradicts the assumption of the finite list of primes.

Q.E.D.

## Twin Primes

Twin primes are consecutive odd numbers that are both prime, like 11 and 13, or 227 and 229.

If you look carefully at the big list up above, you'll see that even though generally the primes are getting farther and farther apart, you still run into a few twin primes in the high numbers... for example, 2729 and 2731.

QUESTION: Are there infinitely many pairs of twin primes?