Prime number

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)