Prime number/Citable Version: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Catherine Woodgold
(Moving "definition" and "unique factorization" sections, which will appeal to more advanced readers, to later in the article.)
imported>John Stephenson
m (moved Prime number to Prime number/Citable Version: citable version policy)
 
(39 intermediate revisions by 9 users not shown)
Line 1: Line 1:
[[Image:Prime rectangles.png|thumb|300px|The prime number 11 illustrated with square tiles: 12 squares can be arranged into a rectangle with sides of length 3 and 4, so 12 is not a prime number. There is no way to form a full rectangle more than one square wide with 11 squares, so 11 is a prime number.]]
{{subpages}}
[[Image:Prime rectangles.png|thumb|300px|'''The prime number 11 illustrated with square tiles.''' 12 squares can be arranged into a rectangle with sides of length 3 and 4, so 12 is not a prime number. There is no way to form a full rectangle more than one square wide with 11 squares, so 11 is a prime number.]]


A '''prime number''' is a number that cannot be evenly [[divisor|divided]] by any numbers but 1 and itself. The first few prime numbers are 2, 3, 5, 7, 11, 13, and 17. With the exception of <math>2</math>, all prime numbers are [[odd]] numbers, but not every odd number is prime. For example, <math>9 = 3\cdot3</math> and <math>15 = 3\cdot5</math>, so neither 9 nor 15 is prime.  By the strict mathematical definition, the number 1 is not considered to be prime:  a prime number is a positive [[integer]] greater than 1 that is (evenly) divisible only by itself and 1.  
A '''prime number''' is a number that can be evenly divided by exactly two positive [[integer|whole numbers]], namely 1 and itself. The first few prime numbers are 2, 3, 5, 7, 11, 13, and 17. A prime number <math>p</math> cannot be factored as the [[multiplication|product]] of two numbers <math>\scriptstyle p=a\times b,</math> except for the trivial factorizations <math>\scriptstyle p = 1\times p = p\times 1</math> that all numbers possess.


The study of prime numbers has a long history, going back to ancient times, and it remains an active part of [[number theory]] (a branch of [[mathematics]]) today. It is commonly believed that the study of prime numbers is an interesting, but not terribly useful, area of mathematical research.  While this used to be the case, the theory of prime numbers has important applications now. Understanding properties of prime numbers and their generalizations is essential to modern [[cryptography]], and to [[public key cipher]]s that are crucial to Internet commerce, wireless networks and, of course, military applications. Less well known is that other computer algorithms also depend on properties of prime numbers.  
With the exception of 2, all prime numbers are odd numbers, but not every odd number is prime. For example, <math>\scriptstyle 9 = 3\times 3</math> and <math>\scriptstyle 15 = 3\times 5,</math> so neither 9 nor 15 is prime. By the strict mathematical definition, the number 1 is not considered to be prime (although this is a matter of definition, and mathematicians in the past often did consider 1 to be a prime).
 
The importance of prime numbers in arithmetic comes in large part from the [[unique factorization]] of numbers.
Every number <math>\scriptstyle N > 1</math> can be written as a product of prime factors, and any two such expressions for <math>N</math> will differ only in the order of the factors. For example, we can write <math>\scriptstyle 5040 = 7 \times 5 \times 3 \times 3 \times 2 \times 2 \times 2 \times 2</math>, where all of the factors in the product are prime numbers; there is no other way of writing 5040 as a product of prime numbers except by rearranging the prime factors we already have, such as <math>\scriptstyle 5040 = 2 \times 3 \times 2 \times 7 \times 2 \times 3 \times 2 \times 5</math>. Because of the unique factorization of numbers into prime numbers, an analogy can be made between the role prime numbers play in arithmetic and the role atoms play in chemistry.
 
The study of prime numbers has a long history, going back to ancient times, and it remains an active part of [[number theory]] today. Although the study of prime numbers used to be an interesting but not terribly useful area of mathematical research, today it has important applications. Understanding properties of prime numbers and their generalizations is essential to modern [[cryptography]]&mdash;in particular to [[public key cipher]]s that are crucial to Internet commerce, wireless networks, and military applications. Less well-known is that other computer algorithms also depend on properties of prime numbers.


==There are infinitely many primes==
==There are infinitely many primes==


One basic fact about the prime numbers is that there are infinitely many of them. In other words, the list of prime numbers 2, 3, 5, 7, 11, 13, 17, ... doesn't ever stop. There are a number of ways of showing that this is so, but one of the oldest and most familiar proofs goes back go [[Euclid]]. Another one, due to [[Leonhard Euler]], is described in another section of the article.
One basic fact about the prime numbers is that there are infinitely many of them. In other words, the list of prime numbers 2, 3, 5, 7, 11, 13, 17, ... never stops. There are a number of ways of showing that there are infinitely many primes, but one of the oldest and most familiar proofs goes back go [[Euclid]].


Euclid's proof is a [[proof by contradiction]]. Suppose the set of prime numbers is finite, say <math>\{ p_1, p_2, p_3, \ldots, p_n \}</math>, and let
Euclid proved that for any finite set of prime numbers, there is always another prime number which is not in that set. Choose any finite set of prime numbers <math>\scriptstyle \{ p_1, p_2, p_3, \ldots, p_n \}</math>. Then the number


:<math>N = p_1 p_2 \cdots p_n +1</math>
:<math>N = p_1 p_2 \cdots p_n +1</math>


then for each <math>i \in 1, \ldots, n</math> we know that <math>p_i</math> does not divide <math>N</math>, because the remainder is 1. This means that ''N'' is not divisible by any prime, which is impossible. This contradiction shows that our assumption that there must only be a finite number of primes must have been wrong and thus proves the theorem.
presents a problem. On the one hand, the number <math>\scriptstyle N-1 = p_1 p_2 \cdots p_n</math> is a multiple of <math>p_1</math>, and multiples of the same prime number are never next to each other, so ''N'' itself can't be a multiple of <math>\scriptstyle p_1</math>. The same argument actually shows that <math>N</math> itself cannot be a multiple of any of the prime numbers  <math>\scriptstyle p_1, p_2, p_3, \dots, p_n</math>. On the other hand, every number <math>\scriptstyle N>1</math> is divisible by ''some'' prime. (For example, its smallest divisor greater than 1 must be a prime.<ref>The number ''N'' has at least one divisor greater than 1, because ''N'' is a divisor of itself.  Let ''q'' denote the smallest divisor of ''N'' greater than 1. To see why ''q'' must be prime: Any divisor of ''q'' is also a divisor of ''N'', and since ''q'' is the smallest, then ''q'' has no divisors smaller than itself except 1, therefore it is prime.</ref>)
 
This shows that there is at least one prime number (namely, the smallest divisor of ''N'' greater than 1) that is excluded from our initial finite set.  Since any finite set of prime numbers can thus be extended to a larger finite set of prime numbers, we conclude that there are infinitely many prime numbers.
 
Although most other proofs of the infinitude of prime numbers are more complicated, they can also provide more information. One mathematical milestone known as the [[Prime Number Theorem]] estimates how many of the numbers between 1 and ''x'' are prime numbers (see [[Prime number#Distribution of prime numbers|below]]).  Another such proof is [[Leonhard Euler|Euler's]] demonstration that the sum of the reciprocals of the primes diverges to &infin;.


==Locating primes==
==Locating primes==


How can we tell which numbers are prime and which are not? It is sometimes possible to tell that a number is ''not'' prime from looking at its digits: for example, any number larger than 2 whose last digit is even is divisble by 2 and hence not prime, and any number ending with 5 or 0 is divisible by 5. Therefore, any prime number larger than 5 must end with 1, 3, 7 or 9. This check can be used to rule out the possibility of a randomly chosen number being prime roughly half of the time, but a number that ends with 1, 3, 7 or 9 could have a divisor that is harder to spot.
How can we tell which numbers are prime and which are not? It is sometimes possible to tell that a number is ''not'' prime by looking at its digits: for example, any number whose last digit is even is divisble by 2, and any number ending with 5 or 0 is divisible by 5. Therefore, except for the prime numbers 2 and 5, any prime number must end with the digit 1, 3, 7, or 9. This check can be used to rule out the possibility of a randomly chosen number being prime more than half of the time, but numbers that end with 1, 3, 7, or 9 often have divisors that are harder to spot.


To find large prime numbers, we must use a systematic procedure &mdash; an ''[[algorithm]]''. Nowadays, prime-finding calculations are performed by computers, often using very complicated algorithms, but there are simple algorithms that can be carried out by hand if the numbers are small. In fact, the simplest methods for locating prime numbers are some of the oldest algorithms, known since antiquity. Two classical algorithms are called ''trial division'' and the ''sieve of Eratosthenes''.
To find large prime numbers, we must use a systematic procedure &mdash; an ''[[algorithm]]''. Nowadays, prime-finding calculations are performed by computers, often using very complicated algorithms, but there are simple algorithms that can be carried out by hand if the numbers are small. In fact, the simplest methods for locating prime numbers are some of the oldest algorithms, known since antiquity. Two classical algorithms are called ''trial division'' and the ''sieve of Eratosthenes''.
Line 23: Line 33:
===Trial division===
===Trial division===


''[[Trial division]]'' consists of systematically searching the list of numbers 2, 3, ..., <math>n-1</math> for a divisor; if none is found, the number is prime. If ''n'' has a small divisor, we can quit as soon as we've found it, but in the worst case &mdash; if ''n'' is prime &mdash; we have to test all <math>n-2</math> numbers to be sure. This algorithm can be improved by realizing the following: if ''n'' has a divisor ''a'' that is larger than <math>\sqrt n</math>, there must be another divisor ''b'' that is ''smaller'' than <math>\sqrt n</math>. Thus, it is sufficient to look for a divisor up to <math>\sqrt n</math>. This makes a significant difference: for example, we only need to try dividing by 2, 3, ..., 31 to verify that 997 is prime, rather than all the numbers 2, 3, ..., 996. Trial division might be described as follows using [[pseudocode]]:
''[[Trial division]]'' consists of systematically searching the list of numbers <math>\scriptstyle 2, 3, \dots, n-1</math> for a divisor; if none is found, the number is prime. If ''n'' has a small divisor, we can quit as soon as we've found it, but in the worst case &mdash; if ''n'' is prime &mdash; we have to test all <math>\scriptstyle n-2</math> numbers to be sure. This algorithm can be improved by realizing the following: if ''n'' has a divisor ''a'' that is larger than <math>\scriptstyle\sqrt n</math>, there must be another divisor ''b'' that is ''smaller'' than <math>\scriptstyle \sqrt n</math>. Thus, it is sufficient to look for a divisor up to <math>\scriptstyle \sqrt n</math>. This makes a significant difference: for example, we only need to try dividing by 2, 3, ..., 31 to verify that 997 is prime, rather than all the numbers 2, 3, ..., 996. Trial division might be described as follows using [[pseudocode]]:


'''Algorithm: trial division'''
'''Algorithm: trial division'''


:Given ''n'',
:Given <math>n</math>,
:For each ''i'' = 2, 3, ... less than or equal to <math>\sqrt{n}</math>:
:For each <math>i</math> = 2, 3, ... less than or equal to <math>\scriptstyle \sqrt{n}</math>:
::If ''i'' divides ''n'':
::If <math>i</math> divides <math>n</math>:
:::Return "''n'' is not prime"
:::Return "<math>n</math> is not prime"
::Else:
::Else:
:::Continue with the next ''i''
:::Continue with the next <math>i</math>
:When all ''i'' have been checked:
:When all <math>i</math> have been checked:
::Return "''n'' is prime"
::Return "<math>n</math> is prime"


===Sieve of Eratosthenes===
===Sieve of Eratosthenes===


The Sieve of Eratosthenes not only provides a method for ''testing'' a number to see if it is prime, but also for ''enumerating'' the (infinite) set of prime numbers. The idea of the method to write down a list of numbers starting from 2 ranging up to some limit, say
The Sieve of [[Eratosthenes]] not only provides a method for ''testing'' a number to see if it is prime, but also for ''enumerating'' the (infinite) set of prime numbers. The idea of the method to write down a list of numbers starting from 2 ranging up to some limit, say:


:2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
:2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20


The first number (2) is prime, so we mark it, and cross out all of its multiples
The first number (2) is prime, so we mark it, and cross out all of its multiples:


:'''2''', 3, <s>4</s>, 5, <s>6</s>, 7, <s>8</s>, 9, <s>10</s>, 11, <s>12</s>, 13, <s>14</s>, 15, <s>16</s>, 17, <s>18</s>, 19, <s>20</s>
:'''2''', 3, <s>4</s>, 5, <s>6</s>, 7, <s>8</s>, 9, <s>10</s>, 11, <s>12</s>, 13, <s>14</s>, 15, <s>16</s>, 17, <s>18</s>, 19, <s>20</s>


The smallest unmarked number is 3, so we mark it and cross out all its multiples (some of which may already have been crossed out)
The smallest unmarked number is 3, so we mark it and cross out all its multiples (some of which may already have been crossed out):


:'''2''', '''3''', <s>4</s>, 5, <s>6</s>, 7, <s>8</s>, <s>9</s>, <s>10</s>, 11, <s>12</s>, 13, <s>14</s>, <s>15</s>, <s>16</s>, 17, <s>18</s>, 19, <s>20</s>
:'''2''', '''3''', <s>4</s>, 5, <s>6</s>, 7, <s>8</s>, <s>9</s>, <s>10</s>, 11, <s>12</s>, 13, <s>14</s>, <s>15</s>, <s>16</s>, 17, <s>18</s>, 19, <s>20</s>


The smallest unmarked number (5) is the next prime, so we mark it and cross out all of its multiples
The smallest unmarked number (5) is the next prime, so we mark it and cross out all of its multiples:


:'''2''', '''3''', <s>4</s>, '''5''', <s>6</s>, 7, <s>8</s>, <s>9</s>, <s>10</s>, 11, <s>12</s>, 13, <s>14</s>, <s>15</s>, <s>16</s>, 17, <s>18</s>, 19, <s>20</s>
:'''2''', '''3''', <s>4</s>, '''5''', <s>6</s>, 7, <s>8</s>, <s>9</s>, <s>10</s>, 11, <s>12</s>, 13, <s>14</s>, <s>15</s>, <s>16</s>, 17, <s>18</s>, 19, <s>20</s>


Notice that there are no multiples of 5 <math>(\le 20)</math> that haven't already been crossed out, but that doesn't matter at this stage. Proceeding as before, we add 7, 11, 13, 17 and 19 to our list of primes
Notice that there are no multiples of 5 <math>\scriptstyle (\le 20)</math> that have not already been crossed out, but that doesn't matter at this stage. Proceeding as before, we add 7, 11, 13, 17 and 19 to our list of primes:


:'''2''', '''3''', <s>4</s>, '''5''', <s>6</s>, '''7''', <s>8</s>, <s>9</s>, <s>10</s>, '''11''', <s>12</s>, '''13''', <s>14</s>, <s>15</s>, <s>16</s>, '''17''', <s>18</s>, '''19''', <s>20</s>
:'''2''', '''3''', <s>4</s>, '''5''', <s>6</s>, '''7''', <s>8</s>, <s>9</s>, <s>10</s>, '''11''', <s>12</s>, '''13''', <s>14</s>, <s>15</s>, <s>16</s>, '''17''', <s>18</s>, '''19''', <s>20</s>
Line 60: Line 70:
We have now found all prime numbers up to 20.
We have now found all prime numbers up to 20.


==Definition==
==Distribution of prime numbers==


A prime numbers is a positive [[integer]] other than 1 that is (evenly) [[divisor|divisible]] only by 1 and itself.
''It is evident that the prime numbers are randomly distributed but, unfortunately, we don't know what 'random' means.'' - R. C. Vaughan


There is another way of defining prime numbers, and that is that a number is prime if whenever it divides the product of two numbers, it must divide one of those numbers. A nonexample (if you will) is that 4 divides 12 (i.e. is a factor of 12), but 4 does not divide 2 and 4 does not divide 6 even though 12 is 2 times 6. This means that 4 is ''not'' a prime number. We may express this second possible definition in  [[mathematical notation]] as follows: A number <math>p \in \mathbb{N}</math> ([[natural number]]) is prime if for any <math>a, b \in \mathbb{N}</math> such that <math>p | ab</math> (read ''p'' divides ''ab''), either <math>p | a</math> or <math>p | b</math>.  
The list of prime numbers suggests that they thin out the further you go: 44% of the one-digit numbers are prime, but only 23% of the two-digit numbers and 16% of the three-digit numbers. The trial division method explained above provides an intuitive explanation. To test whether a number <math>n</math> is prime, you have to try whether it can be divided by all numbers between 2 and <math>\scriptstyle\sqrt n</math>. Large numbers have to undergo more tests, so fewer of them will be prime.


If the first characterization of prime numbers is taken as the [[definition]], the second is derived from it as a [[theorem]], and ''vice versa''. The equivalence of these two definitions (in the [[integer]]s <math>\mathbb{Z}</math>) is not immediately obvious. In fact, it is a significant result.<ref>The [[Euclidean algorithm]] may be used to show that <math>\mathbb{Z}</math> is a [[principal ideal domain]], and this implies that irreducibles are prime.</ref>
The [[Prime Number Theorem]] explains how fast the prime numbers thin out. It says that if you are looking around the number <math>n</math>, about one in every <math>\scriptstyle\log\, n</math> numbers is prime (here, <math>\scriptstyle\log\, n</math> denotes the [[natural logarithm]] of <math>n</math>). The formal statement of the prime number theorem is


==Unique factorization==
:<math>\lim_{x\to\infty} \frac{\pi(x) \log x}{x} = 1</math>
 
Every integer ''N'' > 1 can be written in a unique way as a product of prime factors, up to reordering. to see why this is true, assume that ''N'' can be written as a product of prime factors in two ways
 
:<math>N = p_1 p_2 \cdots p_m = q_1 q_2 \cdots q_n</math>
 
We may now use a technique known as [[mathematical induction]] to show that the two prime decompositions are really the ''same''.
 
Consider the prime factor <math>p_1</math>. We know that
 
:<math>p_1 \mid q_1 q_2 \cdots q_n.</math>
 
Using the second definition of prime numbers, it follows that <math>p_1</math> divides one of the ''q''-factors, say <math>q_i</math>. Using the first definition, <math>p_1</math> is in fact equal to <math>q_i</math>
 
Now, if we set <math>N_1 = N/p_1</math>, we may write
 
:<math>N_1 = p_2 p_3 \cdots p_m</math>


and
where <math>\pi(x)</math> is the number of primes <math>\scriptstyle \le x.</math>
 
:<math>N_1 = q_1 q_2 \cdots q_{i-1} q_{i+1} \cdots q_n</math>
 
In other words, <math>N_1</math> is the product of all the <math>q</math>'s except <math>q_i</math>.
 
Continuing this way, we obtain a sequence of numbers <math>N = N_0 > N_1 > N_2 > \cdots > N_n = 1</math> where each <math>N_{\alpha}</math> is obtained by dividing <math>N_{\alpha - 1}</math> by a prime factor. In particular, we see that <math>m = n</math> and that there is some permutation ("rearrangement") &sigma; of the indices <math>1, 2, \ldots n</math> such that <math>p_i = q_{\sigma(i)}</math>. Said differently, the two factorizations of ''N'' must be the same up to a possible rearrangement of terms.


==Some unsolved problems==
==Some unsolved problems==
There are many unsolved problems concerning prime numbers. Two such problems (posed as conjectures) are:
There are many unsolved problems concerning prime numbers. A few such problems (posed as conjectures) are:


===The twin prime conjecture===
===The twin prime conjecture===
'''Twin primes''' are pairs of prime numbers differing by 2. Examples of twin primes include 5 and 7, 11 and 13, and 41 and 43. The Twin Prime Conjecture states that there are an infinite number of these pairs. It remains unproven.
'''Twin primes''' are pairs of prime numbers differing by 2. Examples of twin primes include 5 and 7, 11 and 13, and 41 and 43. The ''Twin Prime Conjecture'' states that there are an infinite number of these pairs. It remains unproven.


===The Goldbach conjecture===
===The Goldbach conjecture===
The '''Goldbach conjecture''' is that every [[even]] number  greater than 2 can be expressed as the sum of two primes.  For example, if you choose the even number 48, you can find <math>48 = 41 + 7</math> where 41 and 7 are prime numbers.
The '''Goldbach conjecture''' is that every [[even]] number  greater than 2 can be expressed as the sum of two primes.  For example, if you choose the even number 48, you can find <math>48 = 41 + 7</math> where 41 and 7 are prime numbers.


==Distribution of prime numbers==
===Primes of special forms===
*It is not known whether there are infinitely many primes of the form <math>2^n - 1</math> (called Mersenne primes). These primes arise in the study of [[perfect number]]s, and factors of numbers of the form <math>2^n - 1</math> (sometimes called 'Mersenne numbers') are a fruitful source of large prime numbers.
*It is not known whether there are infinitely many primes of the form <math>2^n + 1</math> (called 'Fermat primes'). Fermat primes arise in elementary geometry because if <math>p</math> is a Fermat prime, it is possible to construct a regular <math>p</math>-gon with a ruler and compass. In particular, it is possible to construct a regular 17-sided polygon (or 17-gon, for short) with  a ruler and compass.
*It is not known whether there are infinitely many primes of the form <math>n^2 + 1</math>.


==Alternative definition==


''It is evident that the prime numbers are randomly distributed but, unfortunately, we don't know what 'random' means.'' - R. C. Vaughan
A prime number is usually defined as a positive [[integer]] other than 1 that is (evenly) [[divisor|divisible]] only by 1 and itself.


There is another way of defining prime numbers, and that is that a number is prime if whenever it divides the product of two numbers, it must divide one of those numbers. A nonexample (if you will) is that 4 divides 12 (i.e. is a factor of 12), but 4 does not divide 2 and 4 does not divide 6 even though 12 is 2 times 6. This means that 4 is ''not'' a prime number. We may express this second possible definition in  [[mathematical notation]] as follows: A number <math>\scriptstyle p \in \mathbb{N}</math> ([[natural number]]) is prime if for any <math>\scriptstyle a, b \in \mathbb{N}</math> such that <math>\scriptstyle p | ab</math> (read ''p'' divides ''ab''), either <math>p | a</math> or <math>p | b</math>.


 
If the first characterization of prime numbers is taken as the [[definition]], the second is derived from it as a [[theorem]] (known as [[Euclid's lemma]]), and ''vice versa''. The equivalence of these two definitions (in the [[integer]]s <math>\scriptstyle \mathbb{Z}</math>) is not immediately obvious. In fact, it is a significant result.<ref>The [[Euclidean algorithm]] may be used to show that <math>\scriptstyle\mathbb{Z}</math> is a [[principal ideal domain]], and this implies that irreducibles are prime.</ref>
The list of prime numbers suggests that they thin out the further you go: 44% of the one-digit numbers are prime, but only 23% of the two-digit numbers and 16% of the three-digit numbers. The trial division method explained above provides an intuitive explanation. To test whether a number ''n'' is prime, you have to try whether it can be divided by all numbers between 2 and &radic;''n''. Large numbers have to undergo more tests, so fewer of them will be prime.
 
The [[prime number theorem]] explains how fast the prime numbers thin out. It says that if you are looking around the number ''n'', about one in every log ''n'' numbers is prime (here, log ''n'' denotes the [[natural logarithm]] of ''n''). The formal statement of the prime number theorem is
 
:<math>\lim_{x\to\infty} \frac{\pi(x) \log x}{x} = 1</math>
 
where <math>\pi(x)</math> is the number of primes <math>\le x</math>. This result was demonstrated independently by [[Jacques Hadamard]] and [[Charles de la Vallée Poussin]] in 1896. An essential part of their proof is the function
 
:<math>\zeta(s) = \sum_{n = 1}^{\infty} \frac{1}{n^s}. </math>
 
This function was already considered by the 18th century Swiss mathematician [[Leonhard Euler]], who realized that
 
:<math> \sum_{n = 1}^{\infty} \frac{1}{n^s} = \prod_{p \in \mathbb{P}} \frac{1}{1 - p^{-s}}, </math>
 
where the product on the right goes over all prime numbers:
 
:<math> \prod_{p \in \mathbb{P}} \frac{1}{1 - p^{-s}} = \frac{1}{1-2^{-s}} \, \frac{1}{1-3^{-s}} \, \frac{1}{1-5^{-s}} \, \frac{1}{1-7^{-s}} \cdots </math>
 
To see why this is so, we use the formula for the sum of a [[geometric series]] to write the product as
 
:<math> \left( 1 + \frac1{2^s} + \frac1{2^{2s}} + \frac1{2^{3s}} + \cdots \right) \left( 1 + \frac1{3^s} + \frac1{3^{2s}} + \frac1{3^{3s}} + \cdots \right) \left( 1 + \frac1{5^s} + \frac1{5^{2s}} + \frac1{5^{3s}} + \cdots \right) \cdots </math>
 
Multiplying out this product, we get a sum of terms of the form
 
:<math> \frac{1}{(p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k})^s}, </math>
 
where <math>p_1</math>, &hellip; <math>p_k</math> are prime numbers and <math>a_1</math>, &hellip; <math>a_k</math> are positive integers. Euler's formula equating the sum and the product now follows from the fact that every number has a unique prime factorization. This also indicates the connection between the function &zeta; and the prime numbers.
 
Euler used his formula to give an alternative proof that there are infinitely many primes. If we take <math>s=1</math>, we get
 
:<math> \sum_{n = 1}^{\infty} \frac{1}{n} = \prod_{p \in \mathbb{P}} \frac{1}{1 - \frac1p}. </math>
 
The sum on the left is the [[harmonic series]], which diverges. If the number of primes were finite, then the product would evaluate to a finite number. This contradiction shows that there are infinitely many primes.
 
The above definition for the function &zeta; only works when ''s'' > 1, because the infinite sum diverges otherwise, but a technique called [[analytic continuation]] can be used to extend the definition to all values of ''s'', including [[complex number]]s. The function with the extended domain is known as the [[Riemann zeta function]]. Hadamard and de la Vallée Poussin proved that this function cannot be zero in certain parts of the complex plane and used this to establish the prime number theorem. A proof not relying on [[complex analysis]] proved elusive, even though weaker results on the distribution of prime numbers have long been known<ref>Ribenboim, ''Introduction to Analytic Number theory''</ref><ref>Scharlau and Opolka, ''From Fermat to Minkowski''</ref>. It was only in 1949 that [[Atle Selberg]] and [[Paul Erdös]] were able to establish the theorem by elementary means.
 
The location of the values ''s'' for which &zeta;(''s'') is zero, is one of the biggest mysteries in contemporary mathematics. The [[Riemann hypothesis]] states all the zeros of the Riemann zeta function lie on two lines in the complex plane. A proof of the Riemann hypothesis would lead immediately to more precise estimates on how fast the function &pi;(''n'') grows.


==References and notes==
==References and notes==
Line 180: Line 136:
(Note that Scharlau and Opolka was originally published as: {{cite book |last = Scharlau|first = Winfried|coauthors = Hans Opolka|title = Von Fermat bis Minkowski: Eine Vorlesung über Zahlentheorie und ihre Entwicklung|publisher = Springer-Verlag|date = 1980 }}).
(Note that Scharlau and Opolka was originally published as: {{cite book |last = Scharlau|first = Winfried|coauthors = Hans Opolka|title = Von Fermat bis Minkowski: Eine Vorlesung über Zahlentheorie und ihre Entwicklung|publisher = Springer-Verlag|date = 1980 }}).


 
<!--
 
 
[[Category:Mathematics Workgroup]]
[[Category:Mathematics Workgroup]]
[[category:CZ Live]]
[[category:CZ Live]]-->

Latest revision as of 11:20, 13 September 2013

This article has a Citable Version.
 Main Article
 Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
https://en.citizendium.org/wiki/index.php?title=Prime_number/Citable_Version&printable=yes
This version approved either by the Approvals Committee, or an Editor from the listed workgroup. The Mathematics Workgroup is responsible for this citable version. While we have done conscientious work, we cannot guarantee that this version is wholly free of mistakes. See here (not History) for authorship.
Help improve this work further on the editable Main Article!
The prime number 11 illustrated with square tiles. 12 squares can be arranged into a rectangle with sides of length 3 and 4, so 12 is not a prime number. There is no way to form a full rectangle more than one square wide with 11 squares, so 11 is a prime number.

A prime number is a number that can be evenly divided by exactly two positive whole numbers, namely 1 and itself. The first few prime numbers are 2, 3, 5, 7, 11, 13, and 17. A prime number Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} cannot be factored as the product of two numbers Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle p=a\times b,} except for the trivial factorizations Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle p = 1\times p = p\times 1} that all numbers possess.

With the exception of 2, all prime numbers are odd numbers, but not every odd number is prime. For example, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle 9 = 3\times 3} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle 15 = 3\times 5,} so neither 9 nor 15 is prime. By the strict mathematical definition, the number 1 is not considered to be prime (although this is a matter of definition, and mathematicians in the past often did consider 1 to be a prime).

The importance of prime numbers in arithmetic comes in large part from the unique factorization of numbers. Every number Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle N > 1} can be written as a product of prime factors, and any two such expressions for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} will differ only in the order of the factors. For example, we can write Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle 5040 = 7 \times 5 \times 3 \times 3 \times 2 \times 2 \times 2 \times 2} , where all of the factors in the product are prime numbers; there is no other way of writing 5040 as a product of prime numbers except by rearranging the prime factors we already have, such as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle 5040 = 2 \times 3 \times 2 \times 7 \times 2 \times 3 \times 2 \times 5} . Because of the unique factorization of numbers into prime numbers, an analogy can be made between the role prime numbers play in arithmetic and the role atoms play in chemistry.

The study of prime numbers has a long history, going back to ancient times, and it remains an active part of number theory today. Although the study of prime numbers used to be an interesting but not terribly useful area of mathematical research, today it has important applications. Understanding properties of prime numbers and their generalizations is essential to modern cryptography—in particular to public key ciphers that are crucial to Internet commerce, wireless networks, and military applications. Less well-known is that other computer algorithms also depend on properties of prime numbers.

There are infinitely many primes

One basic fact about the prime numbers is that there are infinitely many of them. In other words, the list of prime numbers 2, 3, 5, 7, 11, 13, 17, ... never stops. There are a number of ways of showing that there are infinitely many primes, but one of the oldest and most familiar proofs goes back go Euclid.

Euclid proved that for any finite set of prime numbers, there is always another prime number which is not in that set. Choose any finite set of prime numbers Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle \{ p_1, p_2, p_3, \ldots, p_n \}} . Then the number

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N = p_1 p_2 \cdots p_n +1}

presents a problem. On the one hand, the number Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle N-1 = p_1 p_2 \cdots p_n} is a multiple of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_1} , and multiples of the same prime number are never next to each other, so N itself can't be a multiple of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle p_1} . The same argument actually shows that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} itself cannot be a multiple of any of the prime numbers Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle p_1, p_2, p_3, \dots, p_n} . On the other hand, every number Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle N>1} is divisible by some prime. (For example, its smallest divisor greater than 1 must be a prime.[1])

This shows that there is at least one prime number (namely, the smallest divisor of N greater than 1) that is excluded from our initial finite set. Since any finite set of prime numbers can thus be extended to a larger finite set of prime numbers, we conclude that there are infinitely many prime numbers.

Although most other proofs of the infinitude of prime numbers are more complicated, they can also provide more information. One mathematical milestone known as the Prime Number Theorem estimates how many of the numbers between 1 and x are prime numbers (see below). Another such proof is Euler's demonstration that the sum of the reciprocals of the primes diverges to ∞.

Locating primes

How can we tell which numbers are prime and which are not? It is sometimes possible to tell that a number is not prime by looking at its digits: for example, any number whose last digit is even is divisble by 2, and any number ending with 5 or 0 is divisible by 5. Therefore, except for the prime numbers 2 and 5, any prime number must end with the digit 1, 3, 7, or 9. This check can be used to rule out the possibility of a randomly chosen number being prime more than half of the time, but numbers that end with 1, 3, 7, or 9 often have divisors that are harder to spot.

To find large prime numbers, we must use a systematic procedure — an algorithm. Nowadays, prime-finding calculations are performed by computers, often using very complicated algorithms, but there are simple algorithms that can be carried out by hand if the numbers are small. In fact, the simplest methods for locating prime numbers are some of the oldest algorithms, known since antiquity. Two classical algorithms are called trial division and the sieve of Eratosthenes.

Trial division

Trial division consists of systematically searching the list of numbers Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle 2, 3, \dots, n-1} for a divisor; if none is found, the number is prime. If n has a small divisor, we can quit as soon as we've found it, but in the worst case — if n is prime — we have to test all Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle n-2} numbers to be sure. This algorithm can be improved by realizing the following: if n has a divisor a that is larger than Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle\sqrt n} , there must be another divisor b that is smaller than Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle \sqrt n} . Thus, it is sufficient to look for a divisor up to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle \sqrt n} . This makes a significant difference: for example, we only need to try dividing by 2, 3, ..., 31 to verify that 997 is prime, rather than all the numbers 2, 3, ..., 996. Trial division might be described as follows using pseudocode:

Algorithm: trial division

Given Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} ,
For each Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} = 2, 3, ... less than or equal to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle \sqrt{n}} :
If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} divides Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} :
Return "Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} is not prime"
Else:
Continue with the next Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i}
When all Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} have been checked:
Return "Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} is prime"

Sieve of Eratosthenes

The Sieve of Eratosthenes not only provides a method for testing a number to see if it is prime, but also for enumerating the (infinite) set of prime numbers. The idea of the method to write down a list of numbers starting from 2 ranging up to some limit, say:

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

The first number (2) is prime, so we mark it, and cross out all of its multiples:

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

The smallest unmarked number is 3, so we mark it and cross out all its multiples (some of which may already have been crossed out):

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

The smallest unmarked number (5) is the next prime, so we mark it and cross out all of its multiples:

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

Notice that there are no multiples of 5 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle (\le 20)} that have not already been crossed out, but that doesn't matter at this stage. Proceeding as before, we add 7, 11, 13, 17 and 19 to our list of primes:

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

We have now found all prime numbers up to 20.

Distribution of prime numbers

It is evident that the prime numbers are randomly distributed but, unfortunately, we don't know what 'random' means. - R. C. Vaughan

The list of prime numbers suggests that they thin out the further you go: 44% of the one-digit numbers are prime, but only 23% of the two-digit numbers and 16% of the three-digit numbers. The trial division method explained above provides an intuitive explanation. To test whether a number Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} is prime, you have to try whether it can be divided by all numbers between 2 and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle\sqrt n} . Large numbers have to undergo more tests, so fewer of them will be prime.

The Prime Number Theorem explains how fast the prime numbers thin out. It says that if you are looking around the number Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} , about one in every Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle\log\, n} numbers is prime (here, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle\log\, n} denotes the natural logarithm of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} ). The formal statement of the prime number theorem is

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lim_{x\to\infty} \frac{\pi(x) \log x}{x} = 1}

where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \pi(x)} is the number of primes Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle \le x.}

Some unsolved problems

There are many unsolved problems concerning prime numbers. A few such problems (posed as conjectures) are:

The twin prime conjecture

Twin primes are pairs of prime numbers differing by 2. Examples of twin primes include 5 and 7, 11 and 13, and 41 and 43. The Twin Prime Conjecture states that there are an infinite number of these pairs. It remains unproven.

The Goldbach conjecture

The Goldbach conjecture is that every even number greater than 2 can be expressed as the sum of two primes. For example, if you choose the even number 48, you can find Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 48 = 41 + 7} where 41 and 7 are prime numbers.

Primes of special forms

  • It is not known whether there are infinitely many primes of the form Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^n - 1} (called Mersenne primes). These primes arise in the study of perfect numbers, and factors of numbers of the form Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^n - 1} (sometimes called 'Mersenne numbers') are a fruitful source of large prime numbers.
  • It is not known whether there are infinitely many primes of the form Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^n + 1} (called 'Fermat primes'). Fermat primes arise in elementary geometry because if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} is a Fermat prime, it is possible to construct a regular Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} -gon with a ruler and compass. In particular, it is possible to construct a regular 17-sided polygon (or 17-gon, for short) with a ruler and compass.
  • It is not known whether there are infinitely many primes of the form Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^2 + 1} .

Alternative definition

A prime number is usually defined as a positive integer other than 1 that is (evenly) divisible only by 1 and itself.

There is another way of defining prime numbers, and that is that a number is prime if whenever it divides the product of two numbers, it must divide one of those numbers. A nonexample (if you will) is that 4 divides 12 (i.e. is a factor of 12), but 4 does not divide 2 and 4 does not divide 6 even though 12 is 2 times 6. This means that 4 is not a prime number. We may express this second possible definition in mathematical notation as follows: A number Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle p \in \mathbb{N}} (natural number) is prime if for any Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle a, b \in \mathbb{N}} such that (read p divides ab), either or .

If the first characterization of prime numbers is taken as the definition, the second is derived from it as a theorem (known as Euclid's lemma), and vice versa. The equivalence of these two definitions (in the integers ) is not immediately obvious. In fact, it is a significant result.[2]

References and notes

  1. ↑ The number N has at least one divisor greater than 1, because N is a divisor of itself. Let q denote the smallest divisor of N greater than 1. To see why q must be prime: Any divisor of q is also a divisor of N, and since q is the smallest, then q has no divisors smaller than itself except 1, therefore it is prime.
  2. ↑ The Euclidean algorithm may be used to show that is a principal ideal domain, and this implies that irreducibles are prime.

Further reading

  • Apostol, Tom M. (1976). Introduction to Analytic Number Theory. Springer-Verlag. ISBN 0-387-90163-9. 
  • Ribenboim, Paulo (2004). The Little Book of Bigger Primes, second edition. Springer-Verlag. ISBN 0-387-20169-6. 
  • Scharlau, Winfried; Hans Opolka (1985). From Fermat to Minkowski: Lectures on the Theory of Numbers and its Historical Development. Springer-Verlag. ISBN 0-387-90942-7. 

(Note that Scharlau and Opolka was originally published as: Scharlau, Winfried; Hans Opolka (1980). Von Fermat bis Minkowski: Eine Vorlesung über Zahlentheorie und ihre Entwicklung. Springer-Verlag. ).


Retrieved from "https://citizendium.org/wiki/index.php?title=Prime_number/Citable_Version&oldid=22908"