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
*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

### How many prime numbers are there?

### Finding prime numbers

### The largest known prime

### Some properties

### Applications

### Open Questions

### Generalizations

### See also

/Talk

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

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
^{2}·3·13·149.

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.

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*:

- Write down the numbers 2, 3, 4, ...
*n*. We will eliminate composites by marking them. Initially all numbers are unmarked. - 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. - Mark all multiples of
*m*(2*m*, 3*m*, 4*m*, ...) as composite. - 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 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.

- 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*^{n}is the highest power of the prime*p*which divides the order of*G*, then*G*has a subgroup of order*p*^{n}. (Sylow theorems) - If
*p*is prime and*G*is a group with*p*^{n}elements, then*G*contains an element of order*p* - Adding the reciprocals of all primes together results in a sum of infinity.

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

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)

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.

/Talk