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 represented 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.
A prime number is a natural number that is only divisible by itself and one.
The rest of the numbers are called composite.
Simple natural numbers
But not all natural numbers are prime.
Simple natural numbers are only those that are divisible only by themselves and by one.
Examples of prime numbers:
2; 3; 5; 7; 11; 13;...
Simple integers
It follows that only natural numbers are prime numbers.
This means that prime numbers are necessarily natural.
But all natural numbers are also integers.
Thus, all prime numbers are integers.
Examples of prime numbers:
2; 3; 5; 7; 11; 13; 17; 19; 23;...
Even prime numbers
There is only one even prime number, and that is two.
All other prime numbers are odd.
Why can't an even number greater than two be a prime number?
But because any even number greater than two will be divisible by itself, not by one, but by two, that is, such a number will always have three divisors, and possibly more.
All natural numbers, except for one, are divided into prime and composite. A prime number is a natural number that has only two divisors: one and itself.. All others are called composite. The study of the properties of prime numbers deals with a special section of mathematics - number theory. In ring theory, prime numbers are related to irreducible elements.
Here is a sequence of prime numbers starting from 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, ... etc.
According to the fundamental theorem of arithmetic, every natural number that is greater than one can be represented as a product of prime numbers. However, this is the only way to represent natural numbers up to the order of the factors. Based on this, we can say that prime numbers are the elementary parts of natural numbers.
Such a representation of a natural number is called the decomposition of a natural number into prime numbers or the factorization of a number.
One of the oldest and most effective ways to calculate prime numbers is the "sieve of Erastothenes".
Practice has shown that after calculating prime numbers using the Erastofen sieve, it is required to check whether the given number is prime. For this, special tests, the so-called simplicity tests, have been developed. The algorithm of these tests are probabilistic. Most often they are used in cryptography.
By the way, for some classes of numbers there are specialized effective primality tests. For example, to test Mersenne numbers for simplicity, the Lucas-Lehmer test is used, and to test for the simplicity of Fermat numbers, the Pepin test is used.
We all know that there are infinitely many numbers. The question rightly arises: how many prime numbers are there then? There are also an infinite number of prime numbers. The most ancient proof of this judgment is the proof of Euclid, which is set forth in the Elements. Euclid's proof is as follows:
Imagine that the number of primes is finite. Let's multiply them and add one. The resulting number cannot be divided by any of the finite set of prime numbers, because the remainder of dividing by any of them gives one. Thus, the number must be divisible by some prime not included in this set.
The prime number distribution theorem states that the number of primes less than n, denoted π(n), grows as n / ln(n).
Through thousands of years of studying prime numbers, it has been found that the largest known prime number is 243112609 − 1. This number has 12,978,189 decimal digits and is a Mersenne prime (M43112609). This discovery was made on August 23, 2008 at the uCLA University Mathematics Department as part of the GIMPS distributed search for Mersenne primes.
The main distinguishing feature of Mersenne numbers is the presence of a highly efficient Luc-Lehmer primality test. With it, Mersenne primes are, over a long period of time, the largest known primes.
However, to this day, many questions about prime numbers have not received exact answers. At the 5th International Mathematical Congress, Edmund Landau formulated the main problems in the field of prime numbers:
The Goldbach problem, or Landau's first problem, is to prove or disprove that every even number greater than two can be represented as the sum of two primes, and every odd number greater than 5 can be represented as the sum of three primes. numbers.
Landau's second problem requires finding an answer to the question: is there an infinite set of "simple twins" - prime numbers, the difference between which is equal to 2?
Legendre's conjecture or Landau's third problem is: is it true that between n2 and (n + 1)2 there is always a prime number?
Landau's fourth problem: Is the set of prime numbers of the form n2 + 1 infinite?
In addition to the above problems, there is the problem of determining an infinite number of primes in many integer sequences such as the Fibonacci number, Fermat number, etc.
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 major mathematicians as Euler and Goldbach. Goldbach is the author of one of the seven tasks of the millennium - the Goldbach hypothesis. The original formulation states that any even number can be represented as the sum of two primes. 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 look: "every even number, starting from 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. A consequence of the definition: a prime number p has only one prime divisor - p itself.
Now suppose 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 that differs from it (by 1). But two distinct prime numbers cannot be divisible by each other, because otherwise they are not prime, 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-nar operations in some subset of the algebraic field. Moreover, with respect to the addition operation, 1 is also a generating element for the ring of integers.
Considering this, it is not difficult to find 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 here as a forming element. A prime number in this group is a number that is 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.
The article deals with the concepts of prime and composite numbers. Definitions of such numbers with examples are given. We give a proof that the number of primes is unlimited and make an entry in the table of primes using the method of Eratosthenes. Proofs will be given as to whether a number is prime or composite.
Yandex.RTB R-A-339285-1
Prime and Composite Numbers - Definitions and Examples
Prime and composite numbers are classified as positive integers. They must be greater than one. Divisors are also divided into simple and compound. To understand the concept of composite numbers, it is necessary to first study the concepts of divisors and multiples.
Definition 1
Prime numbers are integers that are greater than one and have two positive divisors, that is, themselves and 1.
Definition 2
Composite numbers are integers that are greater than one and have at least three positive divisors.
One is neither a prime nor a composite number. It has only one positive divisor, so it is different from all other positive numbers. All positive integers are called natural, that is, used in counting.
Definition 3
prime numbers are natural numbers that have only two positive divisors.
Definition 4
Composite number is a natural number that has more than two positive divisors.
Any number greater than 1 is either prime or composite. From the property of divisibility, we have that 1 and the number a will always be divisors for any number a, that is, it will be divisible by itself and by 1. We give the definition of integers.
Definition 5
Natural numbers that are not prime are called composite numbers.
Prime numbers: 2, 3, 11, 17, 131, 523. They are divisible only by themselves and by 1. Composite numbers: 6, 63, 121, 6697. That is, the number 6 can be decomposed into 2 and 3, and 63 into 1, 3, 7, 9, 21, 63, and 121 into 11, 11, that is, its divisors will be 1, 11, 121. The number 6697 will decompose into 37 and 181. Note that the concepts of prime numbers and relatively prime numbers are different concepts.
To make it easier to use prime numbers, you need to use a table:
A table for all existing natural numbers is unrealistic, since there are an infinite number of them. When the numbers reach sizes of 10000 or 1000000000, then you should think about using the sieve of Eratosthenes.
Consider a theorem that explains the last statement.
Theorem 1
The smallest positive divisor of a natural number greater than 1 other than 1 is a prime number.
Proof 1
Assume that a is a natural number greater than 1, b is the smallest non-one divisor of a. We must prove that b is a prime number using the contradiction method.
Let's say b is a composite number. From here we have that there is a divisor for b , which is different from 1 as well as from b . Such a divisor is denoted as b 1 . It is necessary that condition 1< b 1 < b has been completed.
It can be seen from the condition that a is divisible by b, b is divisible by b 1, which means that the concept of divisibility is expressed in this way: a = b q and b = b 1 q 1 , whence a = b 1 (q 1 q) , where q and q 1 are integers. According to the rule of multiplication of integers, we have that the product of integers is an integer with an equality of the form a = b 1 · (q 1 · q) . It can be seen that b 1 is the divisor of a. Inequality 1< b 1 < b not matches, because we get that b is the smallest positive non-1 divisor of a.
Theorem 2
There are infinitely many prime numbers.
Proof 2
Suppose we take a finite number of natural numbers n and denote as p 1 , p 2 , … , p n . Let's consider a variant of finding a prime number different from the indicated ones.
Consider the number p, which is equal to p 1 , p 2 , … , p n + 1 . It does not equal each of the numbers corresponding to primes of the form p 1 , p 2 , … , p n . The number p is prime. Then the theorem is considered to be proved. If it is composite, then we need to take the notation p n + 1 and show divisor mismatch with any of p 1 , p 2 , … , p n .
If this were not so, then, based on the divisibility property of the product p 1 , p 2 , … , p n , we get that it would be divisible by p n + 1 . Note that the expression p n + 1 the number p is divided equals the sum p 1 , p 2 , … , p n + 1 . We get that the expression p n + 1 the second term of this sum, which is equal to 1, must be divided, but this is impossible.
It can be seen that any prime number can be found among any number of given primes. It follows that there are infinitely many prime numbers.
Since there are a lot of prime numbers, the tables are limited to numbers 100, 1000, 10000 and so on.
When compiling a table of prime numbers, it should be borne in mind that such a task requires a sequential check of numbers, starting from 2 to 100. If there is no divisor, it is recorded in the table; if it is composite, then it is not entered in the table.
Let's consider step by step.
If you start with the number 2, then it has only 2 divisors: 2 and 1, which means that it can be entered in the table. Also with the number 3 . The number 4 is composite, it should be decomposed into 2 and 2. The number 5 is prime, which means it can be fixed in the table. Do this up to the number 100.
This method is inconvenient and time consuming. You can make a table, but you will have to spend a lot of time. It is necessary to use divisibility criteria, which will speed up the process of finding divisors.
The method using the sieve of Eratosthenes is considered the most convenient. Let's take a look at the tables below. To begin with, the numbers 2, 3, 4, ..., 50 are written.
Now you need to cross out all the numbers that are multiples of 2. Make sequential strikethrough. We get a table of the form:
Let's move on to crossing out numbers that are multiples of 5. We get:
We cross out the numbers that are multiples of 7, 11. Finally the table looks like
Let us pass to the formulation of the theorem.
Theorem 3
The smallest positive and non-1 divisor of the base number a does not exceed a , where a is the arithmetic root of the given number.
Proof 3
It is necessary to denote b as the smallest divisor of a composite number a. There is an integer q , where a = b · q , and we have that b ≤ q . An inequality of the form b > q because the condition is violated. Both sides of the inequality b ≤ q should be multiplied by any positive number b not equal to 1 . We get that b b ≤ b q , where b 2 ≤ a and b ≤ a .
It can be seen from the proved theorem that crossing out numbers in the table leads to the fact that it is necessary to start with a number that is equal to b 2 and satisfies the inequality b 2 ≤ a . That is, if you cross out numbers that are multiples of 2, then the process starts from 4, and those that are multiples of 3 start from 9, and so on up to 100.
Compiling such a table using Eratosthenes' theorem says that when all composite numbers are crossed out, there will remain prime ones that do not exceed n. In the example where n = 50 , we have that n = 50 . From here we get that the sieve of Eratosthenes sifts out all composite numbers that are not greater than the value of the root of 50. The search for numbers is done by crossing out.
Before solving, it is necessary to find out whether the number is prime or composite. Divisibility criteria are often used. Let's look at this in the example below.
Example 1
Prove that 898989898989898989 is a composite number.
Solution
The sum of the digits of the given number is 9 8 + 9 9 = 9 17 . So the number 9 17 is divisible by 9, based on the sign of divisibility by 9. It follows that it is composite.
Such signs are not able to prove the primeness of a number. If verification is needed, other steps should be taken. The most suitable way is to enumerate numbers. During the process, prime and composite numbers can be found. That is, numbers in value should not exceed a . That is, the number a must be decomposed into prime factors. if this is true, then the number a can be considered prime.
Example 2
Determine the composite or prime number 11723.
Solution
Now you need to find all divisors for the number 11723. Need to evaluate 11723 .
From here we see that 11723< 200 , то 200 2 = 40 000 , and 11 723< 40 000 . Получаем, что делители для 11 723 меньше числа 200 .
For a more accurate estimate of the number 11723, it is necessary to write the expression 108 2 = 11 664, and 109 2 = 11 881 , then 108 2 < 11 723 < 109 2 . It follows from this that 11723< 109 . Видно, что любое число, которое меньше 109 считается делителем для заданного числа.
When decomposing, we get that 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 are all prime numbers. This whole process can be depicted as a division by a column. That is, divide 11723 by 19. The number 19 is one of its factors, since we get division without a remainder. Let's depict the division by a column:
It follows that 11723 is a composite number, because in addition to itself and 1 it has a divisor 19 .
Answer: 11723 is a composite number.
If you notice a mistake in the text, please highlight it and press Ctrl+Enter
