Definition 1. Prime number− it natural number greater than one that is only divisible by itself and 1.

In other words, a number is prime if it has only two distinct natural divisors.

Definition 2. Any natural number that has other divisors besides itself and one is called composite number.

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

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

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

Prime number table

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

Really. If a p prime number, then it is only divisible by itself and 1 if a not divisible by p, then the largest common divisor a and p equals 1. Then p and a mutually prime numbers.

Statement 2. If the product of several numbers of numbers a 1 , a 2 , a 3 , ... is divisible by a prime number p, then at least one of the numbers a 1 , a 2 , a 3 , ... is divisible by p.

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

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

Proof. Let be k composite number, and let a 1 is one of its divisors different from 1 and itself. If a a 1 is composite, then it has in addition to 1 and a 1 and another divider a 2. If a a 2 is a composite number, then it has, in addition to 1 and a 2 and another divider a 3 . Arguing in this way and taking into account that the numbers a 1 , a 2 , a 3 , ... decrease and this series contains a finite number of terms, we will reach some prime number p one . Then k can be represented as

Suppose there are two expansions of a number k:

As k=p 1 p 2 p 3 ... is divisible by a prime number q 1 , then at least one of the factors, for example p 1 is divisible by q one . But p 1 is prime and is only divisible by 1 and itself. Hence p 1 =q 1 (because q 1 ≠1)

Then from (2) we can exclude p 1 and q 1:

Thus, we make sure that any prime number that enters the first expansion as a factor one or more times enters the second expansion at least the same number of times and vice versa, any prime number that enters the second expansion as a factor one or several times also enters the first expansion at least as many times. Therefore, any prime number enters as a factor in both expansions the same number of times and, thus, these two expansions are the same.■

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

(3)

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

Decomposition (3) is called canonical decomposition numbers.

Prime numbers in the series of natural numbers occur unevenly. In some parts of the series there are more of them, in others - less. The further we move along the number series, the rarer the prime numbers. The question is, is there a largest prime number? The ancient Greek mathematician Euclid proved that there are infinitely many prime numbers. We present this proof below.

Theorem 2. The number of prime numbers is infinite.

Proof. Suppose there are a finite number of primes, and let the largest prime be p. Let's consider all the numbers p. By the assumption of the statement, these numbers must be composite and must be divisible by at least one of the prime numbers. Let's choose a number that is the product of all these primes plus 1:

Number z more p as 2p already more p. p is not divisible by any of these prime numbers, since when divided by each of them, it gives a remainder of 1. Thus we arrive at a contradiction. Therefore, there are an infinite number of prime numbers.

This theorem is a special case of a more general theorem:

Theorem 3. Let an arithmetic progression be given

Then any prime number in n, should also be included in m, so in n cannot include other prime factors that are not included in m and, moreover, these prime factors in n appear no more times than in m.

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

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

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

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.

Home distinctive feature 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 that it is necessary to prove or disprove that every even number greater than two can be represented as the sum of two prime numbers, and every odd number greater than 5 can be represented as the sum three simple 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.

Since the time of the ancient Greeks, prime numbers have been very attractive to mathematicians. They are constantly looking different ways their location, but most effective way“Catching” prime numbers is considered to be the method found by the Alexandrian astronomer and mathematician Eratosthenes. This method is already about 2000 years old.

What numbers are prime

How to define a prime number? Many numbers are evenly divisible by other numbers. The number by which an integer is divisible is called the divisor.

In this case, we are talking about division without a remainder. For example, the number 36 can be divided by 1, 2, 3, 4, 6, 9, 12, 18 and by itself, that is, by 36. So 36 has 9 divisors. The number 23 is divisible only by itself and by 1, that is, this number has 2 divisors - this number is prime.

Numbers that have only two divisors are called prime numbers. That is, a number that is divisible without a remainder only by itself and by one is called a prime number.

For mathematicians, the discovery of patterns in a series of numbers, which can then be used to build hypotheses, is a very pleasant event. But prime numbers refuse to obey any pattern. But there is a way to define prime numbers. This method was found by Eratosthenes, it is called the "sieve of Eratosthenes." Let's look at a variant of such a "sieve", presented in the form of a table of numbers up to 48, and understand how it is compiled.

In this table, all prime numbers less than 48 are marked orange. They are found like this:

• 1 - has a single divisor and therefore is not a prime number;
• 2 is the smallest prime number and the only even one, since all other even numbers are divisible by 2, that is, they have at least 3 divisors, these numbers are reduced to purple column;
• 3 is a prime number, has two divisors, all other numbers that are divisible by 3 are excluded - these numbers are summarized in the yellow column. The column marked in both purple and yellow contains numbers divisible by both 2 and 3;
• 5 is a prime number, all numbers that are divisible by 5 are excluded - these numbers are surrounded by a green oval;
• 7 is a prime number, all numbers that are divisible by 7 are circled in red - they are not prime;

All non-prime numbers are marked in blue. Further, this table can be compiled in the image and likeness.

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.

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 prime numbers. Moreover, initially 1 was taken into account as a prime number, and we see this: 2 = 1 + 1. This is smallest example, which satisfies the original formulation of the hypothesis. Later it was corrected, and the wording acquired 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.