Prime numbers are one of the most interesting mathematical phenomena that has attracted the attention of scientists and ordinary citizens for more than two millennia. Despite the fact that we now live in the age of computers and the most modern information programs, many mysteries of prime numbers have not yet been solved, there are even those that scientists do not know how to approach.

Prime numbers are, as is known from the course of elementary arithmetic, those that are divisible without a remainder only by one and itself. By the way, if a natural number is divisible, in addition to those listed above, by another number, then it is called composite. One of the most famous theorems states that any composite number can be represented as the only possible product of prime numbers.

A few interesting facts. First, the unit is unique in the sense that, in fact, it does not belong to either prime or composite numbers. At the same time, in the scientific community it is still customary to attribute it to the first group, since formally it fully satisfies its requirements.

Secondly, the only even number that has crept into the “prime numbers” group is, of course, two. Any other even number simply cannot get here, since by definition, besides itself and one, it is also divisible by two.

Prime numbers, the list of which, as mentioned above, can begin with one, are an infinite series, as infinite as the series of natural numbers. Based on the fundamental theorem of arithmetic, one can come to the conclusion that prime numbers are never interrupted and never end, since otherwise the series of natural numbers would inevitably be interrupted.

Prime numbers do not appear randomly in the natural series, as it might seem at first glance. After carefully analyzing them, you can immediately notice several features, the most curious of which are associated with the so-called "twin" numbers. They are called so because in some incomprehensible way they ended up next to each other, separated only by an even delimiter (five and seven, seventeen and nineteen).

If you look closely at them, you will notice that the sum of these numbers is always a multiple of three. Moreover, when dividing by a triple of the left fellow, the remainder always remains a two, and the right one - one. In addition, the very distribution of these numbers along the natural series can be predicted if this entire series is presented in the form of oscillatory sinusoids, the main points of which are formed when the numbers are divided by three and two.

Prime numbers are not only an object of close scrutiny by mathematicians around the world, but have long been successfully used in compiling various series of numbers, which is the basis, including for ciphergraphy. At the same time, it should be recognized that a huge number of mysteries associated with these wonderful elements are still waiting to be solved, many questions have not only philosophical, but also practical significance.

Definition 1. Prime number is a natural number greater than 1 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 composite number.

In other words, natural numbers that are not prime are called composite numbers. Definition 1 implies that a composite number has more than two natural divisors. The number 1 is neither prime nor composite. has only one divisor 1 and, besides this, many theorems about prime numbers do not hold for unity.

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

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

Prime number table

Statement 1. If a p is a prime number and a any integer, then either a divided by p, or p and a relatively prime numbers.

Really. If a p prime number, then it is only divisible by itself and 1 if a not divisible by p, then the greatest common divisor a and p equals 1. Then p and a relatively prime 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 , ... is divisible by p.

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

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

Proof. Let be k composite number, and let a 1 is one of its divisors different from 1 and itself. If a a 1 is composite, then it has in addition to 1 and a 1 and another divider a 2. If a a 2 is a composite number, then it has, in addition to 1 and a 2 and another divider a 3 . Arguing 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 one . Then k can be represented as

Suppose there are two expansions of a number k:

As k=p 1 p 2 p 3 ... is divisible by a prime number q 1 , then at least one of the factors, for example p 1 is divisible by q one . But p 1 is prime 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 make sure that any prime number that enters the first expansion as a factor one or more times enters the second expansion at least the same number of times and vice versa, any prime number that enters the second expansion as a factor one or several times also enters the first expansion at least as many times. Therefore, any prime number enters as a factor in both expansions the same number of times and, thus, these two expansions are the same.■

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

where p 1 , p 2 , ... distinct prime numbers, α, β, γ ... integer positive numbers.

Decomposition (3) is called canonical decomposition numbers.

Prime numbers in the series of natural numbers occur unevenly. In some parts of the series there are more of them, in others - less. The further we move along the number series, the rarer the prime numbers. The question is, 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 primes, and let the largest prime be p. Let's consider all the numbers p. By the 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 primes plus 1:

Number z more p as 2p already more p. p is not divisible by any of these prime numbers, since when divided by each of them, it gives a remainder of 1. Thus we arrive at 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 in n, should also be included in m, so in n cannot include other prime factors that are not included in m and, moreover, these prime factors in n appear no more times than in m.

The reverse is also true. If every prime factor of a number n occurs at least the same number of times m, then m divided by n.

Statement 3. Let be a 1 ,a 2 ,a 3 ,... various primes appearing in m so

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

• Translation

The properties of prime numbers were first studied by the 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 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 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 the appearance of the work of Euclid's "Beginnings" in 300 BC. 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. By the way, this is one of the first examples of the use of proof by contradiction. He also proves the Basic Theorem of Arithmetic - every integer can be represented in a unique way as a product of prime numbers.

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

In the year 200 B.C. 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 a sum of two squares, and also formulated a theorem that any number can be represented as a sum of four squares.

He developed a new factorization method for 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, a p = a modulo p will be true.

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

Fermat's Little Theorem was the basis for many other results in number theory and methods for testing whether numbers are prime, many of which are still in use today.

Fermat corresponded extensively with his contemporaries, especially with a monk named Marin Mersenne. In one of his letters, he conjectured 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 sure that when n is not a power of two, the number was not necessarily prime. These numbers are called Fermat numbers, and it wasn't until 100 years later that Euler showed that the next number, 232 + 1 = 4294967297, is divisible by 641 and therefore 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 actively studied them.

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 gave mathematicians the largest known primes. That the number M 19 was proved by Cataldi in 1588, and for 200 years was the largest known prime number, until Euler proved that M 31 is also prime. This record held 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 proved.

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 number theory, 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 failed to prove) the quadratic law of reciprocity.

He was the first to introduce the methods of mathematical analysis and developed the analytic theory of numbers. 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 +…

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

At first glance, it seems that prime numbers are distributed among integers rather randomly. 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 on large segments, prime numbers are distributed fairly evenly. Legendre and Gauss dealt with 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 density of primes is 1/log(n). Legendre estimated the number of primes between 1 and n as

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

And Gauss - as 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 Numbers Theorem. They tried to prove it throughout the 19th century, and Chebyshev and Riemann made progress. They connected it with the Riemann Hypothesis, a hitherto unproven conjecture about the distribution of zeros of the Riemann zeta function. The density of primes was simultaneously proved by Hadamard and de la Vallée-Poussin in 1896.

In the theory of prime numbers, there are still many unresolved questions, some of which are many hundreds of years old:

• twin prime hypothesis - about an infinite number of pairs of prime numbers that differ from each other by 2
• Goldbach's conjecture: any even number, starting from 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 proved by Chebyshev)
• Is there an infinite number of Fermat primes? are there any Fermat primes after the 4th?
• 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 primes 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! - one?
• if p is prime, does 2 p -1 always not include among the factors of squared primes
• Does the Fibonacci sequence contain an infinite number of primes?

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

The largest factorial prime number (of the form 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.

List of divisors. By definition, the number n is prime only if it is not evenly divisible by 2 and any integers other than 1 and itself. The above formula removes unnecessary steps and saves time: for example, after checking if a number is divisible by 3, there is no need to check if it is divisible by 9.

• The floor(x) function rounds x to the nearest integer less than or equal to x.

Learn about modular arithmetic. The operation "x mod y" (mod is short for the Latin word "modulo", meaning "module") means "divide x by y and find the remainder". In other words, in modular arithmetic, upon reaching a certain value, which is called module, the numbers "turn" back to zero. For example, a clock measures time in modulus 12: it shows 10, 11, and 12 o'clock and then returns to 1.

• Many calculators have a mod key. The end of this section shows how to manually calculate this function for large numbers.

Numbers are different: natural, natural, rational, integer and fractional, positive and negative, complex and prime, odd and even, real, etc. From this article you can learn what prime numbers are.

What numbers are called the English word "simple"?

Very often, schoolchildren do not know how to answer one of the most seemingly simple questions in mathematics, about what a prime number is. They often confuse prime numbers with natural numbers (that is, the numbers that people use when counting objects, while in some sources they start from zero, and in others - from one). But these are two completely different concepts. Prime numbers are natural numbers, that is, integer and positive numbers that are greater than one and that have only 2 natural divisors. In this case, one of these divisors is a given number, and the second is a unit. For example, three is a prime number because it is not evenly divisible by any number other than itself and one.

Composite numbers

The opposite of prime numbers are composite numbers. They are also natural, also greater than one, but have not two, but more divisors. So, for example, the numbers 4, 6, 8, 9, etc. are natural, composite, but not prime numbers. As you can see, these are mostly even numbers, but not all. But the “two” is an even number and the “first number” in a series of prime numbers.

Subsequence

To build a series of prime numbers, it is necessary to make a selection from all natural numbers, taking into account their definition, that is, you need to act by contradiction. It is necessary to consider each of the natural positive numbers on the subject of whether it has more than two divisors. Let's try to build a series (sequence) that consists of prime numbers. The list starts with two, then comes three, since it's only divisible by itself and one. Consider the number four. Does it have divisors other than four and one? Yes, that number is 2. So four is not a prime number. Five is also prime (besides 1 and 5, it is not divisible by any other number), but six is ​​divisible. And in general, if you follow all the even numbers, you will notice that apart from “two”, none of them is prime. From this we conclude that even numbers, except for two, are not prime. Another discovery: all numbers that are divisible by three, except for the triple itself, whether even or odd, are also not prime (6, 9, 12, 15, 18, 21, 24, 27, etc.). The same applies to numbers that are divisible by five and seven. All their set is also not simple. Let's summarize. So, all odd numbers, except for one and nine, belong to simple single-digit numbers, and only “two” from even ones. The tens themselves (10, 20,... 40, etc.) are not prime. Two-digit, three-digit, etc. prime numbers can be defined based on the above principles: if they have no other divisors than themselves and one.

Theories about the properties of prime numbers

There is a science that studies the properties of integers, including prime ones. This is a branch of mathematics, which is called higher. In addition to the properties of integers, she also deals with algebraic, transcendental numbers, as well as functions of various origins related to the arithmetic of these numbers. In these studies, in addition to elementary and algebraic methods, analytical and geometric ones are also used. Specifically, the study of prime numbers deals with "Number Theory".

Prime numbers are the “building blocks” of natural numbers

In arithmetic there is a theorem called the main theorem. According to it, any natural number, except for unity, can be represented as a product, the factors of which are prime numbers, and the order of the factors is unique, which means that the representation method is unique. It is called the decomposition of a natural number into prime factors. There is another name for this process - factorization of numbers. Proceeding from this, prime numbers can be called “building material”, “blocks” for constructing natural numbers.

Search for prime numbers. Simplicity Tests

Many scientists of different times tried to find some principles (systems) for finding a list of prime numbers. Science knows systems called Atkin's sieve, Sundartam's sieve, Eratosthenes' sieve. However, they do not give any significant results, and a simple test is used to find prime numbers. Algorithms were also created by mathematicians. They are called primality tests. For example, there is a test developed by Rabin and Miller. It is used by cryptographers. There is also a Kayala-Agrawala-Saskena test. However, despite its sufficient accuracy, it is very difficult to calculate, which diminishes its practical value.

Does the set of primes have a limit?

The fact that the set of primes is infinity was written in the book "Beginnings" by the ancient Greek scientist Euclid. He said this: “Let's imagine for a moment that prime numbers have a limit. Then let's multiply them with each other, and add one to the product. The number obtained as a result of these simple operations cannot be divisible by any of the series of prime numbers, because the remainder will always be one. And this means that there is some other number that is not yet included in the list of prime numbers. Therefore, our assumption is not true, and this set cannot have a limit. In addition to Euclid's proof, there is a more modern formula given by the eighteenth-century Swiss mathematician Leonhard Euler. According to him, the sum, the reciprocal of the sum of the first n numbers, grows indefinitely with the growth of the number n. And here is the formula of the theorem regarding the distribution of prime numbers: (n) grows like n / ln (n).

What is the largest prime number?

All the same Leonard Euler was able to find the largest prime number for his time. This is 2 31 - 1 = 2147483647. However, by 2013, another most accurate largest in the list of prime numbers was calculated - 2 57885161 - 1. It is called the Mersenne number. It contains about 17 million decimal digits. As you can see, the number found by a scientist from the eighteenth century is several times smaller than this. It should have been so, because Euler did this calculation manually, but our contemporary was probably helped by a computer. Moreover, this number was obtained at the Department of Mathematics in one of the American departments. Numbers named after this scientist pass through the Luc-Lehmer primality test. However, science does not want to stop there. The Electronic Frontier Foundation, which was founded in 1990 in the United States of America (EFF), has offered a monetary reward for finding large primes. And if until 2013 the prize was given to those scientists who will find them from among 1 and 10 million decimal numbers, today this figure has reached from 100 million to 1 billion. Prizes range from 150 to 250 thousand US dollars.

Names of special prime numbers

Those numbers that were found thanks to algorithms created by certain scientists and passed the simplicity test are called special. Here are some of them:

1. Mersin.

4. Cullen.

6. Mills et al.

The simplicity of these numbers, named after the above scientists, is established using the following tests:

1. Lucas-Lemer.

2. Pepina.

3. Riesel.

4. Billhart - Lehmer - Selfridge and others.

Modern science does not stop there, and probably in the near future the world will know the names of those who were able to win a prize of 250,000 dollars by finding the largest prime number.