Misplaced Pages

Revision as of 20:42, 24 March 2002

A prime number, or prime for short, is a natural number larger than 1 that has as its only positive divisors (factors) 1 and itself. The first 20 prime numbers are

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71.

If a number greater than one is not a prime number then it is called a composite number. Integers are considered to be prime if they are either a prime natural number or the negative of one.

Representing natural numbers as products of primes

An important result is the fundamental theorem of arithmetic, which states that every natural number can be written as a product of primes, and in essentially only one way. Primes are thus the "basic building blocks" of the natural numbers. For example, we can write

23244 = 2 · 3 · 13 · 149.

How many prime numbers are there?

There are infinitely many prime numbers. The oldest known proof for this statement dates back to the Greek mathematician Euclid:

Assume that there is only a finite number of primes. If you multiply all the primes together, and add one, the resulting number, when divided by any of the primes, has a remainder of one. Therefore it cannot be divided by any of what were supposedly all the primes, and it must be another prime, or divisible by a prime that we have omitted from our list of all the primes. We arrive at a contradiction, so our original assumption (that there is a finite number of primes) must be false. So there are an infinite number of primes.

Some mathematicians gave their own proofs as for example Kummer, probably the most elegant one and Furstenberg with topological terms.

Even though the total number of primes is infinite, one could still ask "how many primes are there below 100,000" or "How likely is a random 100-digit number to be prime?" Questions like these are answered by the prime number theorem.

Finding prime numbers

An efficient way to compute a list of all the prime numbers up to a given limit is the algorithm called the "Sieve of Eratosthenes". To find all prime numbers between 1 and n:

1. Write down the numbers 2, 3, 4, ... n. We will eliminate composites by marking them. Initially all numbers are unmarked.
2. Find the smallest number in the list that has not yet been identified as composite or prime. (The first number so found is 2.) Call it m and mark it as prime.
3. Mark all multiples of m (2m, 3m, 4m, ...) as composite.
4. Go back to step 2 and repeat with the next smallest number. Stop if every number in the list has been marked composite or prime.

A large random number (say, up to a few thousand digits), can be partly tested for primality with Fermats little theorem or the Miller-Rabin test. Other primality tests are also possible. These probabilistic tests typically work by picking a random number (a witness), and checking some formula involving the witness and the potential prime. These tests are not perfect. For a given test, there may be some composite numbers that will be declared "probably prime" no matter what witness is chosen. Such numbers are called pseudoprimes for that test.

Some special types of primes

A prime p is called primorial or prime - factorial if it has the form p = Π(n) ± 1, where Π(n) stands for the product 2 · 3 · 5 · 7 · 11 · ... of all the primes ≤ n. A prime is called factorial if it is of the form n! ± 1. The first factorial primes are:

n!+1 is prime for n = 3, 4, 6, 7, 12, 14, 30, 32, 33, 38, 94, 166,...
n!-1 is prime for n = 1, 2, 3, 11, 13, 27, 37, 41, 73, 77, 116, 154...

The base-ten digit sequences of primes can be a palindrome as in the prime 10 + 9700079 · 10 + 1.

Some properties

• If p is a prime number and p divides a product ab of integers, then p divides a or p divides b.

• The ring Z_n (see modular arithmetic) is a field if and only if n is a prime.
• The characteristic of every field is either zero or a prime number.
• If p is prime and a is any integer, then a - a is divisible by p (Fermat's little theorem).
• If G is a finite group and p is the highest power of the prime p which divides the order of G, then G has a subgroup of order p. (Sylow theorems)
• If p is prime and G is a group with p elements, then G contains an element of order p.
• A number p is prime if and only if the factorial (p-1)! + 1 is divisible by p (Wilson's theorem).
• If n is a natural number, then there is always a prime number p with n < p ≤ 2n (Bertrand's postulate).
• Adding the reciprocals of all primes together results in a sum of infinity.

Formulas yielding prime numbers

The curious polynomial f(n) = n - n + 41 yields primes for n = 0,..., 40, but f(41) is composite. There is no polynomial which only yields prime numbers in this fashion.

There exists a polynomial in 26 variables with integer coefficients such that, if you plug in integers for the variables, the set of positive values is equal to the set of prime numbers. However, for some values of the variables, the result is negative and can then be composite.

The following function yields all the primes, and only primes, for natural numbers n:

      f(n) = 2+((2(n!+1)-2)  mod (n+1))

Using the floor function (defined to be the largest integer less than or equal to the real number x), one can construct several formulas for the n-th prime. These formulas are based on Wilson's theorem mentioned above and have little practical value: the methods mentioned above under "Finding prime numbers" are much more efficient.

Define

             m    sin(π*(j-1)!/j)
      π(m) = ∑   ------------------- 
            j=2      sin(π/j)

or alternatively

             m
      π(m) = ∑  ]
            j=2

or alternatively

                   m
      π(m) = 1  +  ∑ ( (j-2)! - j )
                  j=3

All these definitions are equivalent, and the n-th prime number p_n can then be written as

              2
      pn = 1 + ∑   ]
              m=1

Another approach does not use factorials and Wilson's theorem, but also heavily employs the floor function: first define

                     k         
     G(k) = k - 1 +  ∑   - ) ) / j ]                 
                    j=2         s=1

and then

               2(+1)
      pn = 1   +     ∑     ( 1 -  ).
                    k=1

The largest known prime

The largest known prime is 2-1 (this number is 4,053,946 digits long). It is a Mersenne prime found by a collaborative effort known as GIMPS on November 14 2001 and announced in early December 2001 after double checking.

The next largest known is 2-1, (this number is 2,098,960 digits long), also a Mersenne prime, found by GIMPS on June 1 1999.

Some of the largest primes not known to have any particular form (that is, no simple formula such as that of Mersenne primes) have been found by taking a piece of semi-random binary data, converting it to a number n, multiplying it by 256 for some positive integer k, and searching for possible primes within the interval . In fact, as a publicity stunt against the Digital Millennium Copyright Act and other WIPO Copyright Treaty implementations, some people have applied this to various forms of DeCSS code, creating the set of illegal prime numbers. Such numbers, when converted to binary and executed as a computer program, perform acts encumbered by applicable law in one or more jurisdictions.

Applications

Extremely large prime numbers (that is, greater than 10) make public key cryptography possible. Primes are also used for hash tables and pseudorandom number generators.

Open Questions

There are many open questions about prime numbers. For example:

• Goldbachs conjecture: Can every positive even integer greater than 2 be written as a sum of two primes?
• Twin Prime Conjecture: A twin prime is a pair of primes with difference 2, e.g. 11 and 13. All pairs of twin primes (other than {3, 5}) are of the form 6n ± 1. The largest known twin primes, found in 2001, are 318032361·2±1. Are there infinitely many twin primes?

Generalizations

The concept of prime number is so important that it has been generalized in different ways in various branches of mathematics. In number theory itself, one talks of pseudoprimes, integers which, by virtue of having passed a certain test, are considered probable primes but are in fact composite (such as Carmichael numbers). To model some of the behavior of prime numbers, one defines prime and irreducible polynomials. More generally, one can define prime and irreducible elements in every integral domain. Prime ideals are an important tool and object of study in commutative algebra and algebraic geometry.

See also

• Chris K. Caldwell: "The prime pages",
• Chris K. Caldwell: "Illegal Prime",
• J. O'Connor and E. F. Robertson: "MacTutor history of prime numbers",