Prime number

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

2, 3, 5, 7, 11, 13, 17, 19, 23, 29

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.

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.

For a random large number (say, up to a few thousand digits), you can test for primality with Fermats little theorem or the [Miller-Rabin test]?. [Tests for primality]? would make an article in itself and would also bring in the notion of pseudoprimes? and witnesses?.

The largest known prime

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

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

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^p - 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
• Adding the reciprocals of all primes together results in a sum of infinity.

Applications

Extremely large prime numbers (that is, greater than 10¹⁰⁰) make public key cryptography possible. Primes are also used for hash tables and [pseudo random number generator]?s.

Open Questions

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

• Can every positive even integer greater than 2 be written as a sum of two primes? (see Goldbachs conjecture)
• A twin prime is a pair of primes with difference 2, e.g. 11 and 13. Are there infinitely many twin primes? (see Twin Prime Conjecture)

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 pseudoprime?s, integers which, by virtue of having passed a certain test, are considered probable primes but are in fact composite. 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

• [The prime pages]
• [MacTutor history of prime numbers]

---

/Talk