Changes

[[File:Eratosthenes.jpg|thumb|[[Eratosthenes]].]]

[[File:Eratosthenes.jpg|thumb|[[Eratosthenes]].]]

A '''prime number''' is a [[natural number]] greater than 1 that is [[divisible]] by only 1 and itself. Described another way, a prime number has only two [[factor]]s, 1 and itself. The first few prime numbers are 2, 3, 5, 7, 11, 13 .... The opposite of a prime number is a highly [[composite number]].

A '''prime number''' is a [[natural number]] greater than 1 that is [[divisible]] by only 1 and itself. Described another way, a prime number has only two [[factor]]s, 1 and itself. The first few prime numbers are 2, 3, 5, 7, 11, 13 .... The opposite of a prime number is a highly [[composite number]].

 

 

 

[[Leonhard Euler]] wrote: <blockquote>

[[Leonhard Euler]] wrote: <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.''

''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.''

{{main|Prime Number Theorem}}

{{main|Prime Number Theorem}}

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 (by the [[Fundamental Theorem of Arithmetic]]), 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.

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 (by the [[Fundamental Theorem of Arithmetic]]), 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.

Another proof that there are infinitely many primes shows something stronger, namely the sum of the reciprocals of primes less than n "grows like" log(log(n)):

Another proof that there are infinitely many primes shows something stronger, namely the sum of the reciprocals of primes less than n "grows like" log(log(n)):

<math>\sum_{p\le x}p^{-1}\approx\log\log x</math>

<math>\sum_{p\le x}p^{-1}\approx\log\log x</math>

The largest known prime is ''2^57,885,161-1'', a 17,425,169 digit number beginning with 581,887,266,232... and ending with ...951; it was discovered in 2013 by Curtis Cooper with 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>Multiple references:

The largest known prime is ''2^57,885,161-1'', a 17,425,169 digit number beginning with 581,887,266,232... and ending with ...951; it was discovered in 2013 by Curtis Cooper with 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>Multiple references:

* http://primes.utm.edu/largest.html

* http://primes.utm.edu/largest.html

* 2^57,885,161 = 10 ^ (57,885,161 log₁₀ 2).  The number two raised to successively larger powers cause the last three digits to fairly quickly begin repeating themselves in cycles of one hundred, so it is known that the last digits of this Mersenne prime end with ...951.  Written out, the number would be Five hundred eighty-one quinmilliamilliaoctingenoctomilliatrecenoctooctogintillion eight hundred eighty-seven quinmilliamilliaoctingenoctomilliatrecenseptenoctogintillion etc.</ref>

* 2^57,885,161 = 10 ^ (57,885,161 log₁₀ 2).  The number two raised to successively larger powers cause the last three digits to fairly quickly begin repeating themselves in cycles of one hundred, so it is known that the last digits of this Mersenne prime end with ...951.  Written out, the number would be Five hundred eighty-one quinmilliamilliaoctingenoctomilliatrecenoctooctogintillion eight hundred eighty-seven quinmilliamilliaoctingenoctomilliatrecenseptenoctogintillion etc.</ref>

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

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

==Unique factorization==

==Unique factorization==

==Alternative definition==

==Alternative definition==

Beyond the integers, mathematicians are interested in other structures with addition and multiplication; they are called [[Ring_(mathematics)|ring]]s. When working in rings, mathematicians use a different definition for a "prime" element: <blockquote>''A prime element is a non-unit (i.e., not 1 or -1 for the integers) which whenever it divides the product of two numbers will divide at least one of the factors.''</blockquote>

Beyond the integers, mathematicians are interested in other structures with addition and multiplication; they are called [[Ring (mathematics)|ring]]s. When working in rings, mathematicians use a different definition for a "prime" element: <blockquote>''A prime element is a non-unit (i.e., not 1 or -1 for the integers) which whenever it divides the product of two numbers will divide at least one of the factors.''</blockquote>

Or in symbolic notation:

Or in symbolic notation:

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.  

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.

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.

==Open problems about prime numbers==

==Open problems about prime numbers==