home » For full » Prime number rules. Non-prime numbers

Prime number rules. Non-prime numbers

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

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

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

The sequence of prime numbers looks like this:

Fundamental Theorem of Arithmetic

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

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

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

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

Properties of Prime Numbers

Sieve of Eratosthenes

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

To find all prime numbers less than a given number, following the method of Eratosthenes, you need to follow these steps:

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

The process of applying the algorithm will look like this:

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

Goldbach conjecture

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

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

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

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

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

The book “Prime numbers. Long road to infinity"

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

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

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

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 wording became modern look: “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.

A prime number is a natural number that is divisible only by itself and one.

The remaining numbers are called composite numbers.

Prime natural numbers

But not all natural numbers are prime numbers.

Prime natural numbers are only those that are divisible only by themselves and one.

Examples of prime numbers:

2; 3; 5; 7; 11; 13;...

Prime Integers

It follows that only natural numbers are prime numbers.

This means that prime numbers are necessarily natural numbers.

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 - the number 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 and by two, that is, such a number will always have three divisors, and possibly more.

All natural numbers, except 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 properties of prime numbers are studied by a special branch 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. At the same time, 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.

This representation of a natural number is called decomposition of a natural number into prime numbers or factorization of a number.

One of the most ancient and effective ways The calculation of prime numbers is the “sieve of Erasstophenes”.

Practice has shown that after calculating prime numbers using the sieve of Erastophenes, it is necessary to check whether given number simple. For this purpose, special tests have been developed, the so-called simplicity tests. The algorithm of these tests is probabilistic. They are most often used in cryptography.

By the way, for some classes of numbers there are specialized effective primality tests. For example, to check the primality of Mersenne numbers, the Luc-Lehmer test is used, and to check the primality 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 proposition is Euclid's proof, which is set out in the Elements. Euclid's proof looks like this:

Let's imagine that the number of prime numbers 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 division by any of them gives one. Thus, the number must be divisible by some prime number not included in this set.

The prime number distribution theorem states that the number of prime numbers less than n, denoted π(n), grows as n / ln(n).

After thousands of years of studying prime numbers, the largest known prime number is 243112609 − 1. This number has 12,978,189 decimal digits and is the Mersenne prime number (M43112609). This discovery was made on August 23, 2008 at the Faculty of Mathematics of uCLA University as part of the distributed search for Mersenne prime numbers project GIMPS.

Home distinctive feature Mersenne numbers is the presence of a highly effective Luc-Lemaire primality test. With its help, the Mersenne primes are, over a long period of time, the largest known primes.

However, to this day, many questions regarding prime numbers have not received precise answers. At the 5th International Congress of Mathematics, Edmund Landau formulated the main problems in the field of prime numbers:

Goldbach's problem or Landau's first problem is that it is necessary to prove or disprove that every even number greater than 2 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 the set " simple twins» - prime numbers whose difference is 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 the infinite number of prime numbers in many integer sequences such as the Fibonacci number, Fermat number, etc.

The article discusses the concepts of prime and composite numbers. Definitions of such numbers are given with examples. We present a proof that the number of prime numbers is unlimited and we will record it in the table of prime numbers using the method of Eratosthenes. Evidence will be given to determine 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 composite. To understand the concept of composite numbers, you must 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 numbers, 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 that is 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. Let's give a 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 only divisible by themselves and 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 is decomposed into 37 and 181. Note that the concepts of prime numbers and coprime 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 numbers reach sizes of 10000 or 1000000000, then you should consider using the Sieve of Eratosthenes.

Let's consider the theorem that explains the last statement.

Theorem 1

The smallest positive divisor other than 1 of a natural number greater than one is a prime number.

Evidence 1

Let us assume that a is a natural number that is greater than 1, b is the smallest non-one divisor of a. It is necessary to prove that b is a prime number using the method of contradiction.

Let's assume that 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 was completed.

From the condition it is clear that a is divided by b, b is divided by b 1, which means that the concept of divisibility is expressed as follows: a = b q and b = b 1 · q 1 , from where 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 for the number a. Inequality 1< b 1 < b Not corresponds, because we find that b is the smallest positive and non-1 divisor of a.

Theorem 2

There are an infinite number of prime numbers.

Evidence 2

Presumably we take a finite number of natural numbers n and denote them as p 1, p 2, …, p n. Let's consider the option of finding a prime number different from those indicated.

Let us take into consideration the number p, which is equal to p 1, p 2, ..., p n + 1. It is not equal to each of the numbers corresponding to prime numbers of the form p 1, p 2, ..., p n. The number p is prime. Then the theorem is considered to be proven. If it is composite, then you need to take the notation p n + 1 and show that the divisor does not coincide 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 find that it would be divisible by pn + 1. Note that the expression p n + 1 dividing the number p equals the sum p 1, p 2, ..., p n + 1. We obtain that the expression p n + 1 The second term of this sum, which equals 1, must be divided, but this is impossible.

It can be seen that any prime number can be found among any number of given prime numbers. It follows that there are infinitely many prime numbers.

Since there are a lot of prime numbers, the tables are limited to the numbers 100, 1000, 10000, and so on.

When compiling a table of prime numbers, you should take into account that such a task requires sequential checking 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 into the table.

Let's look at it step by step.

If you start with the number 2, then it has only 2 divisors: 2 and 1, which means it can be entered into the table. Same with the number 3. The number 4 is composite; it must be decomposed into 2 and 2. The number 5 is prime, which means it can be recorded in the table. Do this until the number 100.

This method inconvenient and long. You can create a table, but you will have to spend a large number 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 look at the tables below as an example. To begin with, the numbers 2, 3, 4, ..., 50 are written down.

Now you need to cross out all the numbers that are multiples of 2. Perform sequential strikethroughs. We get a table like:

We move on to crossing out numbers that are multiples of 5. We get:

Cross out numbers that are multiples of 7, 11. Ultimately the table looks like

Let's move on 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 arithmetic root a given number.

Evidence 3

It is necessary to denote b the smallest divisor of a composite number a. There is an integer q, where a = b · q, and we have that b ≤ q. Inequalities of the form are unacceptable 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.

From the proven theorem it is clear 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 begins with 4, and multiples of 3 with 9, and so on until 100.

Compiling such a table using Eratosthenes' theorem suggests that when all composite numbers are crossed out, prime numbers will remain that do not exceed n. In the example where n = 50, we have that n = 50. From this we get that the sieve of Eratosthenes sifts out all composite numbers whose value is not greater than the value of the root of 50. Searching for numbers is done by crossing out.

Before solving, you need 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 the number 898989898989898989 is composite.

Solution

The sum of the digits of a given number is 9 8 + 9 9 = 9 17. This means that the number 9 · 17 is divisible by 9, based on the divisibility test 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 actions should be taken. The most suitable way is to enumerate numbers. During the process, prime and composite numbers can be found. That is, the numbers should not exceed a in value. That is, the number a must be decomposed into prime factors. if this is satisfied, then the number a can be considered prime.

Example 2

Determine the composite or prime number 11723.

Solution

Now you need to find all the 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, you need to write the expression 108 2 = 11 664, and 109 2 = 11 881 , That 108 2 < 11 723 < 109 2 . It follows that 11723< 109 . Видно, что любое число, которое меньше 109 считается делителем для заданного числа.

When expanding, we find 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. All this 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 represent the division as a column: