Difference between revisions of "Prime number"

From Conservapedia
Jump to: navigation, search
m (grammar, links)
m (How many prime numbers: ditto)
(44 intermediate revisions by 18 users not shown)
Line 1: Line 1:
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>
+
[[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]].
 +
<br><br>
 +
[[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.''
 
</blockquote>
 
</blockquote>
  
The number of primes smaller than a given number <math>N</math> is roughly <math>\frac{N}{\ln(N)}</math>, where <math>\ln(N)</math> is the [[natural logarithm]] (base ''[[e]]'') of <math>N</math>.<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]].
+
There are infinitely many primes. The only [[even]] prime number is 2. The [[Bible]] includes many references to prime numbers.   
  
==The Prime Numbers==
+
==Sieve of Eratosthenes==
The smallest prime numbers are 2, 3, 5, 7, 11, 13...
+
{|class="wikitable" align="right"
 +
|{{User:ClementB/SieveOfEratosthenes}}
 +
|-
 +
|Here, '''n''' equals 144
 +
|}
 +
To construct a table of all prime numbers less than ''n'', you can use a method called the [[Sieve of Eratosthenes]]. Simply write down an ordered list of all counting numbers from 1 to ''n''. Beginning with 2*2 = 4, cross out every second number:
  
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.
+
: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>.
 +
 
 +
The number of primes smaller than a given number <math>N</math> is roughly <math>\frac{N}{\ln(N)}</math>, where <math>\ln(N)</math> is the [[natural logarithm]] (base ''[[e]]'') of <math>N</math>.<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]].
 +
 
 +
==How many prime numbers==
 +
{{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.
  
 
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<sup>57,885,161</sup>-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
 +
* 2<sup>57,885,161</sup> = 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.</ref>
  
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 1Beginning with 2*2 = 4, cross out every second number:
+
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 2015, only 48 Mersenne Primes have been found.<ref>http://primes.utm.edu/largest.html#largest</ref> The largest known prime, ''2<sup>57885161</sup>-1'', is a Mersenne Prime.  The concept of a Mersenne Prime was discovered by the French theologian, philosopher and mathematician [[Marin Mersenne]].
  
:2 3 <s>4</s> 5 <s>6</s> 7 <s>8</s> 9 <s>10</s> 11 ...
+
==Unique Factorization==
 +
{{main|Fundamental Theorem of Arithmetic}}
  
then beginning with 3*3 = 9 cross out every third number:
+
According to the [[Fundamental Theorem of Arithmetic]], proven by [[Carl Friedrich Gauss]], every positive integer has a unique [[factorization]] into prime numbers.
  
:2 3 <s>4</s> 5 <s>6</s> 7 <s>8 9 10</s> 11 ...
+
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.
  
Beginning with 5*5 = 25, cross out every fifth number, then repeat for the primes 7, 11, 13, etc. until <math>\sqrt{n}</math>.
+
Finding the prime factors for large numbers (having hundreds of digits) can take considerable time (millions of years) even with the most advanced computers.
  
 
==Alternative Definition==
 
==Alternative Definition==
Mathematicians often prefer the following definition, which, for integers, is equivalent to the one stated above: <blockquote>''A prime number 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:
Line 31: Line 56:
 
<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>
  
The advantage of this formulation is that it can be generalized on other structures which allow for addition and multiplication, i.e., [[ring]]s. The earlier definition involves the notion of [[irreducibility]].
+
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.
  
==Unique Factorization==
+
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>
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.
+
 
+
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==
 
==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.
  
==The Largest Known Prime==
+
==Open Problems about Prime Numbers==
  
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==
+
===Twin primes===
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]].
+
{{main|twin primes}}
  
==Riemann hypothesis==
+
[[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.
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>
+
  
==Goldbach's 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 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]]
  
Goldbach's conjecture asserts that every even [[integer]] greater than two is the sum of two [[prime]] numbers.  For example: 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, and so on.
+
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).
 +
 
 +
===Goldbach's conjecture===
 +
 
 +
Goldbach's conjecture asserts that every even integer greater than two is the sum of two prime numbers.  For example: 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, and so on.
  
 
This conjecture is one of the oldest unsettled statements in mathematics.  For centuries mathematicians have attempted to prove this statement, without success.  The conjecture is known to hold for numbers less than 3 <math>\cdot</math>10<sup>17</sup>.
 
This conjecture is one of the oldest unsettled statements in mathematics.  For centuries mathematicians have attempted to prove this statement, without success.  The conjecture is known to hold for numbers less than 3 <math>\cdot</math>10<sup>17</sup>.
 +
 +
===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>
  
 
==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]] 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.
 +
 
 +
==See also==
 +
 
 +
* [[Composite number]]
 +
* [[Fibonacci sequence]]
 +
* [[Perfect number]]
 +
 
 +
==External links==
 +
*[http://www.mersenne.org/ ''Great Internet Mersenne Prime Search'' project website]
 +
*[http://primes.utm.edu/ Prime Number resource Archive]
 +
*[http://educ.queensu.ca/%7Efmc/december2003/Sieve.html Sieve of Eratosthenes]
  
 
==References==
 
==References==
 
<references/>
 
<references/>
  
==See Also==
 
 
* [[Composite number]]
 
  
==External Links==
+
[[Category:Number Theory]]
:[http://www.mersenne.org/ ''Great Internet Mersenne Prime Search'' project website]
+
[[Category:Featured articles]]
:[http://primes.utm.edu/ Prime Number resource Archieve]
+
[[Category:Mathematics]]
+

Revision as of 19:56, December 6, 2015

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 factors, 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:

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.

There are infinitely many primes. The only even prime number is 2. The Bible includes many references to prime numbers.

Sieve of Eratosthenes

User:ClementB/SieveOfEratosthenes
Here, n equals 144

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

2 3 4 5 6 7 8 9 10 11 ...

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

2 3 4 5 6 7 8 9 10 11 ...

Beginning with 5*5 = 25, cross out every fifth number, then repeat for the primes 7, 11, 13, etc. until .

The number of primes smaller than a given number is roughly , where is the natural logarithm (base e) of .[1] This is a formulation of a more general statement known as the Prime Number Theorem.

How many prime numbers

For a more detailed treatment, see 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.

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)):

The largest known prime is 257,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)[2], a distributed computing project launched by George Woltman in early 1996.[3]

A Mersenne prime is a prime number M that is of the form M = 2n − 1, where n is some prime number[4]. As of 2015, only 48 Mersenne Primes have been found.[5] The largest known prime, 257885161-1, is a Mersenne Prime. The concept of a Mersenne Prime was discovered by the French theologian, philosopher and mathematician Marin Mersenne.

Unique Factorization

For a more detailed treatment, see Fundamental Theorem of Arithmetic.

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.

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

Alternative Definition

Beyond the integers, mathematicians are interested in other structures with addition and multiplication; they are called rings. When working in rings, mathematicians use a different definition for a "prime" element:
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.

Or in symbolic notation:

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[6]

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.

Open Problems about Prime Numbers

Twin primes

For a more detailed treatment, see 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 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

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

Goldbach's conjecture

Goldbach's conjecture asserts that every even integer greater than two is the sum of two prime numbers. For example: 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, and so on.

This conjecture is one of the oldest unsettled statements in mathematics. For centuries mathematicians have attempted to prove this statement, without success. The conjecture is known to hold for numbers less than 3 1017.

Riemann hypothesis

For a more detailed treatment, see 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.[7]

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.

See also

External links

References

  1. http://home.att.net/~numericana/answer/primes.htm
  2. http://www.mersenne.org/
  3. Multiple references:
    • http://primes.utm.edu/largest.html
    • 257,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.
  4. Mersenne Prime from Wolfram
  5. http://primes.utm.edu/largest.html#largest
  6. Abstract Algebra: An Introduction, Thomas Hungerford. Brooks Cole; 2 edition (1996)
  7. http://www.claymath.org/millennium/Riemann_Hypothesis/