Reciprocal prime numbers. Coprime numbers
Definition1. Integers a 1,a 2,…,a k are called co-prime if (a 1 ,a 2 ,…,a k) =1
Definition 2. Integers a 1,a 2,…,a k are called pairwise coprime if i,s (i, s = 1, 2, .. , k, is, (a i, a s) =1) .
If the numbers satisfy Definition 2, then they satisfy Definition 1. The converse statement is generally false, for example: (15, 21, 19) = 1, but (15, 21) = 3
Theorem (co-prime criterion)
(a, b) = 1<=> x, y Z: ax + by = 1
Proof:
Let's prove the necessity. Let (a, 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 Euclidean algorithm): 1 = ax + bу.
Adequacy. Let (*) ax + by = 1, let us prove that (a, b) = 1. Suppose that (a, b) = d, then on the left side of equality (*)
(a / d ) & ( b/d ) => (ah + by) /d => (1/d) => (d=l) => (a, b) = 1.
§4. Nok of integers and its properties.
Definition 1. The common multiple of a finite set of integers a 1,a 2,…,a k, different from zero, is an integer m that is divisible by all numbers a i (i=l, 2,…, k)
Definition 2. An integer (m) is called the least common multiple of the numbers a 1, a 2,...,a k, different from zero, if:
1 m - is their common multiple;
2 (m) divides any other common multiple of these numbers.
Designation: 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 the numbers 2, 3, 4, 6, 12. The least common multiple is the number 12. i.e.
The LCM is determined uniquely up to the order of the factors. Indeed, if we assume that m 1 = [a, b] &m 2 = (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) (derive it yourself)
This connection allows us to state that for any pair of integers other than zero, there is their least common multiple. Indeed, (a, b) can always be unambiguously deduced from the Euclidean algorithm and by definition (a, b) 0, then the fraction ab/(a, b) 0 will be uniquely determined.
The LCM of two integers is most easily calculated in the case 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 does not have a positive number. 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 are 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 coprime; 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)/р, 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 non-1 divisor of an integer a>1 is a prime number. Proof. Let aZ and a be a composite number (if a = p, then the statement is proven), then a = a 1 q. Let q be the smallest divisor, let us show that it will be a prime number. If we assume that q is a composite number, then q = q 1 k and a = 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
. From this statement it follows that if a natural number (n) is not divisible by any prime number p n, then n is prime, otherwise it will be composite. Example 1. Find out if 137 is a prime number? 11<137
<12. We write down prime factors not exceeding 137: 2, 3, 5, 7, 11. We check that 137 is not divisible by 2, 3, 5, 7, 11. Therefore, the number 137 is prime. Euclid's theorem. The set of prime numbers is infinite. Proof. Let us assume the opposite, 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, because p i , then it must be composite, then its smallest divisor will be prime (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. Therefore, our assumption that the set of prime numbers is finite was incorrect. However, there is a theorem that states that prime numbers make up only a small part of the natural numbers. 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 create a sequence of natural numbers (n+1)!+2, n+1)!+3,…,(n+1)!+(n+1). In this sequence, each subsequent number is 1 greater 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 indicate 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 in a unique way 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 proven. 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 in a similar way. If n 1 is a prime number, then the theorem is proven, 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: Let's assume 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 another (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. Consequently, in both expansions the number of factors is the same (k=n) and the factors themselves are the same. Comment. When decomposing a number (n) into simple factors, some of them may be repeated. Denoting by the 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 Corollary 1. If Example 3. All divisors of the number 720 = 2 4 3 2 5 are obtained if in the expression The required divisors will be equal to: 1; 2; 4; 8; 16; 3; 6; 12; 24; 48; 9; 18; 36; 72; 144; 5; 10; 20; 40; 80; 15; 30; 60; 120; 240; 45; 90; 180; 360; 720. Corollary 2. If 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 expansion if (24,
42) = 23
= 6 The information in this article covers the topic " coprime numbers" First, the definition of two coprime numbers is given, as well as the definition of three or more coprime numbers. After this, examples of coprime numbers are given, and it is shown how to prove that given numbers are coprime. The following lists and proves the basic properties of coprime numbers. Finally, pairwise prime numbers are mentioned because they are closely related to coprime numbers. Page navigation. There are often tasks in which you need to prove that given integers are relatively prime. The proof boils down to calculating the greatest common divisor of the given numbers and checking the gcd to see if it is equal to one. It is also useful to look at the table of prime numbers before calculating the gcd: what if the original integers are prime, and we know that the largest common divisor prime numbers is equal to one. Let's look at the example solution. Example. Prove that the numbers 84 and 275 are relatively prime. Solution. Obviously, these numbers are not prime, so we cannot immediately talk about the relative prime of the numbers 84 and 275, and we will have to calculate the gcd. We use the Euclidean algorithm to find GCD: 275=84·3+23, 84=23·3+15, 23=15·1+8, 15=8·1+7, 8=7·1+1, 7=7 ·1, therefore, gcd(84, 275)=1. This proves that the numbers 84 and 275 are relatively prime. The definition of coprime numbers can be extended to three and more numbers. Definition. Integers a 1 , a 2 , …, a k , k>2 are called mutually prime, if the greatest common divisor of these numbers is equal to one. From the stated definition it follows that if a certain set of integers has a positive common divisor other than one, then these integers are not coprime. Let's give examples. Three integers −99, 17 and −27 are relatively prime. Any collection of prime numbers constitutes a set of coprime numbers, for example, 2, 3, 11, 19, 151, 293 and 677 are coprime numbers. And the four numbers 12, −9, 900 and −72 are not coprime because they have a positive common divisor 3 other than 1. The numbers 17, 85 and 187 are also not relatively prime, since each of them is divisible by 17. It is usually far from obvious that some numbers are relatively prime, and this fact has to be proven. To find out whether given numbers are coprime, you have to find the greatest common divisor of these numbers and draw a conclusion based on the definition of coprime numbers. Example. Are the numbers 331, 463 and 733 relatively prime? Solution. Looking at the table of prime numbers, we will find that each of the numbers 331, 463 and 733 is prime. Therefore, they have a single positive common divisor - one. Thus, the three numbers 331, 463 and 733 are relatively prime numbers. Answer: Yes. Example. Prove that the numbers −14 , 105 , −2 107 and −91 are not coprime. Solution. To prove that these numbers are not relatively prime, you can find their gcd and make sure that it is not equal to one. That's what we'll do. Since integer divisors negative numbers coincide with the divisors of the corresponding , then GCD(−14, 105, 2 107, −91)= GCD(14, 105, 2 107, 91) . Turning to the material in the article finding the greatest common divisor of three or more numbers, we find out that GCD(14, 105, 2 107, 91) = 7. Therefore, the greatest common divisor of the original numbers is seven, so these numbers are not coprime. Coprime numbers have a number of properties. Let's look at the main properties of coprime numbers. The numbers obtained by dividing the integers a and b by their greatest common divisor are coprime, that is, a:GCD(a, b) and b:GCD(a, b) are coprime. We proved this property when we examined the properties of GCD. The considered property of coprime numbers allows us to find pairs of coprime numbers. To do this, it is enough to take any two integers and divide them by the greatest common divisor, the resulting numbers will be relatively prime. In order for the integers a and b to be relatively prime, it is necessary and sufficient that there exist integers u 0 and v 0 such that a·u 0 +b·v 0 =1. Let us first prove the necessity. Let the numbers a and b be relatively prime. Then, by the definition of coprime numbers, GCD(a, b)=1. And from the properties of GCD we know that for integers a and b the Bezout relation a·u 0 +b·v 0 =GCD(a, b) is true. Therefore, a·u 0 +b·v 0 =1. It remains to prove the sufficiency. Let the equality a·u 0 +b·v 0 =1 be true. Since GCD(a, b) divides both a and b, then GCD(a, b), due to the properties of divisibility, must divide the sum a·u 0 +b·v 0, and therefore unity. And this is only possible when GCD(a, b)=1. Therefore, a and b are relatively prime numbers. The next property of coprime numbers is this: if numbers a and b are coprime, and the product a·c is divisible by b, then c is divisible by b. Indeed, since a and b are relatively prime, then from the previous property we have the equality a·u 0 +b·v 0 =1. Multiplying both sides of this equality by c, we have a·c·u 0 +b·c·v 0 =c. The first term of the sum a·c·u 0 +b·c·v 0 is divided by b, since a·c is divided by b according to the condition, the second term of this sum is also divided by b, since one of the factors is equal to b, therefore, the entire sum is divided by b. And since the sum a·c·u 0 +b·c·v 0 is equal to c, then c is divisible by b. If numbers a and b are coprime, then gcd(a c, b) = gcd(c, b) . Let us show, firstly, that gcd(a c, b) divides gcd(c, b), and secondly, that gcd(c, b) divides gcd(a c, b), this will prove the equality GCD(a c, b)=GCD(c, b) . GCD(a c, b) divides both a c and b, and since gcd(a c, b) divides b, it also divides b c. That is, gcd(a c, b) divides both a c and b c, therefore, due to the properties of the greatest common divisor, it also divides gcd(a c, b c), which, according to the properties of gcd, is equal to c GCD(a, b)=c . Thus, gcd(a c, b) divides both b and c, therefore, divides gcd(c, b) as well. On the other hand, GCD(c, b) divides both c and b, and since it divides c, it also divides a·c. Thus, gcd(c, b) divides both a c and b, therefore, it also divides gcd(a c, b). So we showed that gcd(a c, b) and gcd(c, b) mutually divide each other, which means they are equal. If each of the numbers a 1 , a 2 , …, a k is coprime with each of the numbers b 1 , b 2 , …, b m (where k and m are some natural numbers), then the products a 1 · a 2 · … · a k and b 1 · b 2 ·…·b m are coprime numbers, in particular, if a 1 =a 2 =…=a k =a and b 1 =b 2 =…=b m =b, then a k and b m are coprime numbers. The previous property of coprime numbers allows us to write a series of equalities of the form GCD(a 1 · a 2 ·…·a k , b m)= GCD(a 2 ·…·a k , b m)=…=GCD(a k , b m)=1, where the last transition is possible, since a k and b m are mutually prime numbers by condition. So, GCD(a 1 · a 2 ·…·a k , b m)=1. Now, denoting a 1 ·a 2 ·…·a k =A, we have This concludes our review of the basic properties of coprime numbers. Through coprime numbers it is given identifying pairs of prime numbers. Definition. Integers a 1, a 2, …, a k, each of which is relatively prime to all the others, are called pairwise prime numbers.
Let's give an example of pairwise prime numbers. The numbers 14, 9, 17, and −25 are pairwise prime, since the pairs of numbers 14 and 9, 14 and 17, 14 and −25, 9 and 17, 9 and −25, 17 and −25 are coprime numbers. Here we note that pairwise prime numbers are always coprime. On the other hand, relatively prime numbers are not always pairwise prime, as the following example confirms. The numbers 8, 16, 5 and 15 are not pairwise prime, since the numbers 8 and 16 are not coprime. However, the numbers 8, 16, 5 and 15 are relatively prime. Thus, 8, 16, 5 and 15 are relatively prime numbers, but not pairwise prime. We should especially highlight the collection of a certain number of prime numbers. These numbers are always both relatively prime and pairwise prime. For example, 71, 443, 857, 991 are both pairwise prime and coprime numbers. It is also clear that when we're talking about about two integers, then for them the concepts of “pairwise prime” and “mutually prime” coincide. References. What are coprime numbers? Definition of coprime numbers: Coprime numbers are integers that have no common factors other than one. Example of coprime numbers: 2 and 3 have no other common factors other than one. Another example of coprime numbers: 3 and 7 have no other common factors other than one. Another example of coprime numbers: 11 and 13 have no other common factors other than one. Now we can answer the question of what coprime numbers mean. What does coprime numbers mean? These are integers that have no common divisors other than one. Each of these pairs is two relatively prime numbers. 11 and 15 The common divisors of coprime numbers are only one, as follows from the definition of coprime numbers. The greatest common divisor of coprime numbers is one, as follows from the definition of coprime numbers. Are the numbers 3 and 13 coprime? Yes, because they have no common divisors except one. Are the numbers 3 and 12 coprime? No, because their common divisors are 1 and 3. And by the definition of coprime numbers, the common divisor should only be one. Are the numbers 3 and 108 coprime? No, because their common divisors are 1 and 3. And by the definition of coprime numbers, the common divisor should only be one. Are the numbers 108 and 5 coprime? Yes, because they have no common divisors except one. $p$ is called a prime number if it has only $2$ divisors: $1$ and itself. Divider natural number$a$ is the natural number by which the original number $a$ is divisible without leaving a 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 the 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$. This means that in order to find the divisors of a number, you need to find all the natural numbers into which the given number is divisible without a remainder. It is easy to see that the number $1$ will be a divisor of any natural number. Definition 2 Composite They call a number that has other divisors besides one and itself. An example of a prime number would be the number $13$, an example of a composite number would be $14.$ Note 1 The number $1$ has only one divisor - the number itself, so it is neither prime nor composite. Definition 3 Mutually prime numbers they are those whose gcd is equal to $1$. This means that to find out whether the numbers are relatively prime, you need to find their gcd and compare it with $1$. Definition 4 If in a set of numbers any two are coprime, then such numbers are called pairwise coprime. For two numbers, the concepts “coprime” and “pairwise coprime” coincide. Example 2 $8, $15 - not simple, but relatively simple. $6, 8, 9$ are coprime numbers, but not pairwise coprime numbers. $8, 15, 49$ are pairwise relatively prime. As we see, in order to determine whether numbers are relatively prime, we must first factor them into prime factors. Let's pay attention to how to do this correctly. For example, let’s factorize the number $180$ into prime factors: $180=2\cdot 2\cdot 3\cdot 3\cdot 5$ Let us use the property of powers, then we get, $180=2^2\cdot 3^2\cdot 5$ This notation of decomposition into prime factors is called canonical, i.e. in order to factor a number in canonical form, it is necessary to use the property of powers and represent the number as a product of powers with for different reasons Canonical expansion of a natural number in general view has the form: $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 prime 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 greatest common divisor of the numbers $180$ and $240$. Solution: Let's decompose numbers into simple sets using 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 powers 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 canonical factorization into prime factors. To find the greatest common divisor of two numbers using canonical expansion, you need to: 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 relatively prime. We also see that each of the numbers includes factors, in addition to $1$ and the number itself, which means the numbers will not be prime, but will be composite. Example 5 Determine whether the numbers $39$ and $112$ are prime, coprime numbers. Solution: Let's use the canonical 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 the numbers are relatively prime. We also see that each of the numbers includes factors, in addition to $1$ and the number itself, which means the numbers will not be prime, but will be composite. Example 6 Determine whether the numbers $883$ and $997$ are prime, coprime numbers. Solution: Let's use the canonical 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 the numbers are relatively prime. We also see that each number includes only factors equal to $1$ and the number itself, which means the numbers will be prime.
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 following 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)
Properties of coprime numbers
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 m , A)=… =GCD(b m , A)=1
(the last transition is valid, due to the last equality from the previous paragraph). This is how we got equality GCD(b 1 ·b 2 ·…·b m , a 1 ·a 2 ·…·a k)=1, which proves that the products a 1 ·a 2 ·…·a k and b 1 ·b 2 ·…·b m are coprime numbers.Pairwise prime numbers - definitions and examples
Coprime numbers definition
Coprime numbers examples
Two coprime numbers
15 and 16
16 and 23Common divisors of coprime numbers
Greatest common divisor of coprime numbers
Are numbers coprime?
Coprime numbers
Pairwise coprime
Prime factorization
Canonical expansion of a natural number in general form
Related articles
The best amulets against the evil eye and damage Amulet against the evil eye with hands for children
How to read the Psalter correctly
Delicious dishes with sausages
A glimpse of Bella. Romantic chronicle. A glimpse of genius. Messerer about Akhmadulina Boris Messerer glimpse of Bella romantic chronicle
I dreamed that I was sailing on a boat on the river
How to cook beef entrecote in a frying pan
About the company Foreign language courses at Moscow State University
Which city and why became the main one in Ancient Mesopotamia?
Why Bukhsoft Online is better than a regular accounting program!
Which year is a leap year and how to calculate it