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