dansmath > lessons > number theory > primes

dan's prime page (updated 11/02)
also see supercomposites - the opposite of prime!

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). The first one to go into your number (if any) means it was 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. Sometimes a number can be really stubborn.

What about 97? None of those little primes 2, 3, 5, 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 > 97 and we
already tried all m < 11, so 97 must be prime; we can stop! This gives us the 'phrase that pays':
A number (> 3) is prime if no prime, whose square is less than the number, goes into the number!

Table of the First 400 Prime Numbers : (17 being, of course, the most random)

Simple Mathematica Command: Table[Prime[k], {k, 1, 400}]

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

Dan's note: When I was a kid, my 'World Almanac' had the primes up to 997; a local high school
teacher let me make an old computer chunk away up to 2729 until my mom pulled me away.

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.

The famous Prime Number Theorem states : "The number (n) of primes up to n is
approximated by (n) ~ n / log(n), log(n) = ln(n) is the natural log, and the 'pi' is not 3.14159...
The symbol ~ means that as n goes to infinity, the ratio [(n)] / [n / log(n)] approaches 1.
For example (100) = 25 while 100 / log(100) = 100 / 4.605 = 21.715 (not very good; over 15% error)
and (1000) = 168 and 1000 / log(1000) = 1000 / 6.908 = 144.76 (now 16% error but eventually improves)
This also implies that the kth prime is approximately equal to k log(k) ; 168 log 168 = 861 ; p168 = 997.

Euclid proved over 2400 years ago that there are an infinite number of primes:
"Suppose not: 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."
For example, if 2, 3, and 5 were the only known primes, then N = 2*3*5 + 1 = 31; a new prime!

Table of World Record Primes (by year, Electronic Computer Age)

2^32,582,657 - 1 is currently the largest known prime (discovered September 2006)

This has 9,808,358 digits; we are very close to the ten million digit barrier!

It's a prime example of a Mersenne prime, one of the form 2^p - 1 , where p is a prime number.

If n is odd & composite then so is 2^n - 1: n = ab --> 2^n - 1 = (2^a - 1)[2^(n-a) + 2^(n-2a) + . . . + 2^a + 1]
Ex: 2^9 - 1 = (2^3 - 1)(2^6 + 2^3 + 1), so 2^9 - 1 = 511 = (8-1)(64+8+1) = 7 * 73 is composite.
But 11 is prime, and 2^11 - 1 is not; although you can't factor it with this formula.

The notation Mp means 2^p - 1. (If p is not prime then 2^p - 1 isn't either.) M2 = 3, M3 = 7, M7 = 127 ;
The largest known prime from 1876-1950 was M127 = 170,141,183,460,469,231,731,687,303,715,884,105,727.

Here is a table of the "World Record Primes" by year from Chris Caldwell's Prime Pages,
www.utm.edu/research/primes/ . . . Click here for early history of prime size

 Number Digits Year Machine Prover 180(M127)^2+1 79 1951 EDSAC1 Miller & Wheeler M521 157 1952 SWAC Robinson (Jan 30) M607 183 1952 SWAC Robinson (Jan 30) M1279 386 1952 SWAC Robinson (June 25) M2203 664 1952 SWAC Robinson (Oct 7) M2281 687 1952 SWAC Robinson (Oct 9) M3217 969 1957 BESK Riesel M4423 1,332 1961 IBM7090 Hurwitz M9689 2,917 1963 ILLIAC 2 Gillies

 M9941 2,993 1963 ILLIAC 2 Gillies M11213 3,376 1963 ILLIAC 2 Gillies M19937 6,002 1971 IBM360/91 Tuckerman M21701 6,533 1978 Cyber 174 Noll & Nickel (H.S.students) M23209 6,987 1979 Cyber 174 Noll M44497 13,395 1979 Cray 1 Nelson & Slowinski M86243 25,962 1982 Cray 1 Slowinski M132049 39,751 1983 Cray X-MP Slowinski M216091 65,050 1985 Cray X-MP Slowinski 391581* 2^216193 - 1 65,087 1989 Amdahl 1200 Amdahl Six

 M756839 227,832 1992 Cray-2 Slowinski & Gage M859433 258,716 1994 Cray C90 Slowinski & Gage M1257787 378,632 1996 Cray T94 Slowinski & Gage M1398269 420,921 1996 Pentium 90 Armengaud, Woltman M2976221 895932 1997 Pentium 100 Spence, Woltman M3021377 909,526 1998 Pentium 200 Clarkson, Woltman, Kurowski M6972593 2,098,960 1999 Pentium 350 Hajratwala, Woltman, Kurowski M13466917 4,053,496 2001 AMD 800 Cameron, Woltman, Kurowski M20996011 6,320,430 2003 Pentium 2G Michael Shafer & GIMPS M24036583 7,235,733 2004 P4 2.4GHz Josh Findley & GIMPS M25964951 7,816,230 2005 P4 2,4GHz Nowak using GIMPS M30402457 9,152,052 2005 P4 3.0GHz Cooper, Boone, GIMPS M32582657 9,808,358 2006 P4 3.0GHz Cooper, Boone, GIMPS et al.

All of the Mersenne records were found using the Lucas-Lehmer test and the other two were found using Proth's Theorem (or similar results).
The Amdahl Six is J. Brown, C Noll, B Parady, G Smith, J Smith and S Zarantonello.

[ home | info | meet dan | ask dan | matica | prob of week | lessons | dvc ]

This site maintained by B & L Web Design, a division of B & L Math Enterprises