Prime numbers: history and facts. What does "prime number" mean?

Definition 1. Prime number− is a natural number greater than one that is divisible only by itself and 1.

In other words, a number is prime if it has only two distinct natural divisors.

Definition 2. Any natural number that has other divisors besides itself and one is called a composite number.

In other words, natural numbers that are not prime numbers are called composite numbers. From Definition 1 it follows that a composite number has more than two natural factors. The number 1 is neither prime nor composite because has only one divisor 1 and, in addition, many theorems regarding prime numbers do not hold for unity.

From Definitions 1 and 2 it follows that every positive integer greater than 1 is either a prime number or a composite number.

Below is a program to display prime numbers up to 5000. Fill in the cells, click on the "Create" button and wait a few seconds.

Prime numbers table

Statement 1. If p- prime number and a any integer, then either a divided by p, or p And a coprime numbers.

Really. If p A prime number is divisible only by itself and 1 if a not divisible by p, then the greatest common divisor a And p is equal to 1. Then p And a coprime numbers.

Statement 2. If the product of several numbers of numbers a 1 , a 2 , a 3, ... is divisible by a prime number p, then at least one of the numbers a 1 , a 2 , a 3, ...divisible by p.

Really. If none of the numbers were divisible by p, then the numbers a 1 , a 2 , a 3, ... would be coprime numbers with respect to p. But from Corollary 3 () it follows that their product a 1 , a 2 , a 3, ... is also relatively prime with respect to p, which contradicts the condition of the statement. Therefore at least one of the numbers is divisible by p.

Theorem 1. Any composite number can always be represented, and in a unique way, as the product of a finite number of prime numbers.

Proof. Let k composite number, and let a 1 is one of its divisors different from 1 and itself. If a 1 is composite, then has in addition to 1 and a 1 and another divisor a 2. If a 2 is a composite number, then it has, in addition to 1 and a 2 and another divisor a 3. Reasoning in this way and taking into account that the numbers a 1 , a 2 , a 3 , ... decrease and this series contains a finite number of terms, we will reach some prime number p 1 . Then k can be represented in the form

Suppose there are two decompositions of a number k:

Because k=p 1 p 2 p 3...divisible by a prime number q 1, then at least one of the factors, for example p 1 is divisible by q 1 . But p 1 is a prime number and is only divisible by 1 and itself. Hence p 1 =q 1 (because q 1 ≠1)

Then from (2) we can exclude p 1 and q 1:

Thus, we are convinced that every prime number that appears as a factor in the first expansion one or more times also appears in the second expansion at least as many times, and vice versa, any prime number that appears as a factor in the second expansion one or more times also appears in the first expansion at least the same number of times. Therefore, any prime number appears as a factor in both expansions the same number of times and, thus, these two expansions are the same.■

Expansion of a composite number k can be written in the following form

Where p 1 , p 2, ... various prime numbers, α, β, γ ... positive integers.

Expansion (3) is called canonical expansion numbers.

Prime numbers occur unevenly in the series of natural numbers. In some parts of the row there are more of them, in others - less. The further we move along the number series, the less common prime numbers are. The question arises, is there a largest prime number? The ancient Greek mathematician Euclid proved that there are infinitely many prime numbers. We present this proof below.

Theorem 2. The number of prime numbers is infinite.

Proof. Suppose there are a finite number of prime numbers, and let the largest prime number be p. Let's consider all numbers greater p. By assumption of the statement, these numbers must be composite and must be divisible by at least one of the prime numbers. Let's choose a number that is the product of all these prime numbers plus 1:

Number z more p because 2p already more p. p is not divisible by any of these prime numbers, because when divided by each of them gives a remainder of 1. Thus we come to a contradiction. Therefore there are an infinite number of prime numbers.

This theorem is a special case of a more general theorem:

Theorem 3. Let an arithmetic progression be given

Then any prime number included in n, should be included in m, therefore in n other prime factors that are not included in m and, moreover, these prime factors in n are included no more times than in m.

The opposite is also true. If every prime factor of a number n included at least as many times in the number m, That m divided by n.

Statement 3. Let a 1 ,a 2 ,a 3,... various prime numbers included in m So

Where i=0,1,...α , j=0,1,...,β , k=0,1,..., γ . notice, that α i accepts α +1 values, β j accepts β +1 values, γ k accepts γ +1 values, ... .

All other natural numbers are called composite. The natural number 1 is neither prime nor composite.

Example

Exercise. Which of the natural numbers written below are prime:

Answer.

Factoring a number

Representation of a natural number as a product of natural numbers is called factorization. If in the factorization of a natural number all factors are prime numbers, then such a factorization is called prime factorization.

Theorem

(Fundamental Theorem of Arithmetic)

Every natural number other than 1 can be factorized into prime factors, and in a unique way (if we identify the factorizations and , where and are prime numbers).

By combining identical prime factors in the decomposition of a number, we obtain the so-called canonical decomposition of a number:

where , are various prime numbers, and are natural numbers.

Example

Exercise. Find the canonical expansion of numbers:

Solution. To find the canonical decomposition of numbers, you must first factor them into prime factors, and then combine the same factors and write their product as a power with a natural exponent:

Answer.

Historical reference

How to determine which number is prime and which is not? The most common method for finding all prime numbers in any number range was proposed in the 3rd century. BC e. Eratosthenes (the method is called the “sieve of Eratosthenes”). Suppose we need to determine which numbers are prime. Let's write them out in a row and cross out every second number from those following the number 2 - they are all composite, since they are multiples of the number 2. The first of the remaining uncrossed out numbers - 3 - is prime. Let's cross out every third number from those following the number 3; the next of the uncrossed numbers - 5 - will also be prime. Using the same principle, we will cross out every fifth number from those following the number 5 and, in general, every single one from those following the number . All remaining uncrossed numbers will be prime numbers.

As prime numbers increase, they gradually become less and less common. However, the ancients were already well aware of the fact that there are infinitely many of them. His proof is given in Euclid's Elements.

• Translation

The properties of prime numbers were first studied by mathematicians of Ancient Greece. Mathematicians of the Pythagorean school (500 - 300 BC) were primarily interested in the mystical and numerological properties of prime numbers. They were the first to come up with ideas about perfect and friendly numbers.

A perfect number has a sum of its own divisors equal to itself. For example, the proper divisors of the number 6 are 1, 2 and 3. 1 + 2 + 3 = 6. The divisors of the number 28 are 1, 2, 4, 7 and 14. Moreover, 1 + 2 + 4 + 7 + 14 = 28.

Numbers are called friendly if the sum of the proper divisors of one number is equal to another, and vice versa - for example, 220 and 284. We can say that a perfect number is friendly to itself.

By the time of Euclid's Elements in 300 B.C. Several important facts about prime numbers have already been proven. In Book IX of the Elements, Euclid proved that there are an infinite number of prime numbers. This, by the way, is one of the first examples of using proof by contradiction. He also proves the Fundamental Theorem of Arithmetic - every integer can be represented uniquely as a product of prime numbers.

He also showed that if the number 2n-1 is prime, then the number 2n-1 * (2n-1) will be perfect. Another mathematician, Euler, was able to show in 1747 that all even perfect numbers can be written in this form. To this day it is unknown whether odd perfect numbers exist.

In the year 200 BC. The Greek Eratosthenes came up with an algorithm for finding prime numbers called the Sieve of Eratosthenes.

And then there was a big break in the history of the study of prime numbers, associated with the Middle Ages.

The following discoveries were made already at the beginning of the 17th century by the mathematician Fermat. He proved Albert Girard's conjecture that any prime number of the form 4n+1 can be written uniquely as the sum of two squares, and also formulated the theorem that any number can be written as the sum of four squares.

He developed a new method for factoring large numbers, and demonstrated it on the number 2027651281 = 44021 × 46061. He also proved Fermat's Little Theorem: if p is a prime number, then for any integer a it will be true that a p = a modulo p.

This statement proves half of what was known as the "Chinese conjecture" and dates back 2000 years: an integer n is prime if and only if 2 n -2 is divisible by n. The second part of the hypothesis turned out to be false - for example, 2,341 - 2 is divisible by 341, although the number 341 is composite: 341 = 31 × 11.

Fermat's Little Theorem served as the basis for many other results in number theory and methods for testing whether numbers are primes - many of which are still used today.

Fermat corresponded a lot with his contemporaries, especially with a monk named Maren Mersenne. In one of his letters, he hypothesized that numbers of the form 2 n +1 will always be prime if n is a power of two. He tested this for n = 1, 2, 4, 8 and 16, and was confident that in the case where n was not a power of two, the number was not necessarily prime. These numbers are called Fermat's numbers, and only 100 years later Euler showed that the next number, 2 32 + 1 = 4294967297, is divisible by 641, and therefore is not prime.

Numbers of the form 2 n - 1 have also been the subject of research, since it is easy to show that if n is composite, then the number itself is also composite. These numbers are called Mersenne numbers because he studied them extensively.

But not all numbers of the form 2 n - 1, where n is prime, are prime. For example, 2 11 - 1 = 2047 = 23 * 89. This was first discovered in 1536.

For many years, numbers of this kind provided mathematicians with the largest known prime numbers. That M 19 was proved by Cataldi in 1588, and for 200 years was the largest known prime number, until Euler proved that M 31 was also prime. This record stood for another hundred years, and then Lucas showed that M 127 is prime (and this is already a number of 39 digits), and after that research continued with the advent of computers.

In 1952 the primeness of the numbers M 521, M 607, M 1279, M 2203 and M 2281 was proven.

By 2005, 42 Mersenne primes had been found. The largest of them, M 25964951, consists of 7816230 digits.

Euler's work had a huge impact on the theory of numbers, including prime numbers. He extended Fermat's Little Theorem and introduced the φ-function. Factorized the 5th Fermat number 2 32 +1, found 60 pairs of friendly numbers, and formulated (but could not prove) the quadratic reciprocity law.

He was the first to introduce methods of mathematical analysis and develop analytical number theory. He proved that not only the harmonic series ∑ (1/n), but also a series of the form

1/2 + 1/3 + 1/5 + 1/7 + 1/11 +…

The result obtained by the sum of the reciprocals of prime numbers also diverges. The sum of n terms of the harmonic series grows approximately as log(n), and the second series diverges more slowly as log[ log(n) ]. This means that, for example, the sum of the reciprocals of all prime numbers found to date will give only 4, although the series still diverges.

At first glance, it seems that prime numbers are distributed quite randomly among integers. For example, among the 100 numbers immediately before 10000000 there are 9 primes, and among the 100 numbers immediately after this value there are only 2. But over large segments the prime numbers are distributed quite evenly. Legendre and Gauss dealt with issues of their distribution. Gauss once told a friend that in any free 15 minutes he always counts the number of primes in the next 1000 numbers. By the end of his life, he had counted all the prime numbers up to 3 million. Legendre and Gauss equally calculated that for large n the prime density is 1/log(n). Legendre estimated the number of prime numbers in the range from 1 to n as

π(n) = n/(log(n) - 1.08366)

And Gauss is like a logarithmic integral

π(n) = ∫ 1/log(t) dt

With an integration interval from 2 to n.

The statement about the density of primes 1/log(n) is known as the Prime Distribution Theorem. They tried to prove it throughout the 19th century, and progress was achieved by Chebyshev and Riemann. They connected it with the Riemann hypothesis, a still unproven hypothesis about the distribution of zeros of the Riemann zeta function. The density of prime numbers was simultaneously proved by Hadamard and Vallée-Poussin in 1896.

There are still many unsolved questions in prime number theory, some of which are hundreds of years old:

• The twin prime hypothesis is about an infinite number of pairs of prime numbers that differ from each other by 2
• Goldbach's conjecture: any even number, starting with 4, can be represented as the sum of two prime numbers
• Is there an infinite number of prime numbers of the form n 2 + 1?
• Is it always possible to find a prime number between n 2 and (n + 1) 2? (the fact that there is always a prime number between n and 2n was proven by Chebyshev)
• Is the number of Fermat primes infinite? Are there any Fermat primes after 4?
• is there an arithmetic progression of consecutive primes for any given length? for example, for length 4: 251, 257, 263, 269. The maximum length found is 26.
• Is there an infinite number of sets of three consecutive prime numbers in an arithmetic progression?
• n 2 - n + 41 is a prime number for 0 ≤ n ≤ 40. Is there an infinite number of such prime numbers? The same question for the formula n 2 - 79 n + 1601. These numbers are prime for 0 ≤ n ≤ 79.
• Is there an infinite number of prime numbers of the form n# + 1? (n# is the result of multiplying all prime numbers less than n)
• Is there an infinite number of prime numbers of the form n# -1 ?
• Is there an infinite number of prime numbers of the form n? + 1?
• Is there an infinite number of prime numbers of the form n? - 1?
• if p is prime, does 2 p -1 always not contain prime squares among its factors?
• does the Fibonacci sequence contain an infinite number of prime numbers?

The largest twin prime numbers are 2003663613 × 2 195000 ± 1. They consist of 58711 digits and were discovered in 2007.

The largest factorial prime number (of the type n! ± 1) is 147855! - 1. It consists of 142891 digits and was found in 2002.

The largest primorial prime number (a number of the form n# ± 1) is 1098133# + 1.

Prime number

a natural number greater than one and having no divisors other than itself and one: 2, 3, 5, 7, 11, 13... The number of prime numbers is infinite.

Prime number

a positive integer greater than one, which has no divisors other than itself and one: 2, 3, 5, 7, 11, 13,... The concept of a number is fundamental in the study of the divisibility of natural (positive integers) numbers; Namely, the main theorem of the theory of divisibility establishes that every positive integer, except 1, is uniquely decomposed in the product of a number of numbers (the order of the factors is not taken into account). There are infinitely many prime numbers (this proposal was known to ancient Greek mathematicians; its proof is available in the 9th book of Euclid’s Elements). Questions of the divisibility of natural numbers, and therefore questions related to prime numbers, are important in the study of groups; in particular, the structure of a group with a finite number of elements is closely related to the way in which this number of elements (the order of the group) is decomposed into prime factors. The theory of algebraic numbers deals with the issues of divisibility of algebraic integers; The concept of a partial number turned out to be insufficient for constructing a theory of divisibility; this led to the creation of the concept of an ideal. P. G. L. Dirichlet established in 1837 that the arithmetic progression a + bx for x = 1, 2,... with coprime integers a and b contains infinitely many prime numbers. Determining the distribution of prime numbers in the natural series of numbers is a very difficult problem in number theory. It is formulated as a study of the asymptotic behavior of the function p(x), which denotes the number of partial numbers not exceeding a positive number x. The first results in this direction belong to P.L. Chebyshev, who in 1850 proved that there are two constants a and A such that ═< p(x) < ═при любых x ³ 2 [т. е., что p(х) растет, как функция ]. Хронологически следующим значительным результатом, уточняющим теорему Чебышева, является т. н. асимптотический закон распределения П. ч. (Ж. Адамар, 1896, Ш. Ла Валле Пуссен, 1896), заключающийся в том, что предел отношения p(х) к ═равен

Subsequently, significant efforts of mathematicians were directed toward clarifying the asymptotic law of the distribution of the frequency factor. Questions of the distribution of the frequency factor are studied both by elementary methods and by methods of mathematical analysis. Particularly fruitful is the method based on the use of the identity

(the product extends to all P. h. p = 2, 3,...), first indicated by L. Euler; this identity is valid for all complex s with a real part greater than unity. On the basis of this identity, questions of the distribution of P. numbers are led to the study of a special function ≈ zeta function x(s), determined for Res > 1 by the series

This function was used in questions of the distribution of prime numbers for real s by Chebyshev; B. Riemann pointed out the importance of studying x(s) for complex values ​​of s. Riemann hypothesized that all roots of the equation x(s) = 0 lying in the right half-plane have a real part equal to 1/

This hypothesis has not been proven to date (1975); its proof would do a great deal in solving the problem of the distribution of prime numbers. Questions of the distribution of prime numbers are closely related to Goldbach’s problem, the still unsolved problem of “twins,” and other problems of analytic number theory. The problem of the “twins” is to find out whether the number of P. numbers differing by 2 (such as, for example, 11 and 13) is finite or infinite. Tables of P. numbers lying within the first 11 million natural numbers show the presence of very large “twins” (for example, 10006427 and 10006429), but this is not proof of the infinity of their number. Outside the compiled tables, individual partial numbers are known that admit of a simple arithmetic expression [for example, it was established (1965) that 211213 ≈1 is a regular number; it has 3376 digits].

Lit.: Vinogradov I.M., Fundamentals of Number Theory, 8th ed., M., 1972; Hasse G., Lectures on number theory, trans. from German, M., 1953; Ingham A.E., Distribution of prime numbers, trans. from English, M. ≈ L., 1936; Prahar K., Distribution of prime numbers, trans. from German, M., 1967; Trost E., Prime numbers, transl., from German, M., 1959.

Wikipedia

Prime number

Prime number- a natural number that has exactly two distinct natural divisors - and itself. In other words, the number x is prime if it is greater than 1 and is divisible without remainder only by 1 and x. For example, 5 is a prime number, and 6 is a composite number, since, in addition to 1 and 6, it is also divisible by 2 and 3.

Natural numbers that are greater than one and are not prime numbers are called composite numbers. Thus, all natural numbers are divided into three classes: one. Number theory studies the properties of prime numbers. In ring theory, prime numbers correspond to irreducible elements.

The sequence of prime numbers starts like this:

2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 53 , 59 , 61 , 67 , 71 , 73 , 79 , 83 , 89 , 97 , 101 , 103 , 107 , 109 , 113 , 127 , 131 , 137 , 139 , 149 , 151 , 157 , 163 , 167 , 173 , 179 , 181 , 191 , 193 , 197 , 199 …

Prime number is a natural (positive integer) number that is divisible without a remainder by only two natural numbers: by and by itself. In other words, a prime number has exactly two natural divisors: and the number itself.

By definition, the set of all divisors of a prime number is two-element, i.e. represents a set.

The set of all prime numbers is denoted by the symbol. Thus, due to the definition of the set of prime numbers, we can write: .

The sequence of prime numbers looks like this:

Fundamental Theorem of Arithmetic

Fundamental Theorem of Arithmetic states that every natural number greater than one can be represented as a product of prime numbers, and in a unique way, up to the order of the factors. Thus, prime numbers are the elementary "building blocks" of the set of natural numbers.

Natural number expansion title="Rendered by QuickLaTeX.com" height="13" width="42" style="vertical-align: -1px;"> в произведение простых чисел называют !} canonical:

where is a prime number, and . For example, the canonical expansion of a natural number looks like this: .

Representing a natural number as a product of primes is also called factorization of a number.

Properties of Prime Numbers

Sieve of Eratosthenes

One of the most famous algorithms for searching and recognizing prime numbers is sieve of Eratosthenes. So this algorithm was named after the Greek mathematician Eratosthenes of Cyrene, who is considered the author of the algorithm.

To find all prime numbers less than a given number, following Eratosthenes' method, follow these steps:

Step 1. Write down all the natural numbers from two to , i.e. .
Step 2. Assign the variable the value , that is, the value equal to the smallest prime number.
Step 3. Cross out in the list all numbers from to that are multiples of , that is, the numbers: .
Step 4. Find the first uncrossed number in the list greater than , and assign the value of this number to a variable.
Step 5. Repeat steps 3 and 4 until number is reached.

The process of applying the algorithm will look like this:

All remaining uncrossed numbers in the list at the end of the process of applying the algorithm will be the set of prime numbers from to .

Goldbach conjecture

Cover of the book “Uncle Petros and the Goldbach Hypothesis”

Despite the fact that prime numbers have been studied by mathematicians for quite a long time, many related problems remain unsolved today. One of the most famous unsolved problems is Goldbach's hypothesis, which is formulated as follows:

• Is it true that every even number greater than two can be represented as the sum of two prime numbers (Goldbach's binary hypothesis)?
• Is it true that every odd number greater than 5 can be represented as the sum of three prime numbers (Goldbach's ternary hypothesis)?

It should be said that the ternary Goldbach hypothesis is a special case of the binary Goldbach hypothesis, or as mathematicians say, the ternary Goldbach hypothesis is weaker than the binary Goldbach hypothesis.

Goldbach's conjecture became widely known outside the mathematical community in 2000 thanks to a promotional marketing stunt by the publishing companies Bloomsbury USA (USA) and Faber and Faber (UK). These publishing houses, having released the book “Uncle Petros and Goldbach’s Conjecture,” promised to pay a prize of 1 million US dollars to anyone who proves Goldbach’s hypothesis within 2 years from the date of publication of the book. Sometimes the mentioned prize from publishers is confused with prizes for solving the Millennium Prize Problems. Make no mistake, Goldbach’s hypothesis is not classified by the Clay Institute as a “millennium challenge,” although it is closely related to Riemann hypothesis- one of the “millennium challenges”.

The book “Prime numbers. Long road to infinity"

Cover of the book “The World of Mathematics. Prime numbers. Long road to infinity"

Additionally, I recommend reading a fascinating popular science book, the annotation to which says: “The search for prime numbers is one of the most paradoxical problems in mathematics. Scientists have been trying to solve it for several millennia, but, growing with new versions and hypotheses, this mystery still remains unsolved. The appearance of prime numbers is not subject to any system: they appear spontaneously in the series of natural numbers, ignoring all attempts by mathematicians to identify patterns in their sequence. This book will allow the reader to trace the evolution of scientific concepts from ancient times to the present day and introduce the most interesting theories of searching for prime numbers.”

Additionally, I will quote the beginning of the second chapter of this book: “Prime numbers are one of the important topics that take us back to the very origins of mathematics, and then, along a path of increasing complexity, lead us to the forefront of modern science. Thus, it would be very useful to trace the fascinating and complex history of prime number theory: exactly how it developed, exactly how the facts and truths that are now generally accepted were collected. In this chapter we will see how generations of mathematicians carefully studied the natural numbers in search of a rule that predicted the appearance of prime numbers - a rule that became increasingly elusive as the search progressed. We will also look in detail at the historical context: the conditions under which mathematicians worked and the extent to which their work involved mystical and semi-religious practices, which are quite different from the scientific methods used in our time. Nevertheless, slowly and with difficulty, the ground was prepared for new views that inspired Fermat and Euler in the 17th and 18th centuries.”