Changes

The largest known prime is ''2^43112609-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>

The largest known prime is ''2^43112609-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>

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 April, 2007, only 44 Mersenne Primes have been found.  The largest known prime ''2^32582657-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 2012, only 47 Mersenne Primes have been found.<ref>http://primes.utm.edu/largest.html#largest</ref> The largest known prime, ''2^43112609-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==

According to the [[Fundamental Theorem of Arithmetic]], proven by [[Carl Friedrich Gauss]], every positive integer has a unique [[factorization]] into prime numbers.

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 primes in only one way. For example, 132 = 2 * 2 * 3 * 11. There is no other product of primes that equals 132.

This means that every integer larger than 1 can be expressed as a product of one or more 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 (having hundreds of digits) can take considerable time (millions of years) even with the most advanced computers.

Finding the prime factors for large numbers (having hundreds of digits) can take considerable time (millions of years) even with the most advanced computers.

==Primality testing==

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

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.