The largest prime single digit number. Theories about the properties of prime numbers

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 a 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,..., γ . Note that αi accepts α +1 values, β j accepts β +1 values, γ k accepts γ +1 values, ... .

Prime numbers are one of the most interesting mathematical phenomena, which have 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 riddles of prime numbers have not yet been solved; there are even some 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 any other number, then it is called composite. One of the most famous theorems states that any composite number can be represented as a unique possible product of prime numbers.

Some interesting facts. Firstly, 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 classify it specifically in the first group, since formally it fully satisfies its requirements.

Secondly, the only even number squeezed into the “prime numbers” group is, naturally, two. Any other even number simply cannot get here, since by definition, in addition to itself and one, it is also divisible by two.

Prime numbers, the list of which, as stated above, can begin with one, represent an infinite series, as infinite as the series of natural numbers. Based on the fundamental theorem of arithmetic, we 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 they might seem at first glance. Having carefully analyzed them, you can immediately notice several features, the most interesting of which are associated with the so-called “twin” numbers. They are called that 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 the left one by three, the remainder always remains two, and the right one always remains one. In addition, the very distribution of these numbers over the natural series can be predicted if we imagine this entire series in the form of oscillatory sinusoids, the main points of which are formed when numbers are divided by three and two.

Prime numbers are not only the object of close consideration by mathematicians all over the world, but have long been successfully used in the compilation of various series of numbers, which is the basis, among other things, for cipherography. 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.

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 simplest 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 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 of 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 faculties. 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 receive the $250,000 prize by finding the largest prime number.

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

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

Learn about modular arithmetic. The operation "x mod y" (mod is an abbreviation of the Latin word "modulo", that is, "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” to zero again. For example, a clock keeps time with a modulus of 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 evaluate this function for large numbers.