Namespaces
Variants
Actions

Difference between revisions of "Prime number"

From Encyclopedia of Mathematics
Jump to: navigation, search
(even better)
m (tex encoded by computer)
(One intermediate revision by one other user not shown)
Line 1: Line 1:
A natural number (positive [[Integer|integer]]) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074530/p0745301.png" /> that has only the two divisors 1 and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074530/p0745302.png" />. E.g.,
+
<!--
 +
p0745301.png
 +
$#A+1 = 34 n = 0
 +
$#C+1 = 34 : ~/encyclopedia/old_files/data/P074/P.0704530 Prime number
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074530/p0745303.png" /></td> </tr></table>
+
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
 +
{{MSC|11A41}}
 +
 
 +
A natural number (positive [[Integer|integer]])  $  p > 1 $
 +
that has only the two divisors 1 and  $  p $.
 +
E.g.,
 +
 
 +
$$
 +
2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , .  . . .
 +
$$
  
 
Natural numbers which are not prime are called ''composite''. The concept of a prime number is fundamental in the study of divisibility of natural numbers. Thus, the fundamental theorem of elementary number theory states that every natural number, different from one, is either prime or, if it is composite, can be represented by a product of prime numbers. This representation is, moreover, unique (up to the order of the factors). A description of this decomposition in the form of powers of identical prime numbers and in increasing order is given by the canonical decomposition of a natural number:
 
Natural numbers which are not prime are called ''composite''. The concept of a prime number is fundamental in the study of divisibility of natural numbers. Thus, the fundamental theorem of elementary number theory states that every natural number, different from one, is either prime or, if it is composite, can be represented by a product of prime numbers. This representation is, moreover, unique (up to the order of the factors). A description of this decomposition in the form of powers of identical prime numbers and in increasing order is given by the canonical decomposition of a natural number:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074530/p0745304.png" /></td> </tr></table>
+
$$
 +
= p _ {1} ^ {\alpha _ {1} } \dots p _ {k} ^ {\alpha _ {k} } .
 +
$$
 +
 
 +
By using the canonical decompositions of natural numbers  $  a _ {1} \dots a _ {k} $
 +
one can find their [[Greatest common divisor|greatest common divisor]]  $  d = ( a _ {1} \dots a _ {k} ) $
 +
and [[Least common multiple|least common multiple]]  $  m = [ a _ {1} \dots a _ {k} ] $.
 +
By means of the canonical decomposition of a natural number  $  n $
 +
one can compute the values of the number-theoretic functions  $  \tau ( n) $,
 +
$  S ( n) $
 +
and  $  \phi ( n) $,
 +
which denote, respectively, the number of divisors of  $  n $,
 +
the sum of the divisors of  $  n $
 +
and the amount of natural numbers  $  m \leq  n $
 +
that are coprime with  $  n $(
 +
i.e. are such that  $  ( m , n ) = 1 $):
  
By using the canonical decompositions of natural numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074530/p0745305.png" /> one can find their [[Greatest common divisor|greatest common divisor]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074530/p0745306.png" /> and [[Least common multiple|least common multiple]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074530/p0745307.png" />. By means of the canonical decomposition of a natural number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074530/p0745308.png" /> one can compute the values of the number-theoretic functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074530/p0745309.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074530/p07453010.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074530/p07453011.png" />, which denote, respectively, the number of divisors of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074530/p07453012.png" />, the sum of the divisors of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074530/p07453013.png" /> and the amount of natural numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074530/p07453014.png" /> that are coprime with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074530/p07453015.png" /> (i.e. are such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074530/p07453016.png" />):
+
$$
 +
\tau ( n)  = ( \alpha _ {1} + 1 ) \dots ( \alpha _ {k} + 1 ) ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074530/p07453017.png" /></td> </tr></table>
+
$$
 +
S ( n)  =
 +
\frac{p _ {1} ^ {\alpha _ {1} + 1 } - 1 }{p _ {1} - 1 }
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074530/p07453018.png" /></td> </tr></table>
+
\dots
 +
\frac{p _ {k} ^ {\alpha _ {k} + 1 } - 1 }{p _ {k} - 1 }
 +
,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074530/p07453019.png" /></td> </tr></table>
+
$$
 +
\phi ( n)  = n \left ( 1 -
 +
\frac{1}{p _ {1} }
 +
\right
 +
) \dots \left ( 1 -  
 +
\frac{1}{p _ {k} }
 +
\right ) .
 +
$$
  
An essential feature of these formulas is their dependence on the arithmetical structure of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074530/p07453020.png" />.
+
An essential feature of these formulas is their dependence on the arithmetical structure of $  n $.
  
The prime numbers play the role of  "construction blocks"  from which one can construct all other natural numbers. Already in the 3rd century B.C., Euclid proved that the set of prime numbers is infinite, and Eratosthenes found a way of sifting the prime numbers out of the sequence of natural numbers (cf. [[Eratosthenes, sieve of|Eratosthenes, sieve of]]). L. Euler found a proof of the infinity of the set of prime numbers based on the use of tools of mathematical analysis. The further development of Euler's analytic method proved to be fruitful (cf. [[Analytic number theory|Analytic number theory]]). P.L. Chebyshev discovered new laws to which prime numbers are subject. In particular, using the canonical decomposition of the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074530/p07453021.png" /> he found an inequality for the amount <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074530/p07453022.png" /> of prime numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074530/p07453023.png" />:
+
The prime numbers play the role of  "construction blocks"  from which one can construct all other natural numbers. Already in the 3rd century B.C., Euclid proved that the set of prime numbers is infinite, and Eratosthenes found a way of sifting the prime numbers out of the sequence of natural numbers (cf. [[Eratosthenes, sieve of|Eratosthenes, sieve of]]). L. Euler found a proof of the infinity of the set of prime numbers based on the use of tools of mathematical analysis. The further development of Euler's analytic method proved to be fruitful (cf. [[Analytic number theory|Analytic number theory]]). P.L. Chebyshev discovered new laws to which prime numbers are subject. In particular, using the canonical decomposition of the number $  n ! $
 +
he found an inequality for the amount $  \pi ( x) $
 +
of prime numbers p \leq  x $:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074530/p07453024.png" /></td> </tr></table>
+
$$
 +
a
 +
\frac{x}{ \mathop{\rm ln}  x }
 +
  < \pi ( x)  < b
 +
\frac{x}{ \mathop{\rm ln}  x }
 +
,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074530/p07453025.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074530/p07453026.png" />, are certain positive constants. The most refined laws to which the behaviour of the sequence of prime numbers is subject were obtained by refining the original ideas of Chebyshev and by using analytic and, in a number of cases, elementary methods (cf. [[Distribution of prime numbers|Distribution of prime numbers]]).
+
where $  a , b $,
 +
$  a < 1 < b $,  
 +
are certain positive constants. The most refined laws to which the behaviour of the sequence of prime numbers is subject were obtained by refining the original ideas of Chebyshev and by using analytic and, in a number of cases, elementary methods (cf. [[Distribution of prime numbers|Distribution of prime numbers]]).
  
Prime numbers are related not only to the multiplicative structure but also to the additive structure of natural numbers. Goldbach's problem on the partitioning of a natural number into a sum of three prime numbers is characteristic in this respect (cf. [[Goldbach problem|Goldbach problem]]). It was solved in 1937 by I.M. Vinogradov (cf. [[Additive number theory|Additive number theory]]). The study of laws of decomposing prime numbers in algebraic fields shed light on properties of ordinary prime numbers. E.g., by considering the decompositions of prime numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074530/p07453027.png" /> in the Gaussian number field (cf. [[Gauss number|Gauss number]]) one obtains Euler's theorem: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074530/p07453028.png" /> if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074530/p07453029.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074530/p07453030.png" />).
+
Prime numbers are related not only to the multiplicative structure but also to the additive structure of natural numbers. Goldbach's problem on the partitioning of a natural number into a sum of three prime numbers is characteristic in this respect (cf. [[Goldbach problem|Goldbach problem]]). It was solved in 1937 by I.M. Vinogradov (cf. [[Additive number theory|Additive number theory]]). The study of laws of decomposing prime numbers in algebraic fields shed light on properties of ordinary prime numbers. E.g., by considering the decompositions of prime numbers p \neq 2 $
 +
in the Gaussian number field (cf. [[Gauss number|Gauss number]]) one obtains Euler's theorem: $  p = a  ^ {2} + b  ^ {2} $
 +
if and only if p \equiv 1 $(
 +
$  \mathop{\rm mod}  4 $).
  
 
Up till now (1990) there are a number of unsolved problems related to prime numbers. E.g.,
 
Up till now (1990) there are a number of unsolved problems related to prime numbers. E.g.,
Line 29: Line 89:
 
Is the set of Mersenne prime numbers
 
Is the set of Mersenne prime numbers
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074530/p07453031.png" /></td> </tr></table>
+
$$
 +
= 2  ^ {q} - 1 ,\  \textrm{ where }  q  \textrm{ is  a  "prime" number  } ,
 +
$$
  
 
infinite?
 
infinite?
Line 35: Line 97:
 
Is the set of Fermat prime numbers
 
Is the set of Fermat prime numbers
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074530/p07453032.png" /></td> </tr></table>
+
$$
 +
= 2 ^ {2  ^ {n} } + 1,\  \textrm{ where }  n\geq  0 \textrm{ is  an  integer  } ,
 +
$$
  
 
infinite?
 
infinite?
  
Does there exist an infinite set of prime  "twins"  <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074530/p07453033.png" />, i.e. prime numbers such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074530/p07453034.png" />?
+
Does there exist an infinite set of prime  "twins"   $ p _ {1} , p _ {2} $,  
 +
i.e. prime numbers such that $  p _ {1} - p _ {2} = 2 $?
  
 
Experimental and heuristic considerations favour positive answers to the questions stated above, as well as to a number of similar questions.
 
Experimental and heuristic considerations favour positive answers to the questions stated above, as well as to a number of similar questions.
Line 45: Line 110:
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  H. Hasse,  "Vorlesungen über Zahlentheorie" , Springer  (1950)</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  H. Hasse,  "Vorlesungen über Zahlentheorie" , Springer  (1950)</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====

Revision as of 08:07, 6 June 2020


2020 Mathematics Subject Classification: Primary: 11A41 [MSN][ZBL]

A natural number (positive integer) $ p > 1 $ that has only the two divisors 1 and $ p $. E.g.,

$$ 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , . . . . $$

Natural numbers which are not prime are called composite. The concept of a prime number is fundamental in the study of divisibility of natural numbers. Thus, the fundamental theorem of elementary number theory states that every natural number, different from one, is either prime or, if it is composite, can be represented by a product of prime numbers. This representation is, moreover, unique (up to the order of the factors). A description of this decomposition in the form of powers of identical prime numbers and in increasing order is given by the canonical decomposition of a natural number:

$$ n = p _ {1} ^ {\alpha _ {1} } \dots p _ {k} ^ {\alpha _ {k} } . $$

By using the canonical decompositions of natural numbers $ a _ {1} \dots a _ {k} $ one can find their greatest common divisor $ d = ( a _ {1} \dots a _ {k} ) $ and least common multiple $ m = [ a _ {1} \dots a _ {k} ] $. By means of the canonical decomposition of a natural number $ n $ one can compute the values of the number-theoretic functions $ \tau ( n) $, $ S ( n) $ and $ \phi ( n) $, which denote, respectively, the number of divisors of $ n $, the sum of the divisors of $ n $ and the amount of natural numbers $ m \leq n $ that are coprime with $ n $( i.e. are such that $ ( m , n ) = 1 $):

$$ \tau ( n) = ( \alpha _ {1} + 1 ) \dots ( \alpha _ {k} + 1 ) , $$

$$ S ( n) = \frac{p _ {1} ^ {\alpha _ {1} + 1 } - 1 }{p _ {1} - 1 } \dots \frac{p _ {k} ^ {\alpha _ {k} + 1 } - 1 }{p _ {k} - 1 } , $$

$$ \phi ( n) = n \left ( 1 - \frac{1}{p _ {1} } \right ) \dots \left ( 1 - \frac{1}{p _ {k} } \right ) . $$

An essential feature of these formulas is their dependence on the arithmetical structure of $ n $.

The prime numbers play the role of "construction blocks" from which one can construct all other natural numbers. Already in the 3rd century B.C., Euclid proved that the set of prime numbers is infinite, and Eratosthenes found a way of sifting the prime numbers out of the sequence of natural numbers (cf. Eratosthenes, sieve of). L. Euler found a proof of the infinity of the set of prime numbers based on the use of tools of mathematical analysis. The further development of Euler's analytic method proved to be fruitful (cf. Analytic number theory). P.L. Chebyshev discovered new laws to which prime numbers are subject. In particular, using the canonical decomposition of the number $ n ! $ he found an inequality for the amount $ \pi ( x) $ of prime numbers $ p \leq x $:

$$ a \frac{x}{ \mathop{\rm ln} x } < \pi ( x) < b \frac{x}{ \mathop{\rm ln} x } , $$

where $ a , b $, $ a < 1 < b $, are certain positive constants. The most refined laws to which the behaviour of the sequence of prime numbers is subject were obtained by refining the original ideas of Chebyshev and by using analytic and, in a number of cases, elementary methods (cf. Distribution of prime numbers).

Prime numbers are related not only to the multiplicative structure but also to the additive structure of natural numbers. Goldbach's problem on the partitioning of a natural number into a sum of three prime numbers is characteristic in this respect (cf. Goldbach problem). It was solved in 1937 by I.M. Vinogradov (cf. Additive number theory). The study of laws of decomposing prime numbers in algebraic fields shed light on properties of ordinary prime numbers. E.g., by considering the decompositions of prime numbers $ p \neq 2 $ in the Gaussian number field (cf. Gauss number) one obtains Euler's theorem: $ p = a ^ {2} + b ^ {2} $ if and only if $ p \equiv 1 $( $ \mathop{\rm mod} 4 $).

Up till now (1990) there are a number of unsolved problems related to prime numbers. E.g.,

Is the set of Mersenne prime numbers

$$ p = 2 ^ {q} - 1 ,\ \textrm{ where } q \textrm{ is a "prime" number } , $$

infinite?

Is the set of Fermat prime numbers

$$ p = 2 ^ {2 ^ {n} } + 1,\ \textrm{ where } n\geq 0 \textrm{ is an integer } , $$

infinite?

Does there exist an infinite set of prime "twins" $ p _ {1} , p _ {2} $, i.e. prime numbers such that $ p _ {1} - p _ {2} = 2 $?

Experimental and heuristic considerations favour positive answers to the questions stated above, as well as to a number of similar questions.

References

[1] H. Hasse, "Vorlesungen über Zahlentheorie" , Springer (1950)

Comments

For prime number problems in algebraic number fields see also Algebraic number theory; Kummer theorem.

In [a1], written for both experts and non-experts, the reader can find a great many open problems, results and records in the theory of prime numbers. Also, in this book and in [a2] one finds the description of a number of algorithms to test primality of numbers and, if composite, to factor them. Algorithms of this kind which can handle numbers of 100 or 200 digits have recently attracted a large amount of attention in connection with cryptography.

References

[a1] P. Ribenboim, "The book of prime number records" , Springer (1988)
[a2] H. Riesel, "Prime numbers and computer methods for factorisation" , Birkhäuser (1985)
[a3] G.H. Hardy, E.M. Wright, "An introduction to the theory of numbers" , Oxford Univ. Press (1979) pp. Chapts. 5; 7; 8
[a4] D.M. Bressoud, "Factorization and primality testing" , Springer (1989)
How to Cite This Entry:
Prime number. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Prime_number&oldid=30267
This article was adapted from an original article by B.M. Bredikhin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article