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
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:
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?.
In August 2001, the largest known prime was 26972593-1, (this number is 2,098,960 digits long). This is a Mersenne prime and was found by a collaborative effort of internet volunteers, who organized themselves in a project called GIMPS.
In December 2001, the number 213466917-1 (this number is 4,053,946 digits long) has been reported to be a Mersenne prime; however the computations are still being checked and no official announcement has been made on the GIMPS pages yet.
Extremely large prime numbers (that is, greater than 10100) 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:
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 ideal]?s are an important tool and object of study in commutative algebra and algebraic geometry.