If you adhere to proper nutrition, then avocados are probably in ...
$p$ is called a prime number if it has only $2$ divisors: $1$ and itself.
The divisor of a natural number $a$ is a natural number by which the original number $a$ is divisible without remainder.
Example 1
Find the divisors of the number $6$.
Solution: We need to find all the numbers by which the given number $6$ is divisible without a remainder. These will be numbers: $1,2,3, 6$. So the divisor of the number $6$ will be the numbers $1,2,3,6.$
Answer: $1,2,3,6$.
So, in order to find the divisors of a number, you need to find all integers into which the given is divisible without remainder. It is easy to see that the number $1$ will be a divisor of any natural number.
Definition 2
Composite A number is called a number that has other divisors besides one and itself.
An example of a prime number would be $13$, an example of a composite number would be $14.$
Remark 1
The number $1$ has only one divisor - this number itself, so it is not classified as either prime or composite.
Coprime numbers
Definition 3
Coprime numbers those whose GCD is equal to $1$ are called. So, to find out whether the numbers are coprime, it is necessary to find their GCD and compare it with $1$.
Pairwise coprime
Definition 4
If in a set of numbers any two are coprime, then such numbers are called pairwise coprime. For two numbers, the concepts of "coprime" and "pairwise coprime" are the same.
Example 2
$8, 15$ - not prime, but coprime.
$6, 8, 9$ - mutually prime numbers, but not pairwise coprime.
$8, 15, 49$ are pairwise coprime.
As we can see, in order to determine whether the numbers are coprime, you must first decompose them into prime factors. Let's pay attention to how to do it right.
Prime factorization
For example, let's factorize the number $180$:
$180=2\cdot 2\cdot 3\cdot 3\cdot 5$
We use the property of degrees, then we get,
$180=2^2\cdot 3^2\cdot 5$
Such a representation of the decomposition into prime factors is called canonical, i.e. in order to factorize a number in canonical form, it is necessary to use the power property and represent the number as a product of powers with different grounds
Canonical decomposition of a natural number in general form
Canonical decomposition of a natural number in general view looks like:
$m=p^(n1)_1\cdot p^(n2)_2\cdot \dots \dots ..\cdot p^(nk)_k$
where $p_1,p_2\dots \dots .p_k$ are prime numbers and exponents are natural numbers.
Representing a number as a canonical decomposition into simple sets makes it easier to find the greatest common divisor of numbers, and acts as a consequence of the proof or definition of coprime numbers.
Example 3
Find the largest common divisor numbers $180$ and $240$.
Solution: Decompose the numbers into simple sets using the canonical decomposition
$180=2\cdot 2\cdot 3\cdot 3\cdot 5$, then $180=2^2\cdot 3^2\cdot 5$
$240=2\cdot 2\cdot 2\cdot 2\cdot 3\cdot 5$, then $240=2^4\cdot 3\cdot 5$
Now let's find the gcd of these numbers, for this we choose the degrees with the same base and with the smallest exponent, then
$gcd \ (180;240)= 2^2\cdot 3\cdot 5=60$
Let's compose algorithm for finding gcd taking into account the canonical decomposition into prime factors.
To find the greatest common divisor of two numbers using the canonical expansion, you must:
- factorize numbers into prime factors in canonical form
- choose degrees with the same base and with the smallest exponent of the expansion of these numbers
- Find the product of the numbers found in step 2. The resulting number will be the desired greatest common divisor.
Example 4
Determine whether the numbers $195$ and $336$ are prime, coprime numbers.
$195=3\cdot 5\cdot 13$
$336=2\cdot 2\cdot 2\cdot 2\cdot 3\cdot 7=2^4\cdot 3\cdot 5$
$gcd \ (195;336) =3\cdot 5=15$
We see that the gcd of these numbers is different from $1$, which means the numbers are not coprime. We also see that each of the numbers includes factors, in addition to $1$ and the number itself, which means that the numbers will not be prime either, but will be composite.
Example 5
Determine whether the numbers $39$ and $112$ are prime, coprime numbers.
Solution: We use the canonical factorization for factorization:
$112=2\cdot 2\cdot 2\cdot 2\cdot 7=2^4\cdot 7$
$gcd \ (39;112)=1$
We see that the gcd of these numbers is equal to $1$, which means that the numbers are coprime. We also see that each of the numbers includes factors, in addition to $1$ and the number itself, which means that the numbers will not be prime either, but will be composite.
Example 6
Determine whether the numbers $883$ and $997$ are prime, coprime numbers.
Solution: We use the canonical factorization for factorization:
$883=1\cdot 883$
$997=1\cdot 997$
$gcd \ (883;997)=1$
We see that the gcd of these numbers is equal to $1$, which means that the numbers are coprime. We also see that each of the numbers includes only factors equal to $1$ and the number itself, which means the numbers will be prime.
Definition1. Integers a 1 ,a 2 ,…,a k are called coprime if (a 1 ,a 2 ,…,a k) =1
Definition 2. Integers а 1 ,а 2 ,…,ak are pairwise coprime if i,s (i, s = 1, 2, .. , k, is, (а i , а s) =1) .
If the numbers satisfy definition 2, then they also satisfy Definition 1. The converse is not true in the general case, for example: (15, 21, 19)= 1, but (15, 21) = 3
Theorem (mutual primality criterion)
(a, b) = 1<=> x, y Z: ax + by = 1
Proof:
Let's prove the necessity. Let (а, b) = 1. Above we showed that if d=(a, b), then x, y Z: d = ax + by.
Because in this case d =1, then there will be x, y Z (determined from the Euclid algorithm): 1 = ax + bу.
Adequacy. Let (*) ax + by = 1, we prove that (a, b)=1. Suppose that (a, b) = d, then on the left side of the equality (*)
(a / d ) & ( b/d ) => (ax + by) /d => (1/d) => (d=l) => (a, b) = 1.
§four. Nok of integers and its properties.
Definition 1. A common multiple of a finite set of integers a 1 ,a 2 ,…,a k , other than zero, is an integer m, which is divisible by all numbers a i (i=l, 2,…, k)
Definition 2. An integer (m) is called the least common multiple of non-zero numbers а 1 ,а 2 ,…,a k , if:
1 m - is their common multiple;
2 (m) divides any other common multiple of these numbers.
Notation: m = LCM (a 1, a 2,…, a k) or m = [a 1, a 2,…, a k]
Example. Given numbers: 2, 3, 4, 6, 12.
The numbers 12, 24. 48. 96 are common multiples of 2, 3, 4, 6, 12. The least common multiple is 12. i.e.
The LCM is uniquely determined up to the order of the factors. Indeed, if we assume that m 1 \u003d [a, b] &m 2 \u003d (m 1 / m 2) & (m 2 / m 1) => [(m 1 = m 2) v (m 1 = - m 2)]. There is a relationship between the least common multiple and the greatest common divisor of two integers, which is expressed by the formula: [a, b] = ab / (a, b) (deduce it yourself)
This relationship allows us to assert that for any pair of non-zero integers, there is their least common multiple. Indeed, (a, b) can always be uniquely derived from Euclid's algorithm and by definition (a, b) 0, then the fraction ab/(a, b) 0 will be uniquely determined.
The simplest LCM of two integers is calculated when (a, b) = 1, then [a, b] = ab/1 = a b
For example, = 215/1 = 105, because (21, 5) = 1.
§5. Prime numbers and their properties.
Definition 1. A natural number (p) is called prime if p > 1 and has no posit. divisors other than 1 and p.
Definition 2. A natural number a > 1 that has other positive divisors besides 1 and itself is called composite.
From these definitions it follows that the set of natural numbers can be divided into three classes:
a) composite numbers;
b) prime numbers;
c) unit.
If a is composite, then a = nq, where 1 Task 1. Prove that if aZ and p is a prime number, then (a, p) = 1 v (a / p) Proof. Let d = (a, p) =>
(a / d) & (p / d), because p is a prime number, then it has two divisors 1 and p. If (a, p) = 1, then a and p are relatively prime; if (a, p) = p, then (a/p). Task 2. If the product of several factors is divisible by p, then at least one of the factors is divisible by p. Solution. Let the product (a 1, a 2, ...,
and k)/p, if all a i are not divisible by p, then the product will be coprime with p, therefore, some factor is divisible by p. Task 3. Prove that the smallest divisor of an integer a > 1 other than 1 is a prime number. Proof. Let aZ and a be a composite number (if a = p, then the assertion is proved), then a = a 1 q. Let q be the smallest divisor, let's show that it will be a prime number. If we assume that q is a composite number, then q \u003d q 1 k and a \u003d a 1 q 1 k, because q 1 Task 4. Prove that the smallest prime divisor (p) of a natural number (n) does not exceed n . Proof. Let n = pn 1 , and p< n 1
и р - простое. Тогда n
р 2
=>R<n
. It follows from this statement that if a natural number (n) is not divisible by any prime number р n , then n is prime, otherwise it will be composite. Example 1. Find out if the number 137 is prime? eleven<137
<12. We write down prime divisors not exceeding 137: 2, 3, 5, 7, 11. We check that 137 is not divisible by 2, by 3, by 5, by 7, by 11. Therefore, the number 137 is prime. Euclid's theorem. The set of prime numbers is infinite. Proof. Assume the contrary, let p 1 ,p 2 , ...,
p k are all prime numbers, where p 1 = 2 and p k is the largest prime number. Let's compose a natural number = p 1 p 2 ...
p to +1, as p i , then it must be composite, then its smallest divisor will be simple (see problem 3). However, is not divisible by either p 1 or p 2 ,…, or p k , because 1 is not divisible by any p I . Consequently, our assumption that the set of primes is finite was wrong. However, there is a theorem that states that prime numbers make up only a small part of the numbers in the natural series. The interval theorem. In the natural series, there are arbitrarily long intervals that do not contain a single prime number. Proof. Let's take an arbitrary natural number (n) and compose a sequence of natural numbers (n+1)!+2, n+1)!+3,…,(n+1)!+(n+1). In this sequence, each subsequent number is 1 more than the previous one, all these numbers are composite, because each has more than two divisors (for example, the first number is divisible by 1, by 2, and by itself). As n→∞ we get an arbitrarily long interval consisting only of composite numbers. Euclid's theorem and the interval theorem testify to the complex nature of the distribution of prime numbers in the natural series. Fundamental theorem of arithmetic Any natural number n>1 can be represented uniquely as a product of prime numbers, up to the order of the factors. Proof. Let us prove the possibility of representation: Let nN and n>1, if n is a prime number, then n = p and the theorem is proved. If n is composite, then its smallest divisor will be a prime number and n = p 1 n 1, where n 1 Next, we argue similarly. If n 1 is a prime number, then the theorem is proved, if n 1 is a composite number, then n 1 = p 2 n 2, where n 2< n 1
и тогда n
= p 1 p 2 n 2
. На каком-то шаге получим n
= p 1 p 2
…p n
, где все p i
- простые числа. Let us prove the uniqueness of the decomposition: Suppose that there are two different representations for the number (n): n = p 1 p 2 …p k , n = q 1 q 2 …q n and n>k. Then we get that p 1 p 2 …p k = q 1 q 2 …q n (1). The left side of equality (1) is divisible by p 1 , then by the property of prime numbers (see Problem 2), at least one of the factors on the right side must be divisible by p 1 . Let (q 1 /p 1) => (q 1 =p 1). Dividing both sides of equality (1) by p 1 , we obtain the equality p 2 p 3 …p k = q 2 q 3 …q n . Repeating the previous reasoning more (k-1) times, we get the equality 1 = q k +1 q k +2 …q n , because all q i >1, then this equality is impossible. Therefore, in both expansions the number of factors is the same (k=n) and the factors themselves are the same. Comment. In the decomposition of the number (n) into prime factors, some of them may be repeated. Denoting by letters 1 , 2 ,…, k the multiplicity of their occurrence in (n), we obtain the so-called canonical expansion of the number (n): Example 2 Canonical expansion of the number 588000 = 2 5 35 3 7 2 Consequence 1. If a Example 3 All divisors of the number 720 = 2 4 3 2 5 we get if in the expression The desired divisors will be equal to: 1; 2; four; eight; 16; 3; 6; 12; 24; 48; 9; eighteen; 36; 72; 144; 5; ten; twenty; 40; 80; fifteen; thirty; 60; 120; 240; 45; 90; 180; 360; 720. Consequence 2. If a P 1 1 p 2 2 …p k k , where i = max( I , i). Example 4 Find gcd(a, b) and lcm(a, b) using canonical decomposition if (24,
42) = 23
= 6 In this article, we will talk about what coprime numbers are. In the first paragraph, we formulate definitions for two, three or more coprime numbers, give several examples, and show in which cases two numbers can be considered prime with respect to each other. After that, we turn to the formulation of the main properties and their proofs. In the last section, we'll talk about a related concept, pairwise primes. Yandex.RTB R-A-339285-1 Both two integers and more of them can be coprime. To begin with, we introduce a definition for two numbers, for which we need the concept of their greatest common divisor. If necessary, repeat the material dedicated to him. Definition 1 Two such numbers a and b will be mutually prime, the greatest common divisor of which is equal to 1, i.e. gcd (a , b) = 1 . From this definition, we can conclude that the only positive common divisor of two coprime numbers will be equal to 1. Only two such numbers have two common divisors - one and minus one. What are some examples of relatively prime numbers? For example, such a pair would be 5 and 11 . They have only one common positive divisor, equal to 1, which is a confirmation of their mutual simplicity. If we take two prime numbers, then with respect to each other they will be relatively prime in all cases, but such mutual relations are also formed between composite numbers. There are cases when one number in a pair of coprimes is composite, and the second is prime, or both of them are composite. This statement is illustrated by the following example: the composite numbers - 9 and 8 form a coprime pair. Let's prove it by calculating their greatest common divisor. To do this, we write down all their divisors (we recommend re-reading the article on finding the divisors of a number). For 8, these will be the numbers ± 1, ± 2, ± 4, ± 8, and for 9 - ± 1, ± 3, ± 9. We choose from all divisors the one that will be common and largest - this is one. Therefore, if gcd (8, - 9) = 1, then 8 and - 9 will be coprime with respect to each other. 500 and 45 are not mutually prime numbers, since they have another common divisor - 5 (see the article on signs of divisibility by 5). Five more than one and is a positive number. Another similar pair could be - 201 and 3 , since both of them can be divided by 3 , as indicated by the corresponding divisibility sign. In practice, it is quite common to determine the mutual primeness of two integers. Finding this out can be reduced to finding the greatest common divisor and comparing it to one. It is also convenient to use a table of prime numbers so as not to make unnecessary calculations: if one of the given numbers is in this table, then it is divisible only by one and by itself. Let's take a look at a solution to this problem. Example 1 Condition: find out if the numbers 275 and 84 are coprime. Solution
Both numbers clearly have more than one divisor, so we cannot immediately call them coprime. Calculate the greatest common divisor using Euclid's algorithm: 275 = 84 3 + 23 , 84 = 23 3 + 15 , 23 = 15 1 + 8 , 15 = 8 1 + 7 , 8 = 7 1 + 1 , 7 = 7 1 . Answer: since gcd (84, 275) = 1, then these numbers will be coprime. As we said earlier, the definition of such numbers can be extended to cases where we have not two numbers, but more. Definition 2 Coprime integers a 1 , a 2 , … , a k , k > 2 will be when they have the greatest common divisor equal to 1 . In other words, if we have a set of some numbers with the largest positive divisor greater than 1, then all these numbers are not mutually inverse with respect to each other. Let's take a few examples. So, the integers - 99 , 17 and - 27 are coprime. Any number of primes will be coprime with respect to all members of the population, as in the sequence 2 , 3 , 11 , 19 , 151 , 293 and 667 . But the numbers 12 , − 9 , 900 and − 72
coprime will not be, because in addition to unity they will have one more positive divisor equal to 3. The same applies to the numbers 17, 85 and 187: except for one, they can all be divided by 17. Usually the mutual simplicity of numbers is not obvious at first glance, this fact needs to be proved. To find out if some numbers are coprime, you need to find their greatest common divisor and draw a conclusion based on its comparison with one. Example 2 Condition:
determine if the numbers 331 , 463 and 733 are coprime. Solution
Let's check the table of prime numbers and determine that all three of these numbers are in it. Then their common divisor can only be one. Answer: all these numbers will be relatively prime to each other. Example 3 Condition: give proof that the numbers − 14 , 105 , − 2 107 and − 91 are not coprime. Solution
Let's start by finding their greatest common divisor, after which we make sure that it is not equal to 1 . Since negative numbers the same divisors as the corresponding positive ones, then gcd (− 14 , 105 , 2 107 , − 91) = gcd (14 , 105 , 2 107 , 91) . According to the rules that we gave in the article on finding the greatest common divisor, in this case GCD will be equal to seven. Answer: seven is greater than one, which means that these numbers are not coprime. Such numbers have some practically important properties. We list them in order and prove them. Definition 3 If we divide the integers a and b by the number corresponding to their greatest common divisor, we get relatively prime numbers. In other words, a: gcd(a, b) and b: gcd(a, b) will be coprime. We have already proved this property. The proof can be found in the article on the properties of the greatest common divisor. Thanks to it, we can define pairs of coprime numbers: just take any two integers and divide by gcd. As a result, we should get coprime numbers. Definition 4 Necessary and sufficient condition coprime of numbers a and b is the existence of such integers u 0 and v0, for which the equality a u 0 + b v 0 = 1 will be true. Proof 1 We begin by proving the necessity of this condition. Let's say we have two relatively prime numbers, labeled a and b . Then, by definition of this concept, their greatest common divisor will be equal to one. We know from the properties of gcd that for integers a and b there is a Bezout relation a u 0 + b v 0 = gcd (a, b). From it we get that a u 0 + b v 0 = 1. After that, we need to prove the sufficiency of the condition. Let equality a u 0 + b v 0 = 1 will be true if gcd (a , b) divides and a ,
and b , then it will divide and sum a u 0 + b v 0, and unit, respectively (this can be argued based on the properties of divisibility). And this is only possible if gcd(a, b) = 1, which proves the mutual simplicity of a and b . Indeed, if a and b are coprime, then according to the previous property, the equality will be true a u 0 + b v 0 = 1. We multiply both its parts by c and we get that a c u 0 + b c v 0 = c. We can divide the first term a c u 0 + b c v 0 by b , because it is possible for a c , and the second term is also divisible by b , because one of the factors we have is b . From this we conclude that the whole sum can be divided by b, and since this sum is equal to c, then c can be divided by b. Definition 5 If two integers a and b are coprime, then gcd(a c, b) = gcd(c, b) . Proof 2 Let us prove that gcd (a c , b) will divide gcd (c , b) , and after that - that gcd (c , b) divides gcd (a c , b) , which will prove the validity of the equality gcd (a · c, b) = gcd (c, b) . Since gcd (a c , b) divides both a c and b and gcd (a c , b) divides b , it will also divide b c . Hence, gcd (a c, b) divides both a c and b c, therefore, due to the properties of gcd, it also divides gcd (a c, b c), which will be equal to c gcd (a, b ) = c. Hence gcd(a c, b) divides both b and c, hence gcd(c, b) also divides. You can also say that since gcd (c, b) divides both c and b, then it will divide both c and a c. This means that GCD (c , b) divides both a c and b, therefore, GCD (a c , b) also divides. Thus, gcd (a c, b) and gcd (c, b) mutually divide each other, which means they are equal. Definition 6 If the numbers in the sequence a 1 , a 2 , … , a k will be coprime with respect to the numbers of the sequence b 1 , b 2 , … , b m(for natural values of k and m), then their products a 1 a 2 … a k and b 1 b 2 … b m are also coprime, in particular, a 1 = a 2 = … = a k = a and b 1 = b 2 = ... = b m = b, then a k and b m are coprime. Proof 3 According to the previous property, we can write equalities of the following form: gcd (a 1 a 2 … a k , b m) = gcd (a 2 a k , b m) = … = gcd (a k , b m) = 1 . The possibility of the last transition is ensured by the fact that a k and b m are coprime by assumption. Hence, GCD (a 1 · a 2 · … · a k , b m) = 1 . Denote a 1 a 2 … a k = A and obtain that gcd (b 1 b 2 … b m , a 1 a 2 … a k) = gcd (b 1 b 2 … b m , A) = GCD (b 2 · … · b · b m , A) = … = GCD (b m , A) = 1 . This will be true due to the last equality from the chain constructed above. Thus, we have obtained the equality gcd (b 1 b 2 … b m , a 1 a 2 … a k) = 1 , which can be used to prove the mutual simplicity of the products a 1 a 2 … a k and b 1 b 2 … b m These are all the properties of coprime numbers that we would like to tell you about. Knowing what coprime numbers are, we can formulate the definition of pairwise prime numbers. Definition 7 Pairwise prime numbers is a sequence of integers a 1 , a 2 , … , a k , where each number is coprime with respect to the others. An example of a sequence of pairwise primes would be 14 , 9 , 17 , and − 25 . Here all pairs (14 and 9 , 14 and 17 , 14 and − 25 , 9 and 17 , 9 and − 25 , 17 and − 25) are coprime. Note that the coprime condition is mandatory for pairwise prime numbers, but coprime numbers will not be pairwise prime in all cases. For example, in the sequence 8 , 16 , 5 and 15 the numbers are not so because 8 and 16 will not be coprime. We should also dwell on the concept of a set of a certain number of prime numbers. They will always be both mutually and pairwise simple. An example would be the sequence 71 , 443 , 857 , 991 . In the case of prime numbers, the concepts of mutual and pairwise simplicity will coincide. If you notice a mistake in the text, please highlight it and press Ctrl+Enter Keywords: number theory, lectures, mutually simple numbers. Definition. Integers a and b are called relatively prime if (a , b) = 1. Two numbers a and b are coprime if and only if there are integers u and v such that au + bv = 1. Let X = ( x n | n = 1, 2,...) be an arbitrary strictly increasing sequence of natural numbers (or, if you like, X is an arbitrary subset of natural numbers ordered in a natural way). Denote by ξ(N; X) the number of terms in the sequence X that do not exceed N . Definition. The number is called the (upper asymptotic) density of the sequence X = ( x n | n = 1, 2,...) in the set N . Example 1 Let x n = 2n , where n runs through N , be the sequence of all even numbers. It's obvious that By the way, this is in good agreement with our intuitive ideas that even numbers are half. Example 2 Let x n =2 n , where n runs through N , is a geometric progression. It is intuitively clear that there are few such numbers in the natural series, because the "further into the forest" along the natural series, the less often the power of two occurs. The concept of density confirms this feeling: ξ (2 k ; ( x n )) = k , and it is easy to check that Density is the probability of randomly pulling out from the natural series a number belonging to a given sequence. Similarly to the definition of the density of a sequence, one can define the density of the set of pairs of natural numbers. Let there be an arbitrary set X of ordered pairs of natural numbers. Denote by ξ (N ; X) the number of pairs from the set X, each component of which does not exceed N . It is useful to think of pairs of numbers from the set X as the coordinates of points on the coordinate plane, then ξ (N; X) is simply the number of points in the set X that fall into the square ((x, y) | 0< x ≤ N ; 0 < y ≤ N }. Definition. Number is called the (upper asymptotic) density of the set of pairs X in the set N 2 . Example 3 Let X be the set of all pairs of natural numbers whose first component is strictly greater than the second. The set X corresponds to the points of the first quarter of the coordinate plane, which lie under the bisector y = x. The density of such a set is easy to calculate: Let X be the set of all ordered pairs (u , v) of natural numbers such that (u , v) = 1, i.e. the set of all pairs of coprime numbers. Theorem (Cesaro). The probability of choosing a pair of coprime numbers from N is 6/π 2 , more precisely. Proof. Assume at once that there is a probability p that the randomly chosen natural numbers a and b are coprime. Let d ∈ N . By P ( S ) we denote, as usual, the probability of the event S . Thinking: P Mathematics textbooks are sometimes difficult to read. The dry and clear language of the authors is not always easy to understand. Yes, and the topics there are always interconnected, mutually flowing. To master one topic, you have to raise a number of previous ones, and sometimes leaf through the entire textbook. Difficult? Yes. And let's take the risk of circumventing these difficulties and try to find a non-standard approach to the topic. Let's make a kind of excursion into the country of numbers. However, we will leave the definition the same, because the rules of mathematics cannot be canceled. So, coprime numbers are natural numbers with a common divisor equal to one. This is clear? Quite. For more good example let's take the numbers 6 and 13. Both of them are divisible by one (coprime). But the numbers 12 and 14 cannot be such, since they are divisible not only by 1, but also by 2. The following numbers - 21 and 47 also do not fit into the category of "coprime numbers": they can be divided not only by 1, but also on 7. Coprime numbers are denoted as follows: ( a, y) = 1. It can be said even more simply: the common divisor (largest) here is equal to one. Mutually included in some encryption systems. Those who work with Hill ciphers or with the Caesar substitution system understand that without this knowledge, you can’t get anywhere. If you have heard about generators, then you are unlikely to dare to deny: coprime numbers are used there too. Now let's talk about ways to get such simple ones, as you understand, they can only have two divisors: they are divisible by themselves and by one. Let's say 11, 7, 5, 3 are prime numbers, but 9 is not, because this number is already divisible by 9, 3, and 1. And if a is a prime number, and at- from the set (1, 2, ... a- 1), then it is guaranteed ( a, at) = 1, or coprime numbers — a and at. This is, rather, not even an explanation, but a repetition or summing up of what has just been said. Getting prime numbers is possible, however, for impressive numbers (billions, for example), this method is too long, but, unlike super-formulas, which sometimes make mistakes, it is more reliable. Can work by choosing at > a. To do this, y is chosen so that the number on a did not share. To do this, a prime number is multiplied by a natural number and a value is added (or, conversely, subtracted) (for example, R), which is less a: y= R a + k If, for example, a = 71, R= 3, q=10, then, respectively, at here it will be equal to 713. Another selection is possible, with degrees. Composite numbers, unlike coprime numbers, are divisible by themselves, by 1, and by other numbers (also without a remainder). In other words, (except for one) are divided into composite and simple. Prime numbers are natural numbers that do not have non-trivial divisors (other than the number itself and unity). Their role is especially important in today's, modern, rapidly developing cryptography, thanks to which, previously considered an extremely abstract discipline, it has become so in demand: data protection algorithms are constantly being improved. The largest prime number was found by ophthalmologist Martin Nowak, who participated in the GIMPS (distribution computing) project, along with other enthusiasts, of which there were about 15 thousand. It took six long years to calculate. Two and a half dozen computers located in Novak's eye clinic were involved. The result of titanic work and perseverance was the number 225964951-1, written in 7816230 decimal places. Incidentally, the record a large number was delivered six months before this discovery. And there were half a million fewer signs. A genius who wants to name a number where the duration of the decimal record "jumps" over the ten million mark has a chance to receive not only worldwide fame, but also $ 100,000. By the way, Nayan Khairatwal received a smaller amount ($50,000) for the number that crossed the million mark.
then all divisors of the number (n) have the form: 
where 0 i i (i = 1, 2,…,k).
instead of 1 , 2 , 3 , independently of each other, we will substitute the values: 1 =0, 1, 2, 3, 4, 2 =0, 1, 2, 3 = 0, 1.
and 
then (a, b) = p 1 1 p 2 2 …p k k , where i = min( I , i)
What are coprime numbers
Basic properties of coprime numbers
The concept of pairwise prime numbers
Why do we need such knowledge? Reason enough.
