Prime number

from Wikipedia, the free encyclopedia

A prime number is a natural number that is greater than 1 and only divisible by itself and by 1 . The word “prime number” is derived from the Latin numerus primus 'first number' , where primus specifically means 'beginning, the first (of things)', so that a 'starting number' is meant that is not constructed from any other (preceding) number can.

The set of prime numbers is usually denoted by the symbol . With linked is the result of the ordered by size primes that are also prime consequence calls. It is accordingly

With

(Follow A000040 in OEIS ).
The number 12 is not a prime number, but the number 11 is.
Prime number sequence in the divider area

The importance of the prime numbers for many areas of mathematics is based on three consequences from their definition:

  • Existence and uniqueness of the prime factorization : Every natural number that is greater than 1 and is not itself a prime number can be written as the product of at least two prime numbers. This product representation is clear except for the order of the factors. That serves as proof
  • Euclid's lemma : If a product of two natural numbers is divisible by a prime number, then at least one of the factors is divisible by them.
  • Prime numbers cannot be represented as the product of two natural numbers that are both greater than 1.

These properties are used in algebra for generalizations of the concept of prime numbers .

A number that is the product of two or more prime factors is called composite . The number 1 is neither prime nor composite, which is related to its invertibility . All other natural numbers are one of the two, either prime (i.e. prime number) or composite.

Even in ancient Greece there was an interest in the prime numbers and some of their properties were discovered. Although primes have always been very appealing to people since then, many questions relating to prime numbers remain unanswered , including those that are more than a hundred years old and easy to understand. These include Goldbach's conjecture , according to which every even number except 2 can be represented as the sum of two prime numbers, and the conjecture that there are an infinite number of prime twins (these are pairs of prime numbers whose difference is 2).

Prime numbers and their properties play a major role in cryptography because prime factors cannot really be found efficiently, even with the advent of electronic calculating machines. On the other hand, these machines enable efficient encryption and, if you know the key, decryption of even long texts.

Prime factorization

The fundamental theorem of arithmetic applies : Every positive integer can be represented as a product of prime numbers, and this representation is unique except for the order of the prime numbers. These prime numbers are called the prime factors of the number. The one is shown as an empty product .

Because every natural number greater than zero can be clearly represented by multiplying prime numbers, the prime numbers occupy a special atomic position in mathematics, they “generate” all other natural numbers, so to speak. Alexander K. Dewdney described them as largely similar to the elements of chemistry .

This also makes it clear why it is inexpedient to define one as a prime number: It is the neutral element of multiplication and can therefore not generate any further numbers multiplicatively. It is not required for the representation of the numbers as the product of prime factors. If one were to count 1 among the prime numbers, the uniqueness of the prime factorization would also be lost, because any number of ones can be appended to each division without changing the value of the number.

A number of factorization methods have been developed to determine the prime factors of general numbers or those of special form as quickly as possible. So far, however, no method is known to efficiently factor any number, i.e. H. in a time that grows at most polynomially with the length of the given number. The factoring assumption states that such a method does not exist either.

Properties of prime numbers

The prime numbers are within the set of natural numbers, thereby characterized , that each of them natural exactly two numbers as a splitter has.

With the exception of the number 2, all prime numbers are odd, because all larger even numbers can be divided by 2 (at least) in addition to themselves and 1. So every prime number except 2 has the form with a natural number .

Each prime number can be assigned to one of the two classes “prime number of form ” or “prime number of form ”, where is a natural number. In addition, every prime number has the form or , where is a natural number. According to Dirichlet's prime number theorem, there are infinitely many prime numbers in each of these four classes.

Every natural number of the form with a nonnegative integer contains at least one prime factor of the form . A corresponding statement about numbers of the form or prime factors of the form is not possible.

A prime number can be written in the form with whole numbers if and only if the form has. In this case the representation is essentially clear; H. except for the order and sign of . This representation corresponds to the prime factorization

in the ring of whole Gaussian numbers .

The number −1 is a quadratic remainder modulo any prime number of the form and a quadratic non- remainder modulo any prime number of the form .

Fermat's Little Theorem

Let it be a prime number. For every whole number that is not divisible by , the following applies (for the notation see congruence ):

For numbers that are not divisible by numbers , the following formulation is equivalent:

There are numbers that are not prime, but still behave like prime numbers on a base ; h., it is . Such are called Fermat's pseudoprimes for the base . One that is Fermat's pseudoprime with respect to all bases coprime to it is called a Carmichael number .

In this context, the problem of Fermat's pseudoprimes becomes apparent: they are mistaken for prime numbers by a primality test that uses Fermat's small theorem ( Fermat's primality test ). However, if an encryption method such as RSA uses a composite number instead of a prime number, the encryption is no longer secure. Therefore, better primality tests must be used in such procedures.

Euler and the Legendre symbol

A simple consequence of Fermat's Little Theorem is the following statement: For every odd prime number and every integer that is not divisible by , either

or

One can show that the first case occurs if and only if there is a square number that is congruent to modulo  , see Legendre symbol .

Binomial coefficient

For prime numbers and applies

together with the binomial sentence it follows

For whole numbers , this statement also follows directly from Fermat's Little Theorem, but it can also be used, for example, for polynomials with whole-number coefficients; in the general context it corresponds to the fact that the mapping in rings of the characteristic is a homomorphism, the so-called Frobenius homomorphism .  

From Wilson's theorem ( is a prime number if and only if is) it follows that for every prime number and every natural number there is congruence

is satisfied.

Charles Babbage proved in 1819 that for every prime number this congruence holds:

The mathematician Joseph Wolstenholme (1829–1891) then proved in 1862 that the following congruence applies to every prime number :

Giuga

From Fermat's Little Theorem it follows that for a prime number :

Example :

Giuseppe Giuga hypothesized that the reverse direction also applies, i.e. that a number with this property is always prime. It is not clear whether this assumption is correct. It is known, however, that a counterexample would have to have more than 10,000 decimal places. In connection with Giuga's conjecture , the Giuga numbers are examined.

Linear recursions

The little Fermat's sentence can also be read in the following form: In the following , the -th term for a prime number is always divisible by. Other sequences of exponential character have similar properties, such as the Lucas sequence ( ) and the Perrin sequence ( ). Analog apply to other linear recursion, but more complex statements, such as the Fibonacci sequence : If a prime number, then by divisible; is there

the Legendre symbol .

Divergence of the sum of the reciprocal values

The series of reciprocal values ​​of the prime numbers is divergent. Thus:

.

This is equivalent to the statement that the sequence defined by does not have a finite limit value, which in turn means that any imaginable real number can be exceeded for a sufficiently large selected . This is initially astonishing, since the prime number gaps keep increasing on average. The set of Mertens makes a statement about the exact growth behavior of these divergent series.

Prime number tests

A prime number test can be used to find out whether any natural number is prime. There are several such methods that rely on special properties of prime numbers. In practice, the Miller-Rabin test is most often used, which has an extremely short duration, but has a low probability of delivering false-positive results. With the AKS primality test it is possible to decide on the primality without the risk of an error in polynomial running time. However, in practice it is significantly slower than the Miller-Rabin test.

Prime number certificate

Finding out whether a natural number is prime or not can be a hassle. For each prime number, however, a chain of assertions can be made, all of which are immediately understandable, together prove the primality and whose total length is at most proportional to the square of the length of the prime number. Such a document is Certificate (Engl. Primality certificate ) called.

In the case of the composite nature (non-primality) of a number, the difference between receipt and finding a receipt is even more obvious: Two factors are sufficient as evidence, the product of which results in the composite number; Finding a real divisor can take a lot of effort.

Largest known prime

In the fourth century BC, the Greek Euclid logically concluded that there are an infinite number of prime numbers; this statement is called Euclid's theorem. Euclid provided a contradictory proof for the correctness of this theorem ( Elements, Book IX, § 20): Based on the assumption that there are only finitely many prime numbers, another number can be constructed that has a previously unknown prime number as a divisor or itself is a prime number, which contradicts the assumption. Thus a finite set can never contain all prime numbers, so there are infinitely many. Today we know a whole series of proofs for Euclid's theorem.

Euclid's theorem states that there is no greatest prime. However, there is no known method that efficiently generates arbitrarily large prime numbers - that is why there has always been one largest known prime number since people started dealing with prime numbers. Currently (as of December 2018) it is a number with 24,862,048 (decimal) digits, which was calculated on December 7, 2018. The discoverer Patrick Laroche received $ 3,000 from the Great Internet Mersenne Prime Search project , which searches for Mersenne prime numbers using distributed computing .

The largest known prime number was almost always a Mersenne prime number, i.e. of the form that the Lucas-Lehmer test can be used in this special case , a very quick prime number test compared to the general situation. When searching for large prime numbers, only numbers of this or a similarly suitable type are therefore examined for primality.

List of record prime numbers by years

number Number of
decimal digits
year Explorer (computer used)
2 17 −1 6th 1588 Cataldi
2 19 −1 6th 1588 Cataldi
2 31 −1 10 1772 Euler
(2 59 −1) / 179951 13 1867 Landry
2 127 −1 39 1876 Lucas
(2 148 +1) / 17 44 1951 Ferrier
180 · (2 127 −1) 2 +1 79 1951 Miller & Wheeler (EDSAC1)
2 521 −1 157 1952 Robinson ( SWAC )
2 607 −1 183 1952 Robinson (SWAC)
2 1,279 −1 386 1952 Robinson (SWAC)
2 2,203 −1 664 1952 Robinson (SWAC)
2 2,281 −1 687 1952 Robinson (SWAC)
2 3,217 −1 969 1957 Riesel (BESK)
2 4,423 −1 1,332 1961 Hurwitz (IBM7090)
2 9,689 −1 2,917 1963 Gillies (ILLIAC 2)
2 9,941 −1 2,993 1963 Gillies (ILLIAC 2)
2 11,213 −1 3,376 1963 Gillies (ILLIAC 2)
2 19,937 −1 6.002 1971 Tuckerman (IBM360 / 91)
2 21,701 −1 6,533 1978 Noll & Nickel (CDC Cyber ​​174)
2 23,209 −1 6,987 1979 Noll (CDC Cyber ​​174)
2 44,497 −1 13,395 1979 Nelson & Slowinski (Cray 1)
2 86,243 −1 25,962 1982 Slowinski (Cray 1)
2 132,049 −1 39,751 1983 Slowinski (Cray X-MP)
2 216.091 −1 65,050 1985 Slowinski (Cray X-MP / 24)
391581 · 2 216,193 −1 65,087 1989 "Amdahler Six" (Amdahl 1200)
2 756 839 -1 227.832 1992 Slowinski & Gage (Cray 2)
2 859 433 -1 258.716 1994 Slowinski & Gage (Cray C90)
2 1,257,787 −1 378.632 1996 Slowinski & Gage (Cray T94)
2 1,398,269 −1 420.921 1996 Armengaud, Woltman ( GIMPS , Pentium 90 MHz)
2 2,976,221 −1 895.932 1997 Spence, Woltman (GIMPS, Pentium 100 MHz)
2 3,021,377 −1 909.526 1998 Clarkson, Woltman, Kurowski (GIMPS, Pentium 200 MHz)
2 6,972,593 −1 2,098,960 1999 Hajratwala, Woltman, Kurowski (GIMPS, Pentium 350 MHz)
2 13,466,917 −1 4,053,946 2001 Cameron, Woltman, Kurowski (GIMPS, Athlon 800 MHz)
2 20.996.011 −1 6.320.430 2003 Shafer (GIMPS, Pentium 4 2 GHz)
2 24,036,583 −1 7,235,733 2004 Findley (GIMPS, Pentium 4 2.4 GHz)
2 25,964,951 −1 7,816,230 2005 Nowak (GIMPS, Pentium 4 2.4 GHz)
2 30,402,457 −1 9,152,052 2005 Cooper, Boone (GIMPS, Pentium 4 3 GHz)
2 32,582,657 −1 9,808,358 2006 Cooper, Boone (GIMPS, Pentium 4 3 GHz)
2 43.112.609 −1 12,978,189 2008 Smith, Woltman, Kurowski, et al. (GIMPS, Core 2 Duo 2.4 GHz)
2 57,885,161 −1 17,425,170 2013 Cooper, Woltman, Kurowski, et al. (GIMPS, Core2 Duo E8400 @ 3.00 GHz)
2 74,207,281 −1 22,338,618 2016 Cooper, Woltman, Kurowski, et al. (GIMPS, Intel i7-4790 @ 3.60 GHz)
2 77,232,917 −1 23.249.425 2017 Jonathan Pace et al. (GIMPS, Intel i5-6600 @ 3.30 GHz)
2 82,589,933 −1 24,862,048 2018 Patrick Laroche et al. (GIMPS, Intel i5-4590T @ 2.0 GHz)

Distribution and growth

Pi function and prime number theorem

The function is shown in blue in the graphic . The function in green and the
integral logarithm in red are approximations of the function.

To investigate the distribution of the prime numbers one considers the function, among other things

,

the number of primes indicating and Primzahlzählfunktion is called. For example is

.

This function and its growth behavior is a popular research subject in number theory. Over time, some approximation formulas have been developed and improved.

The prime number theorem says that

holds, that is, the quotient of the left and right side tends towards 1:

(see asymptotic analysis )

The Dirichlet prime number theorem, on the other hand, restricts the consideration to residual classes : Let it be a natural number. If there is an integer that is not relatively prime , the arithmetic sequence can be

contain at most one prime number, because all terms in the series are divisible by the greatest common divisor of and . But if coprime is to , then the Dirichlet prime number theorem says that the sequence contains infinitely many prime numbers. For example, there are an infinite number of prime numbers of the form and an infinite number of the form ( each traverses the nonnegative natural numbers).

This statement can be further specified in the following form: It applies

here is the Euler phi function . In this sense, there are prime numbers for a fixed one in the remainder classes , each with an “equal number”.

Barriers

The (proven) Bonsian inequality guarantees that the square of a prime number is smaller than the product of all smaller prime numbers (from the fifth prime onwards).

According to Andrica's (unproven) conjecture , the difference between the roots of the -th and -th prime numbers is less than 1.

Prime gaps

The difference between two neighboring prime numbers is called the prime number gap. This difference fluctuates and there are prime number gaps of arbitrary size. But there are also restrictions on the size of the gap depending on its location:

The set of Bertrand ensures the existence of a prime number between any natural number and its double .

According to the (unproven) Legendre's conjecture, there is always at least one prime number between and .

Estimates of prime numbers and conclusions from the prime number theorem

In the following, the sequence of prime numbers is denoted by.

Estimates

The following estimates apply to indices :

(1a)
(1b)
For
(1c)
For
(1d)
(1e)
For

Consequences from the prime number theorem

With the prime number theorem, the following results are obtained:

(2a)
(2 B)
For
(2c)

For every positive real number there is a sequence of prime numbers with

.
(2d)

The set of quotients formed from all prime numbers is a dense subset of the set of all positive real numbers. That means: For any positive real numbers with there always exist prime numbers , so that

is satisfied.

Generation of prime numbers

Illustration of the
Sieve algorithm of Eratosthenes

One of the oldest algorithms for determining prime numbers is the sieve of Eratosthenes . To date, no efficient prime number generator is known. However, there are formulas where there is a certain probability that the numbers generated are prime. Such numbers have to be tested for their primality afterwards.

Special prime numbers and prime number constellations

Other special types of prime numbers can be found in the category: prime number .

generalization

In ring theory, the concept of the prime number is generalized to the elements of any commutative unitary ring. The corresponding terms are prime element and irreducible element .

The prime numbers and their negatives are then precisely the prime elements and also precisely the irreducible elements of the ring of whole numbers . In factorial rings , that is, rings with unambiguous prime factorization, the terms prime element and irreducible element coincide; in general, however, the set of prime elements is only a subset of the set of irreducible elements.

Particularly in the case of Dedekind rings , which is significant from a number-theoretical point of view , prime ideals take on the role of prime numbers.

Prime numbers in computer science

In the information security and in particular in the encryption of messages (see cryptography ) play an important role primes. They are often used in asymmetric cryptosystems such as public key encryption methods. Important examples are the Diffie-Hellman key exchange , the RSA cryptosystem , which is used by OpenPGP , among others , the Elgamal cryptosystem and the Rabin cryptosystem . The keys are calculated from large, randomly generated prime numbers that must remain secret.

Such algorithms are based on one-way functions that can be executed quickly, but the inverse of which is practically impossible to calculate with the currently known technology. New information technologies , such as quantum computers , could change that. The unsolved P-NP problem is related to this.

Prime numbers in nature

Some animal and plant species (e.g. certain cicadas or spruce ) multiply particularly strongly in cycles of prime numbers (about every 11, 13 or 17 years) in order to make it difficult for predators to adapt to the massive occurrence.

Why 1 is not a prime number

For hundreds of years mathematicians have debated whether or not the number is prime. The great mathematician Godfrey Harold Hardy , for example, designated the number 1 as a prime number in 1908, but no longer in 1929 at the latest. In general, since the 20th century, the vast majority of mathematicians have agreed not to count the number 1 among the prime numbers.

The argument that 1 is prime is as follows:

  • 1 is only divisible by itself and 1.

Arguments against that 1 is not a prime number are as follows:

  • A particularly important proposition in mathematics is the uniqueness of the prime factorization . For example, if a number were prime, the composite number would have many different prime factorizations, for example .
Suddenly every number would have an infinite number of different prime factorizations and one would have to formulate the requirements for this important theorem differently so that the uniqueness is given again.
  • If you multiply two prime numbers with each other, you get a composite number according to the definition , i.e. a number that consists of at least two (prime) factors. If 1 were a prime number, it could be multiplied by a prime number, for example, and the product would again be a prime number and not a composite number. The definition of the composite number would have to be much more complicated.
  • Every prime number has exactly two factors: the number 1 and itself. Has only one factor and obviously does not fulfill this property, which means that this number is different from all other prime numbers.
  • The sieve of Eratosthenes would not work, since one would first have to cross out all multiples of 1, which would not leave a single number other than the 1.
  • For all prime numbers is Euler's Phi function . But applies to . The sentence would have to be reformulated and make 1 an exception.
  • The divisor function applies to all prime numbers . For is but . It also applies . For is but . So the number 1 would be a big exception for these function (s) as well.
  • The definition of prime elements would have to be reformulated if 1 were a prime number. The new definition would be more complicated.
  • For every prime power there is a finite field that has just as many elements. If 1 were a prime number, there would also have to be a finite field with a single element. But there is no such thing. One would have to change the definition of finite fields.

There are other mathematical theorems about prime numbers that would also have to be rephrased if the number were a prime number.

The examples show that the set of prime numbers without a 1 is urgently needed - more urgently than the concept of the prime numbers including the 1. Since there are always degrees of freedom in definitions, for the sake of the economy of the terms, the decision was made to exclude (in addition to the 0) the 1 (and more generally all units ) from the prime numbers (or prime elements).

See also

literature

Web links

Commons : Prime Numbers  - collection of images, videos, and audio files
Wiktionary: Prime number  - explanations of meanings, word origins, synonyms, translations
Wikibooks: Fundamental Theorem of Arithmetic  - Learning and Teaching Materials
Wikibooks: prime numbers from 2 to 100,000  - learning and teaching materials

Individual evidence

  1. ^ Karl Ernst Georges : Comprehensive Latin-German concise dictionary . 8th, improved and increased edition. Hahnsche Buchhandlung, Hannover 1918 ( zeno.org [accessed on March 12, 2020] dictionary entry “prior”).
  2. Christlieb von Clausberg : Demonstrative arithmetic art, or science to calculate thoroughly and briefly . In which both common and other types of commercial invoices, samples and arbitrage of bills of exchange are thoroughly taught in a particularly short manner, and a description of European coins, types of bills and usages, a comparison of weights and cubic measures, the true calculation of the interusurii, a new logarithmic table, too more other mathematical and curious calculations are attached. Bernhard Christoph Breitkopf and Son , Leipzig 1762, p. 86 ( limited preview in Google Book Search [accessed March 12, 2020]).
  3. Armin Leutbecher: Number Theory: An Introduction to Algebra. Springer, 1996, ISBN 3-540-58791-8 , p. 18, limited preview in the Google book search.
  4. ^ Vaughan R. Pratt: Every Prime has a Succinct Certificate. PDF.
  5. ^ Vašek Chvátal : Lecture notes on Pratt's Primality Proofs. PDF.
  6. Vaughan Pratt's Theorem as Theorem of the Day. PDF.
  7. For proofs of Euclid's theorem see evidence archive .
  8. Mersenne Prime Number discovery - 2 82589933 -1 is Prime! Retrieved December 21, 2018 .
  9. List of known Mersenne prime numbers - PrimeNet. Retrieved November 1, 2019 .
  10. https://primes.utm.edu/bios/page.php?id=5004
  11. Daniel AJ Sokolov: Computer in Florida finds new greatest prime. In: Heise.de. December 22, 2018, accessed December 22, 2018 .
  12. Rademacher-Toeplitz: p. 164.
  13. Sierpiński: p. 146.
  14. Dressler Pigno-Young: . Nordisk Mat Tidskr . tape 24 , p. 39 .
  15. Sándor Mitrinović-Crstici: S. 247th
  16. Sierpiński: p. 145.
  17. The estimate (1d) was first found by John Barkley Rosser (see Rosser in: Proc. London Math. Soc., Vol. 45, p. 21 ff. / Sierpiński, p. 163 / Sándor-Mitrinović-Crstici, p . 247).
  18. Sierpiński: p. 162.
  19. From (1e) is obtained as Sierpiński observes, directly, the divergence in sequence .
  20. Sierpiński: p. 163.
  21. ^ Rosser-Schoenfeld: Illinois J. Math . tape 6 , p. 64 ff .
  22. Sierpiński: p. 163.
  23. As Sierpiński notes, (2b) leads directly to the prime number theorem.
  24. Sierpiński: p. 165.
  25. According to Sierpiński, this result was first obtained by the Polish mathematician Hugo Steinhaus .
  26. Sierpiński: p. 165.
  27. Klaus Schmeh : What cicadas have to do with prime numbers. In: heise online . Retrieved March 9, 2020 .
  28. Numbers count in cicada life. Max Planck Society, April 29, 2002, archived from the original on October 1, 2007 ; accessed on March 9, 2020 .
  29. Chris K. Caldwell , Angela Reddick, Yeng Xiong: The History of the Primality of One: A Selection of Sources. Journal of Integer Sequences 15 , Article 12.9.8, 2012, pp. 1-40 , accessed on February 10, 2020 .