What is a prime number? Prime numbers: history and facts

Theorem.

There are an infinite number of prime numbers.

Proof.

Let's assume that this is not the case. That is, suppose that there are only n prime numbers, and these prime numbers are p 1, p 2, ..., p n. Let us show that we can always find a prime number different from those indicated.

Consider the number p equal to p 1 ·p 2 ·…·p n +1. It is clear that this number is different from each of the prime numbers p 1, p 2, ..., p n. If the number p is prime, then the theorem is proven. If this number is composite, then by virtue of the previous theorem there is a prime divisor of this number (we denote it p n+1). Let us show that this divisor does not coincide with any of the numbers p 1, p 2, ..., p n.

If this were not so, then, according to the properties of divisibility, the product p 1 ·p 2 ·…·p n would be divided by p n+1. But the number p is also divisible by p n+1, equal to the sum p 1 ·p 2 ·…·p n +1. It follows that p n+1 must divide the second term of this sum, which is equal to one, but this is impossible.

Thus, it has been proven that a new prime number can always be found that is not included among any number of predetermined prime numbers. Therefore, there are infinitely many prime numbers.

So, due to the fact that there are an infinite number of prime numbers, when compiling tables of prime numbers, you always limit yourself from above to some number, usually 100, 1,000, 10,000, etc.

Sieve of Eratosthenes

Now we will discuss ways to create tables of prime numbers. Suppose we need to make a table of prime numbers up to 100.

The most obvious method for solving this problem is to sequentially check positive integers, starting from 2 and ending with 100, for the presence of a positive divisor that is greater than 1 and less than the number being tested (from the properties of divisibility we know that the absolute value of the divisor does not exceed the absolute value of the dividend, non-zero). If such a divisor is not found, then the number being tested is prime, and it is entered into the prime numbers table. If such a divisor is found, then the number being tested is composite; it is NOT entered in the table of prime numbers. After this, there is a transition to the next number, which is similarly checked for the presence of a divisor.

Let's describe the first few steps.

We start with the number 2. The number 2 has no positive divisors other than 1 and 2. Therefore, it is simple, therefore, we enter it in the table of prime numbers. Here it should be said that 2 is the smallest prime number. Let's move on to number 3. Its possible positive divisor other than 1 and 3 is the number 2. But 3 is not divisible by 2, therefore, 3 is a prime number, and it also needs to be included in the table of prime numbers. Let's move on to number 4. Its positive divisors other than 1 and 4 can be the numbers 2 and 3, let's check them. The number 4 is divisible by 2, therefore, 4 is a composite number and does not need to be included in the table of prime numbers. Please note that 4 is the smallest composite number. Let's move on to number 5. We check whether at least one of the numbers 2, 3, 4 is its divisor. Since 5 is not divisible by 2, 3, or 4, then it is prime, and it must be written down in the table of prime numbers. Then there is a transition to the numbers 6, 7, and so on up to 100.

This approach to compiling a table of prime numbers is far from ideal. One way or another, he has a right to exist. Note that with this method of constructing a table of integers, you can use divisibility criteria, which will slightly speed up the process of finding divisors.

There is a more convenient way to create a table of prime numbers, called. The word “sieve” present in the name is not accidental, since the actions of this method help, as it were, to “sift” whole numbers and large units through the sieve of Eratosthenes in order to separate simple ones from composite ones.

Let's show the sieve of Eratosthenes in action when compiling a table of prime numbers up to 50.

First, write down the numbers 2, 3, 4, ..., 50 in order.

The first number written, 2, is prime. Now, from number 2, we sequentially move to the right by two numbers and cross out these numbers until we reach the end of the table of numbers being compiled. This will cross out all numbers that are multiples of two.

The first number following 2 that is not crossed out is 3. This number is prime. Now, from number 3, we sequentially move to the right by three numbers (taking into account the already crossed out numbers) and cross them out. This will cross out all numbers that are multiples of three.

The first number following 3 that is not crossed out is 5. This number is prime. Now from the number 5 we consistently move to the right by 5 numbers (we also take into account the numbers crossed out earlier) and cross them out. This will cross out all numbers that are multiples of five.

Next, we cross out numbers that are multiples of 7, then multiples of 11, and so on. The process ends when there are no more numbers to cross off. Below is the completed table of prime numbers up to 50, obtained using the sieve of Eratosthenes. All uncrossed numbers are prime, and all crossed out numbers are composite.

Let's also formulate and prove a theorem that will speed up the process of compiling a table of prime numbers using the sieve of Eratosthenes.

Theorem.

The smallest positive divisor of a composite number a that is different from one does not exceed , where is from a .

Proof.

Let us denote by the letter b the smallest divisor of a composite number a that is different from one (the number b is prime, as follows from the theorem proven at the very beginning of the previous paragraph). Then there is an integer q such that a=b·q (here q is a positive integer, which follows from the rules of multiplication of integers), and (for b>q the condition that b is the least divisor of a is violated, since q is also a divisor of the number a due to the equality a=q·b ). By multiplying both sides of the inequality by a positive and an integer greater than one (we are allowed to do this), we obtain , from which and .

What does the proven theorem give us regarding the sieve of Eratosthenes?

Firstly, crossing out composite numbers that are multiples of a prime number b should begin with a number equal to (this follows from the inequality). For example, crossing out numbers that are multiples of two should begin with the number 4, multiples of three with the number 9, multiples of five with the number 25, and so on.

Secondly, compiling a table of prime numbers up to the number n using the sieve of Eratosthenes can be considered complete when all composite numbers that are multiples of prime numbers not exceeding . In our example, n=50 (since we are making a table of prime numbers up to 50) and, therefore, the sieve of Eratosthenes should eliminate all composite numbers that are multiples of the prime numbers 2, 3, 5 and 7 that do not exceed the arithmetic square root of 50. That is, we no longer need to search for and cross out numbers that are multiples of prime numbers 11, 13, 17, 19, 23 and so on up to 47, since they will already be crossed out as multiples of smaller prime numbers 2, 3, 5 and 7 .

Is this number prime or composite?

Some tasks require finding out whether a given number is prime or composite. In general, this task is far from simple, especially for numbers whose writing consists of a significant number of characters. In most cases, you have to look for some specific way to solve it. However, we will try to give direction to the train of thought for simple cases.

Of course, you can try to use divisibility tests to prove that a given number is composite. If, for example, some test of divisibility shows that a given number is divisible by some positive integer greater than one, then the original number is composite.

Example.

Prove that 898,989,898,989,898,989 is a composite number.

Solution.

The sum of the digits of this number is 9·8+9·9=9·17. Since the number equal to 9·17 is divisible by 9, then by divisibility by 9 we can say that the original number is also divisible by 9. Therefore, it is composite.

A significant drawback of this approach is that the divisibility criteria do not allow one to prove the primeness of a number. Therefore, when testing a number to see whether it is prime or composite, you need to do things differently.

The most logical approach is to try all possible divisors of a given number. If none of the possible divisors is a true divisor of a given number, then this number will be prime, otherwise it will be composite. From the theorems proved in the previous paragraph, it follows that divisors of a given number a must be sought among prime numbers not exceeding . Thus, a given number a can be sequentially divided by prime numbers (which are conveniently taken from the table of prime numbers), trying to find the divisor of the number a. If a divisor is found, then the number a is composite. If among the prime numbers not exceeding , there is no divisor of the number a, then the number a is prime.

Example.

Number 11 723 simple or compound?

Solution.

Let's find out up to what prime number the divisors of the number 11,723 can be. To do this, let's evaluate.

It's pretty obvious that , since 200 2 =40,000, and 11,723<40 000 (при необходимости смотрите статью comparison of numbers). Thus, the possible prime factors of 11,723 are less than 200. This already makes our task much easier. If we didn’t know this, then we would have to go through all the prime numbers not up to 200, but up to the number 11,723.

If desired, you can evaluate more accurately. Since 108 2 =11,664, and 109 2 =11,881, then 108 2<11 723<109 2 , следовательно, . Thus, any of the prime numbers less than 109 is potentially a prime factor of the given number 11,723.

Now we will sequentially divide the number 11,723 into prime numbers 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 . If the number 11,723 is divided by one of the written prime numbers, then it will be composite. If it is not divisible by any of the written prime numbers, then the original number is prime.

We will not describe this whole monotonous and monotonous process of division. Let's say right away that 11,723

• 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.

Tags: Add tags

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 …

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

What numbers are called “simple” in English?

Very often, schoolchildren do not know how to answer one of the most simple questions in mathematics at first glance, 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 begin with zero, and in others with one). But these are completely two different concepts. Prime numbers are natural numbers, that is, integers and positive numbers that are greater than one and that have only 2 natural divisors. Moreover, one of these divisors is the given number, and the second is one. For example, three is a prime number because it cannot be divided without a remainder by any number other than itself and one.

Composite numbers

The opposite of prime numbers is composite numbers. They are also natural, also greater than one, but have not two, but a larger number of 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 “two” is an even number and the “first number” in a series of prime numbers.

Subsequence

To construct a series of prime numbers, it is necessary to select from all natural numbers, taking into account their definition, that is, you need to act by contradiction. It is necessary to examine each of the positive natural numbers to see if it has more than two divisors. Let's try to build a series (sequence) that consists of prime numbers. The list starts with two, followed by three, since it is 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 (it is not divisible by any other number, except 1 and 5), but six is ​​divisible. And in general, if you follow all the even numbers, you will notice that except for “two”, none of them are prime. From this we conclude that even numbers, except two, are not prime. Another discovery: all numbers divisible by three, except the three 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 multitude is also not simple. Let's summarize. So, simple single-digit numbers include all odd numbers except one and nine, and even “two” are even numbers. The tens themselves (10, 20,... 40, etc.) are not simple. Two-digit, three-digit, etc. prime numbers can be determined based on the above principles: if they have no divisors other than themselves and one.

Theories about the properties of prime numbers

There is a science that studies the properties of integers, including prime numbers. This is a branch of mathematics called higher. In addition to the properties of integers, she also deals with algebraic and 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, “Number Theory” deals with the study of prime numbers.

Prime numbers are the “building blocks” of natural numbers

In arithmetic there is a theorem called the fundamental theorem. According to it, any natural number, except one, 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 method of representation is also unique. It is called factoring a natural number into prime factors. There is another name for this process - factorization of numbers. Based on this, prime numbers can be called “building material”, “blocks” for constructing natural numbers.

Search for prime numbers. Simplicity tests

Many scientists from different times tried to find some principles (systems) for finding a list of prime numbers. Science knows systems called the Atkin sieve, the Sundartham sieve, and the Eratosthenes sieve. However, they do not produce any significant results, and a simple test is used to find the prime numbers. Mathematicians also created algorithms. They are usually called primality tests. For example, there is a test developed by Rabin and Miller. It is used by cryptographers. There is also the Kayal-Agrawal-Sasquena test. However, despite sufficient accuracy, it is very difficult to calculate, which reduces its practical significance.

Does the set of prime numbers have a limit?

The ancient Greek scientist Euclid wrote in his book “Elements” that the set of primes is infinity. 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 actions cannot be divided by any of the series of prime numbers, because the remainder will always be one. 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. Besides Euclid's proof, there is a more modern formula given by the eighteenth-century Swiss mathematician Leonhard Euler. According to it, the sum reciprocal of the sum of the first n numbers grows unlimitedly as the number n increases. And here is the formula of the theorem regarding the distribution of prime numbers: (n) grows as n/ln (n).

What is the largest prime number?

The same Leonard Euler was able to find the largest prime number of 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 an eighteenth-century scientist is several times smaller than this. It should have been so, because Euler carried out this calculation manually, while our contemporary was probably helped by a computer. Moreover, this number was obtained at the Faculty of Mathematics in one of the American departments. Numbers named after this scientist pass the Luc-Lemaire 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 prime numbers. And if until 2013 the prize was awarded to those scientists who would find them from among 1 and 10 million decimal numbers, today this figure has reached from 100 million to 1 billion. The 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. Merssen.

4. Cullen.

6. Mills et al.

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

1. Luc-Lemaire.

2. Pepina.

3. Riesel.

4. Billhart - Lemaire - Selfridge and others.

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

Ilya's answer is correct, but not very detailed. In the 18th century, by the way, one was still considered a prime number. For example, such great mathematicians as Euler and Goldbach. Goldbach is the author of one of the seven problems of the millennium - the Goldbach hypothesis. The original formulation states that every even number can be represented as the sum of two prime numbers. Moreover, initially 1 was taken into account as a prime number, and we see this: 2 = 1+1. This is the smallest example that satisfies the original formulation of the hypothesis. Later it was corrected, and the formulation acquired a modern form: “every even number, starting with 4, can be represented as the sum of two prime numbers.”

Let's remember the definition. A prime number is a natural number p that has only 2 different natural divisors: p itself and 1. Corollary from the definition: a prime number p has only one prime divisor - p itself.

Now let's assume that 1 is a prime number. By definition, a prime number has only one prime divisor - itself. Then it turns out that any prime number greater than 1 is divisible by a prime number different from it (by 1). But two different prime numbers cannot be divided by each other, because otherwise they are not prime numbers, but composite numbers, and this contradicts the definition. With this approach, it turns out that there is only 1 prime number - the unit itself. But this is absurd. Therefore, 1 is not a prime number.

1, as well as 0, form another class of numbers - the class of neutral elements with respect to n-ary operations in some subset of the algebraic field. Moreover, with respect to the operation of addition, 1 is also a generating element for the ring of integers.

With this consideration, it is not difficult to discover analogues of prime numbers in other algebraic structures. Suppose we have a multiplicative group formed from powers of 2, starting from 1: 2, 4, 8, 16, ... etc. 2 acts as a formative element here. A prime number in this group is a number greater than the smallest element and divisible only by itself and the smallest element. In our group, only 4 have such properties. That’s it. There are no more prime numbers in our group.

If 2 were also a prime number in our group, then see the first paragraph - again it would turn out that only 2 is a prime number.