Changes

A '''prime number''' is a [[natural number]] greater than 1 which 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 ....  

A '''prime number''' is a [[natural number]] greater than 1 which 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 ....  

As the building-block for all numbers, prime numbers have a [[spiritual]] quality that has fascinated [[mathematicians]] and others.  Prime numbers are a great way to learn and teach [[math]], to improve mental acuity and focus, to fend off [[addiction]], and to understand great works such as the [[Bible]].  The two greatest unsolved mysteries in [[mathematics]] relate to prime numbers: why every even number is the sum of two primes ([[Goldbach's conjecture]]), and apparently there are [[infinity|infinitely]] many [[twin primes]].

As the building block for all numbers, prime numbers have a [[spiritual]] quality that has fascinated [[mathematicians]] and others.  Prime numbers are a great way to learn and teach [[math]], to improve mental acuity and focus, to fend off [[addiction]], and to understand great works such as the [[Bible]].  The two greatest unsolved mysteries in [[mathematics]] relate to prime numbers: why every even number is the sum of two primes ([[Goldbach's conjecture]]), and apparently there are [[infinity|infinitely]] many [[twin primes]].

The [[multiplication of the loaves]] -- the only [[miracle]] described in all four [[Gospels]], and more than once in some Gospels, which suggests it happened more than once -- was always done with a prime number of loaves and fish (5 loaves and 2 fish, totaling 7, for the incidents described in {{bibleref|Mark|6|31-44}}, {{bibleref|Matthew|14|19}}, {{bibleref|Luke|9|13}}, and {{bibleref|John|6|9}}). When another such incident is described later in the [[Gospel of Matthew]], the multiplication occurs with another prime number-worth of loaves:  7.  ''See'' {{bibleref|Matthew|15|34}}.  Many [[biblical parables]] are tantalizing similar to prime numbers, such as [[The Parable of the Weeds]]. Acts 17:17, twice prime, is the midpoint of the [[New Testament]].

The [[multiplication of the loaves]] -- the only [[miracle]] described in all four [[Gospels]], and more than once in some Gospels, which suggests it happened more than once -- was always done with a prime number of loaves and fish (5 loaves and 2 fish, totaling 7, for the incidents described in {{bibleref|Mark|6|31-44}}, {{bibleref|Matthew|14|19}}, {{bibleref|Luke|9|13}}, and {{bibleref|John|6|9}}). When another such incident is described later in the [[Gospel of Matthew]], the multiplication occurs with another prime number-worth of loaves:  7.  ''See'' {{bibleref|Matthew|15|34}}.  Many [[biblical parables]] are tantalizing similar to prime numbers, such as [[The Parable of the Weeds]]. Acts 17:17, twice prime, is the midpoint of the [[New Testament]].

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 causes 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]].

<math>p \in \mathbb{Z}  \quad prime :\Leftrightarrow p \not\in \{-1, 1\} \wedge (\forall a,b \in \mathbb{Z}: p \vert ab \Rightarrow p \vert a \vee p \vert b) </math>

<math>p \in \mathbb{Z}  \quad prime :\Leftrightarrow p \not\in \{-1, 1\} \wedge (\forall a,b \in \mathbb{Z}: p \vert ab \Rightarrow p \vert a \vee p \vert b) </math>

For the integers, this definition is equivalent to the one stated above. However, in general the two definitions are not equivalent. The earlier definition is still important in rings, and is given the name [[irreducibility]], since it literally states that the element cannot be broken into smaller pieces.

For the integers, this definition is equivalent to the one stated above. However, in general the two definitions are not equivalent. The earlier definition is still important in rings and is given the name [[irreducibility]], since it literally states that the element cannot be broken into smaller pieces.

The preference for this alternate definition of "prime" is that this definition gives you unique [[factorization]] theorems analogous to the [[Fundamental Theorem of Arithmetic]]. For more information, consult an abstract algebra book<ref>'''Abstract Algebra: An Introduction''', Thomas Hungerford. Brooks Cole; 2 edition (1996)</ref>

The preference for this alternate definition of "prime" is that this definition gives you unique [[factorization]] theorems analogous to the [[Fundamental Theorem of Arithmetic]]. For more information, consult an abstract algebra book<ref>'''Abstract Algebra: An Introduction''', Thomas Hungerford. Brooks Cole; 2 edition (1996)</ref>

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

{{main|twin primes}}

{{main|twin primes}}

[[Twin primes]] or '''prime twins''' are pairs of prime number which differ from each other by only 2.  Since all primes other than 2 are odd numbers, this is the closest two primes can be to each other, with the exception of 2 and 3.  The first few twin primes are 3 and 5, 5 and 7, 11 and 13, 17 and 19, and 29 and 31.   

[[Twin primes]] or '''prime twins''' are pairs of prime numbers that differ from each other by only 2.  Since all primes other than 2 are odd numbers, this is the closest two primes can be to each other, with the exception of 2 and 3.  The first few twin primes are 3 and 5, 5 and 7, 11 and 13, 17 and 19, and 29 and 31.   

Twin primes become increasingly scarce among larger numbers.  For example, there are twenty-four sets of twin primes between 0 and 500, but only eleven sets between 500 and 1000.  Computer programmes have calculated some extremely large sets of twin primes.  While there are undoubtedly an unlimited number of primes, opinions differ among mathematicians whether there is also an infinite number of twin primes or whether there is an upper limit. This debate is captured by the [[twin primes conjecture]]  

Twin primes become increasingly scarce among larger numbers.  For example, there are twenty-four sets of twin primes between 0 and 500, but only eleven sets between 500 and 1000.  Computer programs have calculated some extremely large sets of twin primes.  While there is undoubtedly an unlimited number of primes, opinions differ among mathematicians on whether there is also an infinite number of twin primes or whether there is an upper limit. This debate is captured by the [[twin primes conjecture]]  

Mathematicians have long been fascinated by twin primes and the relationship between them.  There seems to be no distinct pattern in their occurrence.  For example, there are no twin primes between 700 and 800, or between 900 and 1000, but there are five sets between 800 and 900 (809 and 811; 821 and 823; 827 and 829; 857 and 859; 881 and 883).

Mathematicians have long been fascinated by twin primes and the relationship between them.  There seems to be no distinct pattern in their occurrence.  For example, there are no twin primes between 700 and 800, or between 900 and 1000, but there are five sets between 800 and 900 (809 and 811; 821 and 823; 827 and 829; 857 and 859; 881 and 883).

{{main|Riemann hypothesis}}

{{main|Riemann hypothesis}}

The [[Riemann hypothesis]] is related to patterns 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>

The [[Riemann hypothesis]] is related to patterns in the distribution of prime numbers.  ''The Clay Mathematics Institute'' has offered a one million dollar prize for proof of the Riemann hypothesis.<ref>http://www.claymath.org/millennium/Riemann_Hypothesis/</ref>

==Cryptography==

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

The security of [[public-key cryptography]] schemes such as [[RSA]] depends 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.

== Composite numbers ==

== Composite numbers ==