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.
Learn about the pitfalls of Fermat's Little Theorem. All numbers for which the test conditions are not met are composite, but the remaining numbers are only likely are classified as simple. If you want to avoid incorrect results, look for n in the list of "Carmichael numbers" (composite numbers that satisfy this test) and "pseudo-prime Fermat numbers" (these numbers meet the test conditions only for some values a).
If convenient, use the Miller-Rabin test. Although this method is quite cumbersome to calculate by hand, it is often used in computer programs. It provides acceptable speed and produces fewer errors than Fermat's method. A composite number will not be accepted as a prime number if calculations are made for more than ¼ of the values a. If you randomly select different values a and for all of them the test will give a positive result, we can assume with a fairly high degree of confidence that n is a prime number.
For large numbers, use modular arithmetic. If you don't have a calculator with mod on hand, or your calculator isn't designed to handle such large numbers, use the properties of powers and modular arithmetic to make calculations easier. Below is an example for 3 50 (\displaystyle 3^(50)) mod 50:
- Rewrite the expression in a more convenient form: mod 50. When doing manual calculations, further simplifications may be necessary.
- (3 25 ∗ 3 25) (\displaystyle (3^(25)*3^(25))) mod 50 = mod 50 mod 50) mod 50. Here we took into account the property of modular multiplication.
- 3 25 (\displaystyle 3^(25)) mod 50 = 43.
- (3 25 (\displaystyle (3^(25)) mod 50 ∗ 3 25 (\displaystyle *3^(25)) mod 50) mod 50 = (43 ∗ 43) (\displaystyle (43*43)) mod 50.
- = 1849 (\displaystyle =1849) mod 50.
- = 49 (\displaystyle =49).
The article discusses the concepts of prime and composite numbers. Definitions of such numbers are given with examples. We provide 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 is inconvenient and time-consuming. It is possible to create 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 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 the arithmetic root of the 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 factorized 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. This entire process can be depicted as 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:
It follows that 11723 is a composite number, because in addition to itself and 1 it has a divisor of 19.
Answer: 11723 is a composite number.
If you notice an error in the text, please highlight it and press Ctrl+Enter
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.
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 proposition 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 …
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 we know 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 as belonging to 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.
