View source for Prime number

A '''prime number''' is a [[natural number]] that is divisible by only 1 and itself.   The only even prime number is 2.  There is no upper limit to the quantity of primes, but there is no known formula for deriving the nth prime.  [[Leonhard Euler]] once commented: <blockquote>
''Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the mind will never penetrate.''
</blockquote>

The probability that a random integer N is prime is roughly 1/ln(N), where ln(N) is the natural logarithm (base ''e'') of N.<ref>http://home.att.net/~numericana/answer/primes.htm</ref>  This is a formulation of a more general statement known as the [[prime number theorem]].

==The Prime Numbers==
The smallest prime numbers are 2, 3, 5, 7, 11, 13...

It is easy to prove that there are an infinite number of primes using Euclid's second theorem:  Imagine there is a finite set consisting of all the primes.  Multiply them all together, add 1, and call this N.  N would not be divisible by any number in the set--there would always be a remainder of 1.  Because all non-prime numbers can be decomposed into a product of underlying primes, N must be divisible by some prime not in the set (possibly itself), thus contradicting the assumption that the set contained all of the primes.

To construct a table of all prime numbers less than ''n'', you would use a method called the [[Sieve of Eratosthenes]].  Simply write down an ordered list of all counting numbers greater than 1.  Beginning with 2*2 = 4, cross out every second number:

:2 3 <s>4</s> 5 <s>6</s> 7 <s>8</s> 9 <s>10</s> 11 ...

then beginning with 3*3 = 9 cross out every third number:

:2 3 <s>4</s> 5 <s>6</s> 7 <s>8 9 10</s> 11 ...

Beginning with 5*5 = 25, cross out every fifth number, then repeat for the primes 7, 11, 13, etc. until <math>\sqrt{n}</math>.

==Unique Factorization==
According to the [[fundamental theorem of arithmetic]], proven by [[Carl Friedrich Gauss]], every positive integer has a unique factorization into prime numbers.

This means that every integer larger than 1, can be expressed as a product of one or more [[prime|primes]] in only one way. For example, 132 = 2 * 2 * 3 * 11. There is no other product of primes that equals 132.

Finding the prime factors for large numbers can take considerable time (millions of years) even with the most advanced computers. This is referred to as the prime factorization problem, and it is believed to be NP-complete.

==Primality testing==
To determine whether a number is prime, you can use the trial division method, provided the number you are testing is not too large.  Let ''N'' be the number being tested and ''s'' be its square root.  Divide ''N'' by each number in the prime table, beginning with 2.  If there is no remainder, stop--N is composite.  Otherwise, test again with the next largest prime in the table.  If the next largest prime is greater than ''s'', stop--''N'' is prime. 

For larger values of ''N'', a method based on Fermat's theorem can be used, though it usually requires a computer.  Start with the number 1, and double it ''N-1'' times.  Divide this number by ''N'', keeping only the remainder.  If the remainder is greater than 1, ''N'' is composite.  Unfortunately, the converse is not true--if the remainder is 1, ''N'' is ''probably'' prime, but not necessarily.  Algorithms which improve on this method exist, and primality testing is today an active subject of mathematical research.

==The Largest Known Prime==

The largest known prime is ''2<sup>32582657</sup>-1''; it was discovered by the '''Great Internet Mersenne Prime Search''' ('''GIMPS''')<ref>http://www.mersenne.org/</ref>, a distributed computing project launched by George Woltman in early 1996.<ref>http://primes.utm.edu/largest.html</ref>

==Mersenne Prime==
A '''Mersenne prime''' is a prime number ''M'' that is of the form ''M =  2<sup>n</sup> − 1'', where ''n'' is some [[prime number]]<ref>[http://mathworld.wolfram.com/MersennePrime.html Mersenne Prime] from Wolfram</ref>.  As of April, 2007, only 44 Mersenne Primes have been found.  The largest known prime ''2<sup>32582657</sup>-1'', is a Mersenne Prime.  The concept of a Mersenne Prime was discovered by the French theologian, philosopher and mathematician [[Marin Mersenne]].

==Riemann hypothesis==
Most mathematicians believe a proof of the [[Riemann hypothesis]] is the best hope for discovering some pattern in the distribution of prime numbers.  ''The Clay Mathematics Institute'' has offered a one million dollar prize for a proof of the Riemann hypothesis.<ref>http://www.claymath.org/millennium/Riemann_Hypothesis/</ref>

==Cryptography==
The security of [[public-key cryptography]] schemes such as [[RSA]] depend on the difficulty of prime factorization, if a pattern in the distribution of prime numbers is discovered, then such cryptographic schemes could become vulnerable to attack.

==References==
<references/>

==See Also==

* [[Composite number]]

==External Links==
:[http://www.mersenne.org/ ''Great Internet Mersenne Prime Search'' project website]
:[http://primes.utm.edu/ Prime Number resource Archieve]
[[Category:Mathematics]]