Divisibility relation on the set of natural numbers. Divisibility of natural numbers. Divisibility properties. A consistent system of axioms is called independent if none of the axioms of this system is a consequence of other axioms of this system
If the first number is divisible by the second, and the second by the third, then the first number is divisible by the third.
For example, given three numbers 777, 111 and 3. The number 777 is divisible by 111, and 111 is divisible by 3, which means 777 is also divisible by 3:
Divisibility of sum and difference
If each of two given numbers is divisible by a certain number, then their sum and difference are divided by that number.
For example, given two numbers: 27 and 12. The number 27 is divisible by 3, and 12 is divisible by 3. It follows that the sum of 27 and 12 and the difference of 27 and 12 are divisible by 3:
If one of two given numbers is divisible by a certain number, and the other is not divisible by it, then their sum and difference are not divisible by this number.
For example, given two numbers: 64 and 10. The number 64 is divisible by 8, and 10 is not divisible by 8, which means the sum of 64 and 10 and the difference of 64 and 10 are not divisible by 8:
10: 8 = 1 (remainder 2)
74: 8 = 9 (remainder 2)
54: 8 = 6 (remainder 6)
Divisibility of a product
If one of the factors is divisible by a certain number, then the product is also divisible by that number.
For example, given two numbers: 8 and 9. The number 8 is divisible by 4, which means the product of 8 and 9 is divisible by 4.
Let natural numbers be givenaAndb. They say that the numberadivisible by a numberb, if there is such a natural numberq, Whata = bq.
In this case the number b called divisor of a number A, and the number A - multiples of the number b.
For example, 24 is divisible by 8, since there is such a thing q= 3, which is 24 = 8*3. We can say it differently: 8 is a divisor of the number 24, and 24 is a multiple of the number 8.
In case A divided by b, write: . This entry is often read like this: “ A multiple b».
Note that the concept of “divisor of a given number” should be distinguished from the concept of “divisor”, which denotes the number by which it is divided. For example, if 18 is divided by 5, then the number 5 is a divisor, but 5 is not a divisor of the number 18. If 18 is divided by 6, then in the case of the concept of “divisor” and “divisor of a given number” the same.
From the definition of the relation of divisibility and equality A = 1*A, valid for any natural number a, it follows that 1 is divider any natural number.
Let's find out how many divisors a natural number can have. Let's first consider the following theorem.
Theorem. Divider b given number A does not exceed this number. If, then.
Proof. Since, then there is such that a = bq, Means, a-b = bq - b = b*(q- 1). Because , then . Then and therefore .
From this theorem it follows that the set of divisors of a given number is finite. Let's call, for example, all the divisors of the number 36. They form a finite set (1, 2, 3, 4, 6, 9, 12, 18, 36).
Divisibility properties
We know that the divisibility relation on a set N has a number of properties, in particular, it is reflexive, antisymmetric and transitive. Now, having a definition of the divisibility relation, we can prove these and other properties of it.
Theorem. The divisibility relation is reflexive, i.e. any natural number is divisible by itself.
Proof. For any natural A equality is true . Since 1 e N, then, by definition of the divisibility relation, .
Theorem. The divisibility relation is antisymmetric, i.e. If and , then .
Proof. Let's assume the opposite, i.e. that . But then , according to the theorem discussed above.
By condition And . Then, by the same theorem,.
Inequalities will be fair only when , which contradicts the conditions of the theorem. Consequently, our assumption is incorrect and the theorem is proven.
Theorem. The divisibility relation is transitive, i.e. If And , That .
Proof. Because , q, What A= bq, and since , then there is such a natural number p, What . But then we have: . Number pq- natural. This means, by definition of the divisibility relation,.
Theorem(a sign of divisibility of the sum). If each of the natural numbers a1, a2..., up divisible by a natural number b, then their sum a1 + a2 +... + up is divided by this number.
Proof. Because , then there is a natural number such that . Because , then there is such a natural number , What . Continuing the reasoning, we get that if , then there is such a natural number , What . These equalities allow us to transform the sum a1 + a2 +... + up in the amount of type bq1+ bq2+ ... + bqn. Let's put it out of brackets common multiplier b, and the resulting natural number in brackets q1 + q2 +... + qn denoted by the letter q. Then a1+ a2+ ... + up= b(q1+ q2+ ... + qn) = bq, i.e. sum a1+ a2+ ... + up turned out to be represented as a product of the number b and some natural number q. This means that the amount a1+ a2+ ... + up divided by b, Q.E.D.
For example, without making calculations, we can say that the sum 175 + 360 + 915 is divisible by 5, since each term of this sum is divisible by 5.
Theorem(test of the divisibility of the difference). If the numbers a1 And a2 are divided into b and , then their difference is divided by b.
The proof of this theorem is similar to the proof of the divisibility of a sum.
Theorem(a sign of the divisibility of a work). If the number A divided by b, then a product of the form Oh, Where xÎ N, divisible by b.
Proof. Because , then there is such a natural number q, What . Let's multiply both sides of this equality by a natural number X. Then Oh= (bq)x, whence, based on the associative property of multiplication (bq)x = b(qx) and, therefore, Oh= b(qx), Where qx- natural number. According to the definition of the divisibility relation, , Q.E.D.
From the proven theorem it follows that if one of the factors of the product is divisible by a natural numberb, then the entire product is divisible by b.
For example, the product 24
Divisibility relation and its properties Definition Let a and b N. The number a is divisible by the number b if there is a natural number q such that a = bq and b q N such that a = bq In this case, the number b is called a divisor of the number a, and the number a is a multiple of b 24 8, since 3 N, which means 24 = 8 3
A distinction is made between the concepts “b is a divisor of the number a” and “b is a divisor.” In the expression “25: 8” the number 8 is a divisor (as a component of division), and in the expression “24: 8” the number 8 is a divisor of the number 24 Theorem 1 1 is a divisor of any natural numbers because for a N a = 1 a Theorem 2 If a b, then b a
Proof Since a is b, then q N, that a = bq a – b = bq – b = b · (q – 1). Since a is N, then q 1. Then b · (q – 1) 0, i.e. the difference a – b 0 b a From Theorem 2 it follows: The set of divisors of a given number a is finite - all divisors are less than the number b All divisors of the number 36 form a finite set (1, 2, 3, 4, 6, 9, 12, 18, 36)
Properties of the divisibility relation Theorem 3 (a N) a a, i.e. the divisibility relation is reflexive Proof (a N) a = a 1. Since 1 N is divisible, a a
Theorem 4 (a b and a b) b a, i.e. the divisibility relation is antisymmetric Proof (by contradiction) Let it be false that b a a b (by Theorem 2) By condition a b and a b b a (by Theorem 2) Inequalities a b and b a will be valid only when a = b, which contradicts the conditions of the theorem. Therefore our assumption is incorrect
Theorem 5 a b and b c a c, i.e. the divisibility relation is transitive Proof Since a b q N, that a = bq Since b c p N, that b = cf a = bq = (cf)q = c( pq). The number pq N. So, by definition of the divisibility relation, and with
Theorem 6 (divisibility test for a sum) If each of the natural numbers a 1, a 2, . . . , аn is divisible by a natural number b, then their sum is a 1 + a 2 +. . . + аn is divided by this number Proof Since a 1 b, then q 1 N, that a 1= b q 1 Since a 2 b, then q 2 N, that a 2= b q 2 ……………………. Since аn b, then qn N, that аn= b qn
a 1 + a 2 +. . . + аn = b (q 1 + q 2 +... + qn) = bq q = q 1 + q 2 +. . . + qn, i.e. q N i.e. the sum of a 1 + a 2 +. . . + аn is the product of the number b and the natural number q. Therefore, the sum is a 1 + a 2 +. . . + an is divided by b Example Sum (175 + 360 + 915) 5, because 175 5 and 360 5 and 915 5
Theorem 7 (divisibility test for a difference) If a 1 b, a 2 b and a 1 > a 2, then (a 1 – a 2) b Proof is similar to the proof of Theorem 6
Theorem 8 (test for the divisibility of a product) If a b, then ax b, where x N Proof Since a b, then q N, that a = bq on x ax = (bq)x = b(qx), i.e. ax = b(qx), where qx N by definition of the divisibility relation ax b
It follows from Theorem 8 that if one of the factors of the product is divisible by a natural number b, then the entire product is divisible by b Example Product (24 976 305) 12, since 24 12 Theorem 9 If in the sum one term is not divisible by the number b, and all other terms are divisible by the number b, then the entire sum is not divisible by the number b
Example Sum (34 + 125 + 376 + 1024) 2, since 34 2, 376 2, 124 2, but 125 2 Theorem 10 If in the product ab the factor a is divided by the natural number m, and the factor b is divided by the natural number n, then ab is divisible by mn. Proof is based on Theorem 8
Theorem 11 If ac bc and c N, then a b Proof Since ac bc, then q N is such that ac = (bc)q ac = (bq)c, therefore a = bq, i.e. a b
Tests for divisibility Theorem 12 (test for divisibility by 2) In order for a number x to be divisible by 2, it is necessary and sufficient that its decimal notation ends in one of the digits 0, 2, 4, 6, 8 Proof 1) Let the number x be written in the decimal system notation: x = аn · 10 n + аn-1 · 10 n – 1 +. . . + a 1 · 10 + a 0 , where аn, аn-1, . . . a 1 takes the values 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, an 0 and a 0 takes the values 0, 2, 4, 6, 8
x = аn· 10 n+аn-1· 10 n -1+. . . + a 1 10 + a 0 = = (an 10 n-1 + an-1 10 n -2+... + a 1) 10 + a 0 is divisible by 2, since 10 2 a 0 is also divisible by 2, because by condition it ends in 0, 2, 4, 6 or 8
2) Let us prove that if the number x is 2, then a 0 takes the values 0, 2, 4, 6 or 8 x = аn· 10 n + аn-1· 10 n -1 +. . . + a 1 10 + a 0 = x – (аn 10 n + аn-1 10 n -1+... + а 1 10) is divisible by 2, because 10 2 The number x 2 by condition a 0 2
Theorem 13 (test for divisibility by 5) In order for a number x to be divisible by 5, it is necessary and sufficient that its decimal notation ends with the number 0 or 5. The proof is similar to the test for divisibility by 2.
Theorem 14 (test for divisibility by 4) In order for the number x to be divisible by 4, it is necessary and sufficient that the two-digit number formed by the last two digits of the decimal notation of the number x is divisible by 4. Proof 1) x = аn· 10 n+аn-1· 10 n -1+. . . а 2 102 + а 1 10 + а 0 = = (аn 10 n-2 + аn-1 10 n -3+... + а 2) 102 + а 1 10 + а 0 is divided by 4, because 102 4 is divisible by 4 according to the condition
2) Let us prove that if the number x is 4, then (a 1 10 + a 0) forms a two-digit number, which is divisible by 4 x = an 10 n + an-1 10 n -1+. . . + a 2 10 2 + a 1 10 + a 0 = x – (аn 10 n + аn-1 10 n -1+... + а 2 10 2) is divisible by 4, because 102 4 The number x 4 according to the condition (a 1 10 + a 0) 4
Example 1) Number 1 5 7 8 7 2 4 72 4 2) Number 9 8 7 6 4 1 4 41 4
Theorem 15 (divisibility test by 9) In order for a number x to be divisible by 9, it is necessary and sufficient that the sum of the digits of its decimal notation is divisible by 9. Proof 1) Let us prove that (10 n – 1) 9
10 n – 1 = 10 10 n-1 – 1 = (9 + 1) 10 n-1 – 1 = = (9 10 n - 1 + 10 n - 1) – 1 = = (9 10 n - 1 + 9 10 n - 2 + 10 n - 2) – 1 = = (9 10 n-1 + 9 10 n-2 +... + 10) – 1 = = 9 10 n-1 + 9 · 10 n-2 + 10 n-2 +. . . + 9 = 9 · (10 n-1 + 10 n-2 + 10 n-2 +... + 1) divided by 9 (10 n – 1) 9
2) To the decimal notation of the number x: x = аn · 10 n + аn-1 · 10 n – 1 +. . . + а 1 10 + а 0 add and subtract the expression (аn+ аn-1+... + а 0) We get: x = (аn 10 n – аn) + (аn-1 10 n-1 – аn- 1) +. . . + (a 1 10 – a 1) + (a 0 – a 0) + (аn +аn-1 +... + а 1 + а 0) = divisible by 9, since each term contains a factor ( 10 n – 1) = аn (10 n – 1) + аn-1 (10 n-1 – 1)+. . . + a 1 (10 – 1) + + (аn + аn-1 +... + а 1 + а 0) is divided by 9 according to the condition
3) We prove that if the number x is 9, then (аn+ аn-1+... + а 0) 9 We write the equality in the form: x = (аn· 10 n – аn) + (аn-1 · 10 n- 1– an-1) +. . . + (а 1· 10 – а 1) + + (а 0 – а 0) + (аn +аn-1 +... + а 1 + а 0) аn +аn-1 +. . . + а 1 + а 0 = = x – (аn (10 n – 1) + аn-1 (10 n-1 – 1) +... + а 1 (10 – 1)) On the right side of this equalities, the minuend and subtrahend are multiples of 9, then by the theorem on the divisibility of the difference (аn +аn-1 +... + а 1 + а 0) 9
Example Number 34578 9, since 3 + 4 + 5 + 7 + 8 = 27, 27 9 Number 130542 is not divisible by 9, since 1 + 3 + 0 + 5 + 4 + 2 = 15, 15 is not divisible by 9
Theorem 16 (divisibility test by 3) In order for a number x to be divisible by 3, it is necessary and sufficient that the sum of the digits of its decimal notation is divisible by 3. The proof is similar to the proof of the divisibility test by 9
Least common multiple and common divisor greatest Definition The common multiple of natural numbers a and b is a number that is a multiple of each of these numbers. The smallest number of all common multiples of a and b is called the least common multiple of these numbers. The least common multiple of a is denoted by K(a, b) and b
The common multiples of the numbers 12 and 18 are: 36, 72, 108, 144, 180 ... The number 36 is the least common multiple of the numbers 12 and 18 Write: K(12, 18) = 36 Properties of K(a, b) 1. Least common multiple the numbers a and b always exist and are unique 2. The least common multiple of the numbers a and b is not less than the largest of the given numbers, i.e. if a > b, then K(a, b) > a 3. Any common multiple of the numbers a and b is divided by their least common multiple
Definition The common divisor of natural numbers a and b is a number that is a divisor of each of these numbers. The largest number of all common divisors of the numbers a and b is called the greatest common divisor of these numbers. The greatest common divisor of the numbers a and b is denoted by D(a, b) The common divisors of the numbers 12 and 18 are the numbers: 1, 2, 3, 6 Number 6 is the greatest common divisor of the numbers 12 and 18 Write: D(12, 18) = 6
The number 1 is a common divisor of any two natural numbers a and b. Definition D(a, b) = 1, then the numbers a and b are called mutually simple Example The numbers 14 and 15 are relatively prime, since D(14, 15) = 1
Properties of D (a, b) 1. The greatest common divisor of the numbers a and b always exists and is unique 2. The greatest common divisor of the numbers a and b does not exceed the smaller of the given numbers, i.e. if a
The product of the least common multiple and the greatest common divisor of the numbers a and b is equal to the product of these numbers, i.e. K(a, b) · D(a, b) = a · b Corollaries 1) The least common multiple of two coprime numbers is equal to the product these numbers, i.e. D(a, b) = 1 K(a, b) = a · b For example, K(14, 15) = 14 15, since D (14, 15) = 1
2) Test for divisibility by a composite number: In order for a natural number a to be divisible by the product of coprime numbers m and n, it is necessary and sufficient that it is divisible by both m and n Example 6 = 2 3 and D(2, 3 ) = 1, then we obtain a test for divisibility by 6: in order for a natural number to be divisible by 6, it is necessary and sufficient that it be divisible by 2 and 3 This sign can be used repeatedly
Problem Formulate a criterion for divisibility by 60. In order for a number to be divisible by 60, it is necessary and sufficient that it is divisible by both 4 and 15, where D(4, 15) = 1. In turn, the number will be divisible by 15 then and only when it is divisible by both 3 and 5, where D(3, 5) = 1 Thus, the sign of divisibility by 60: In order for a number to be divisible by 60, it is necessary and sufficient that it is divisible by 4, on 3 and 5
3) The quotients obtained by dividing two given numbers by their greatest common divisor are coprime numbers. For example, let’s check whether the number 12 is the greatest common divisor of the numbers 24 and 36. To do this, divide 24 and 36 by 12. We get the numbers 2 and 3, where D (2, 3) = 1, i.e. 2 and 3 are relatively prime. Therefore, D(24, 36) = 12
Prime and Composite Numbers Definition Prime are numbers that are divisible only by themselves and one Definition Composite are numbers that have more than two divisors Unit is neither a prime nor a composite number Numbers 2, 5, 17, 61, etc. . – prime numbers, numbers 4, 25, 102, etc. – composite
Properties of prime numbers 1. If a prime number p is divisible by some natural number n, where n ≠ 1, then it coincides with n Indeed, if p ≠ n, then the number p has three divisors: 1, n and p, and then it is not prime 2. If p and q are prime numbers and p ≠ q, then p is not divisible by q. If p is a prime number, then it has only two divisors: 1 and p. By condition, q is also prime, which means q ≠ 1 and q ≠ р Therefore, q is not a divisor of the number p Numbers 17 and 11 are prime, which means 17 is not divisible by 11
3. If a natural number a is not divisible by a prime number p, then a and p are coprime, i.e. D (a, p) = 1 For example, 25 is not divisible by 7, then 25 and 7 are coprime 4. If the product of two natural numbers a and b is divisible by a prime number p, then at least one of them is divisible by p For example, 25 39 = 975. The number 975 is divisible by 3, since 9 + 7 + 5 = 21. But the number 25 is not divisible by 3, therefore 39 is divisible by 3
5. If a natural number is greater than 1, then it has at least one prime divisor. Indeed, all prime numbers have prime divisors - these numbers themselves, composite numbers, can be factored until they become prime numbers. For example, 240 > 1 , means it has at least one prime divisor, this is the number 2 (or 5)
6. The smallest prime divisor of a composite number a does not exceed Proof Let a be a composite number and p its smallest prime divisor. Then a = pb. In this case, p b, because otherwise the prime divisor of b would be less than p, and then a would have prime divisors less than p. Let's multiply both sides of the inequality by p. We get, p2 pb pb = a. Therefore, p2 a, i.e. p
Theorem – Fundamental theorem of arithmetic Any composite number can be uniquely represented as a product of prime factors where a 1, a 2, a 3, ..., ak are prime numbers, n 1, n 2, n 3, ..., nk are exponents, c which include prime numbers in the decomposition of the number x. Such a decomposition of a number into prime factors is called canonical
Example 110 = 2 5 11 – the product of prime factors is the decomposition of the number 110 into prime factors. Two decompositions of a number into prime factors are considered the same if they differ from each other only in the order of the factors 110 = 2 5 11 = 5 11 2 - the same decomposition
Method of factoring a number into prime factors 90 2 45 3 15 3 5 5 only prime numbers 1 Thus, 90 = 2 3 5 1 = 2 32 5 60 = 22 3 5; 72 = 23 32
Sieve of Eratosthenes Eratosthenes (3rd century BC) invented a way to obtain prime numbers not exceeding the natural number a (sieve of Eratosthenes) Find all prime numbers up to 50
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
The infinity of the set of prime numbers Theorem proved by Euclid The set of prime numbers is infinite Proof Let the set of prime numbers be finite and consist of the numbers: 2, 3, 5, 7, . . . , p, where p is the largest prime number. Let's find the product of all prime numbers 2 3 5 7. . . p = a. Let's add one to a. The number a + 1 is not prime, because a + 1 > p of the largest prime number (by assumption)
Let a + 1 be a composite number (a + 1) must have at least one prime divisor q p. Since the number a = 2 3 5 p is also divisible by this prime number q, then the difference (a + 1) - a is divisible by q, i.e. the number 1 is divisible by q, which is impossible. So, the number and is neither simple nor composite. But this also cannot be - every number other than 1 is either prime or composite. Therefore, the proposition that the set of prime numbers is finite and is the largest prime number is false, and therefore the set of prime numbers is infinite
Methods for finding the greatest common divisor and the least common multiple of numbers Method 1 To find the gcd of two numbers, you can list all their common divisors and select the greatest from them Example Given the numbers 120 and 486 Divisors of the number 120: 1, 2, 3, 4, 5, 6 , 8, 10, 12, 15, 20, 24, 30, 40, 60, 120 Divisors of 486: 1, 2, 3, 6, 9, 27, 54, 81, 162, 243, 486 Common divisors: 1, 2, 3, 6 The greatest common divisor is the number 6
To find the LCM of two numbers, you can list some of their common multiples and choose the smallest one. Example Given the numbers 60 and 48 Multiples of 60: 60, 120, 180, 240, 300, 360, 420, 480, 540, . . . Multiples of 48: 48, 96, 144, 192, 240, 288, 336, 384, 432, 480, . . . Common multiples of 60 and 48 are: 240, 480, . . . The least common multiple is 240
Method 2 - based on decomposition of given numbers into prime factors. Algorithm for finding the greatest common divisor of given numbers: 1) represent each given number in canonical form; 2) form the product of prime factors common to all given numbers, each with the smallest exponent with which it is included in all expansions of the given numbers; 3) find the value of this product - it will be the greatest common divisor of these numbers
Example Two numbers are given: 3600 and 288. Canonical expansion of these numbers: 3600 = 24 32 52; D(3600, 288) = 24 32 = 144 288 = 25 32
An algorithm for finding the least common multiple of given numbers: 1) represent each given number in canonical form; 2) form the product of all prime factors found in the expansions of these numbers, each with the highest exponent with which it is included in all expansions of these numbers; 3) find the value of this product - it will be the least common multiple of these numbers
Example Two numbers are given: 3600 and 288. Canonical expansion of these numbers: 3600 = 24 32 52; 288 = 25 32 K(3600, 288) = 25 32 52 = 7200
Method 3 - Euclid's algorithm The Euclid algorithm is based on the following statements: 1. If a is divisible by b, then D(a, b) = b 2. If a = bq + r and r
Src="https://present5.com/presentation/3/71306524_41475257.pdf-img/71306524_41475257.pdf-55.jpg" alt="Let a > b If a is divisible by b, then D(a , b) = b"> Пусть а > b Если а делится на b, то D(a, b) = b Если при делении а на b, получается остаток r, то а = bq + r и D(a, b) = D(b, r) Найдем D(b, r) Если b делится на r, то D(b, r) = r и тогда D(a, b) = r Если при делении b на r получается остаток r 1, то b = rq 1 + r 1, и тогда D(r, r 1) = D(b, r) = D(a, b) Найдем D(r, r 1)!}
Continuing the described process, we get smaller and smaller balances. As a result, we obtain a remainder by which the previous remainder will be divided. This smallest non-zero remainder will be the greatest common divisor of the numbers a and b. You can find the LCM and GCD of numbers using the formula: K(a, b) D(a, b) = a b K(a, b) = a b: D(a, b) = a b: K(a, b)
Example Find, using the Euclidean algorithm, the greatest common divisor of the numbers 2585 and 7975 = 2585 3 + 220 2585 = 220 11 + 165 220 = 165 1 + 55 165 = 55 3 + 0 So, D(7975, 2585) = 55, K(7975, 2585) = = (7975 2585) : 55 = = 20615375: 55 = 374825
7975 7555 2585 220 385 220 165 165 0 55 3 165 1 220 11 2585 3
Definition. Let natural numbers a and b be given. A number a is said to be divisible by a number b if there is a natural number q such that a = bq.
In this case, the number b is called divisor of a number a, and the number a is multiples of the number b.
For example, 24 is divisible by 8, since there is a q =3 such that 24 = 8·3. You can say it differently: 8 is a divisor of the number 24, and 24 is a multiple of the number 8. In the case when a is divided by b, they write: a: . b. This entry "" is also read like this: “a is a multiple of b.” Note that the concept of “divisor of a given number” should be distinguished from the concept of “divisor”, which denotes the number by which it is divided. For example, if 18 is divided by 5, then the number 5 is a divisor, but 5 is not a divisor of the number 18. If 18 divides 6, then in this case the concepts of “divisor” and “divisor of a given number” coincide.
From the definition of the divisibility relation and the equality a = 1·a, which is valid for any natural number a, it follows that 1 is a divisor of any natural number.
Let's find out how many divisors the natural number a can have. Let's first consider the following theorem.
Theorem 1. Divisor b of a given number a does not exceed this number, i.e. If
A: . b, then b< а.
Proof. Since a: . b, then there exists q Є N such that a = bq u, which means a-b = bq – b= b (q - 1). Since q Є N, then q≥ 1. Then b· (q - 1) ≥ 0 and therefore , b ≤ a.
From this theorem it follows that the set of divisors of a given number is finite. Let's call, for example, all the divisors of the number 36. They form a finite set (1,2,3,4,6,9,12,18,36).
Depending on the number of divisors, natural numbers are divided into prime and composite numbers.
Definition. A prime number is a natural number that has only two divisors - one and the number itself.
For example, the number 13 is prime because it has only two divisors: 1 and 13.
Definition. A composite number is a natural number that has more than two divisors.
So the number 4 is composite, it has three divisors: 1,2 and 4.
The number 1 is neither a prime nor a composite number due to the fact that it has only one divisor.
Numbers, multiples given number, you can name as many as you like - there are an infinite number of them. Thus, numbers that are multiples of 4 form an infinite series: 4, 8, 12, 16, 20, 24, ..., and all of them can be obtained by the formula a = 4q, where q takes the values 1, 2, 3,... .
We know that the divisibility relation has a number of properties, in particular, it is reflexive, antisymmetric and transitive. Now, having a definition of the divisibility relation, we can prove these and other properties of it.
Theorem 2. The divisibility relation is reflexive, i.e. Any natural number is divisible by itself.
Proof. For any natural number a, the equality a = a·1 is true. Since 1 Є N, then, by definition of the divisibility relation, a: . A.
Theorem 3. The divisibility relation is antisymmetric, i.e. if a: . b and a ≠ b,
That b ⁞͞ a.
Proof. Let's assume the opposite, i.e. that b ⁞ a. But then a ≤ b, according to the theorem discussed above.
By condition and ⁞ . b and a ≠ b. Then, by the same theorem, b ≤ a.
The inequalities a ≤ b and b ≤ a will be valid only when a = b, which contradicts the conditions of the theorem. Therefore, our assumption is incorrect and the theorem is proven.
Theorem 4. The divisibility relation is transitive, i.e. if a ⁞ b and b ⁞ s, then a ⁞ With.
Proof. Since a: . b, then there is a natural number q such that a = bq, and since b ⁞ c, then there exists a natural number p such that b = cf. But then we have: a = bq = (cp)q = c(pq) - The number pq is a natural number. This means, by definition of the divisibility relation,
A ⁞ With.
Theorem 5 (test of divisibility of the sum). If each of the natural numbers a 1, a 2, ..., a n is divisible by a natural number b, then their sum a 1 + a 2 + ... + a n is divisible by this number.
Proof. Since a 1 ⁞ b, then there is a natural number q 1 such that a 1 =bq 1. Since a 2 ⁞ b, then there exists a natural number q 2 such that a 2 = bq 2 . Continuing the reasoning, we get that if a n: . b, then there is a natural number q n such that a n = bq n. These equalities allow us to transform the sum a 1 + a 2 + ... + a n into a sum of the form bq 1 + bq 2 + ... + bq n. Let's take the common factor b out of brackets, and denote the resulting natural number q 1 + q 2 + ... + q n by the letter q. Then a 1+ a 2 + ... + a n = b(q 1 + q 2 +... + q n) = bq, i.e. the sum a 1 + a 2 +… + a n turned out to be represented as the product of the number b and some natural number q. This means that the sum a 1 + a 2 +... + a n is divisible by b, which is what needed to be proven.
For example, without doing any calculations, we can say that 175 + 360 + 915 is divisible by 5, since each term of this sum is divisible by 5.
Theorem 6 (test for the divisibility of a difference). If the numbers a 1 and a 2 are divisible by b and a 1 ≥ a 2, then their difference a 1 - a 2 is divisible by b.
The proof of this theorem is similar to the proof of the divisibility test for a sum.
Theorem 7 (divisibility test for a product). If the number a is divisible by b, then a product of the form ax, where x Є N, is divisible by b.
Proof. Since a: . b, then there exists a natural number q such that a= bq. Let's multiply both sides of this equality by a natural number x. Then ax = (bq)x, from which, based on the associativity property of multiplication, (bq)x = b(qx) and, therefore, ax = b(qx), where qx is a natural number. According to the definition of the divisibility relation, ax: . b, which is what needed to be proven.
From the proven theorem it follows that if one of the factors of a product is divisible by a natural number b, then the entire product is divisible by b. For example, the product 24 976 305 is divisible by 12, since the factor 24 is divisible by 12.
Let's consider three more theorems related to the divisibility of a sum and a product, which are often used in solving divisibility problems.
Theorem 8. If in the sum one term is not divisible by the number b, and all other terms are divisible by the number b, then the entire sum is not divisible by the number b.
Proof. Let s = a 1 + a g + ... + a n + "c and it is known that a 1: . B, and 2: . B,
a 3: . b, ... and n: . b, but with: . b. Let us prove that then s: . b
Let's assume the opposite, i.e. Let s: . b. Let us transform the sum s to the form c = s- ( a 1 + a 2 +… + and n). Since s: . b by assumption, ( a 1 + a 2 +… + and n): . b according to the divisibility theorem of a sum, then by the divisibility theorem of the difference c: .b
We came to a contradiction with what was given. Therefore, s: . b.
For example, the sum 34 + 125 + 376 + 1024 is not divisible by 2, so 34: .2,376: .2,124: .2, but 125 is not divisible by 2.
Theorem 9 . If in the product ab the multiplier a is divided by the natural number m, and the factor b is divided by the natural number n, then ab is divided by mn.
The validity of this statement follows from the theorem on the divisibility of a product.
Theorem 10. If the work ac is divisible by the product bс, and c is a natural number, then A is divisible by b.
Proof. Since ace shares on bc, then there is a natural number q such that ac = (bc)q, whence ac = (bq)c and, therefore, a = bq, i.e. A:.b.
Exercises
1. Explain why 15 is a divisor of 60 but not 70.
2. Construct a graph of the relation “to be a divisor of a given number” given on the set X = (2, 6,. 12, 18, 24). How are the properties of this relationship reflected in this graph?
3. It is known that the number 24 is a divisor of the number 96, and the number 96 is a divisor of the number 672. Prove that the number 24 is a divisor of the number 672 without performing division.
4. Write down the set of divisors of the number.
a) 24; 6)13; in 1.
5 .On the set X =(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11; 12) the relation “to have the same number of divisors” is given. Is it an equivalence relation?
6 .Build a conclusion proving that:
a) the number 19 is prime;
b) the number 22 is composite.
7. Prove or disprove the following statements:
a) If the sum of two terms is divisible by a certain number, then each term is divisible by this number.
b) If one of the terms of the sum is not divisible by a certain number, then the sum is not divisible by this number.
c) If not a single term is divisible by a certain number, then the sum is not divisible by this number.
d) If one of the terms of the sum is divisible by a certain number, and the other is not divisible by this number, then the sum is not divisible by this number.
8. Is it true that:
a) a: . ty b: . n =>ab: .mn
b) a: .n and b: .n => ab: .n;
c) ab: .n => a: .n or b: .n.
Divisibility of natural numbers
As you know, subtraction and division on the set of natural numbers is not always feasible. The question of the existence of a difference between natural numbers a and b is solved simply - it is enough to establish (by writing the numbers) that b< а. Для деления такого общего и simple sign No. Therefore, in mathematical science, for a long time, they have been trying to find rules that would allow one to find out from writing the number a whether it is divisible by the number b or not, without directly dividing a by b. As a result of these searches, not only some signs of divisibility were discovered, but also other important properties of numbers; Let's get to know some of them.
IN elementary courses In mathematics, the divisibility of natural numbers is, as a rule, not studied, but many facts from this branch of mathematics are used implicitly. For example, the sign of divisibility of a sum, difference, and product by a number is closely related to the rules for dividing a sum, difference, and product by a number, studied in elementary grades. A number of courses study the signs of divisibility of numbers by 2, 3, 5 and others.
In general, knowledge about the divisibility of natural numbers expands the understanding of the set of natural numbers, allows you to better understand the material related to the division of natural numbers, apply previously acquired knowledge about methods of proof, the properties of relations, etc.
Divisibility relation and its properties
Definition . Let natural numbers a and b be given. A number a is said to be divisible by a number b if there is a natural number q such that a - bq.
In this case, the number b is called divisor of a number a, and the number a is multiples of the number b .
For example, 24 is divisible by 8, since there is a q = 3 such that 24 = 8·3. We can say it differently: 8 is a divisor of the number 24, and 24 is a multiple of the number 8.
In the case when a is divisible by b, write: a b. This entry is often read like this: “a is a multiple of b.”
Note that the concept of “divisor of a given number” should be distinguished from the concept of “divisor”, which denotes the number by which it is divided. For example, if 18 is divided by 5, then the number 5 is a divisor, but 5 is not a divisor of the number 18. If 18 is divided by 6, then in this case the concepts of “divisor” and “divisor of a given number” coincide.
From the definition of the divisibility relation and the equality a = 1 a, which is valid for any natural a, it follows that 1 is a divisor of any natural number.
Let's find out how many divisors the natural number a can have. Let's first consider the following theorem.
Theorem 1. Divisor b of a given number a does not exceed this number, i.e. if a b, then b≤a.
Proof. Since a is b, then there is a q N such that a=bq and, therefore, a-b = bq-b = b· (q- 1). Since a is N, then q≥l. Then b· (q- 1) ≥0 and, therefore, b≤a.
From this theorem it follows that the set of divisors of a given number is finite . Let's call, for example, all the divisors of the number 36. They form a finite set (1, 2, 3.4, 6.9, 12, 18, 36).
Depending on the number of divisors, natural numbers are divided into prime and composite numbers.
Definition. A prime number is a natural number that has only two divisors - one and the number itself.
For example, the number 13 is prime because it has only two divisors: 1 and 13.
Definition. A composite number is a natural number that has more than two divisors.
So the number 4 is composite, it has three divisors: 1, 2 and 4.
The number 1 is neither a prime nor a composite number due to the fact that it has only one divisor.
Numbers that are multiples of a given number can be named as many as you like - there is an infinite number of them. Thus, numbers that are multiples of 4 form an infinite series: 4, 8, 12, 16, 20, 24, ..., and all of them can be obtained by the formula a = 4q, where q takes the values 1, 2, 3,. ...
We know that the divisibility relation has a number of properties, in particular, it is reflexive, antisymmetric and transitive. Now, having a definition of the divisibility relation, we can prove these and other properties of it.
Theorem 2. The divisibility relation is reflexive, i.e. Any natural number is divisible by itself.
Proof. For any natural number a, the equality a = a·1 is true. Since 1 N, then, by definition of the divisibility relation, a.
Theorem 3. The divisibility relation is antisymmetric, i.e.
if a b and a≠b, then .
Proof. Let's assume the opposite, i.e. that b a. But then a ≤ b, according to the theorem discussed above.
By condition a b and a≠b. Then, by the same theorem, b≤a.
The inequalities a ≤b and b ≤a will be valid only when a=b, which contradicts the conditions of the theorem. Consequently, our assumption is incorrect and therefore if a b and a≠b, then .
Theorem 4. The divisibility relation is transitive, i.e. if a b and b c, then a c.
Proof. Since a b, then there is a natural number q such that a - bq, and since b c, then there is a natural number p such that b = cf. But then we have: a=bq = (cp)q = c(pq). The number pq is a natural number. This means, by definition of the divisibility relation, and c.
Theorem 5 (test of divisibility of the sum). If each of the natural numbers a 1 , a 2 , ... , a n is divisible by a natural number b, then their sum a 1 + a 2+ ...+ a n is divisible by this number.
Proof. Since a 1 b, then there is a natural number q 1 such that a 1= bq 1. Since a 2 b, then there is a natural number q 2 such that a 2 = bq 2. Continuing the reasoning, we find that if a n b, then there is a natural number q n such that a n = bq n. These equalities allow us to transform the sum a 1 + a 2 + ... + a n into a sum of the form bq 1 + bq 2 + ... + bq n. Let's take the common factor b out of brackets, and denote the resulting natural number q 1 + q 2 + ... + q n by the letter q. Then a 1 + a 2 + ... + a n = b(g 1 + q 2 + ... + q n)= bq, i.e. the sum a 1 + a 2 + ... + a n turned out to be represented as the product of the number b and some natural number q. This means that the sum a 1 + a 2 + ... + a n is divisible by b, which is what needed to be proven.
For example, without making calculations, we can say that the sum 175 + 360 + 915 is divisible by 5, since each term of this sum is divisible by 5.
Theorem 6(test of the divisibility of the difference). If the numbers a 1 and a 2 are divisible by b and a 1 > a 2, then their difference a 1 - a 2 is divisible by b.
The proof of this theorem is similar to the proof of the divisibility test for a sum.
Theorem 7 (test of divisibility of a product). If the number a is divisible by b, then the product of the form ax, where x is N, is divisible by b.
Proof. Since a is b, then there is a natural number q such that a = bq. Let's multiply both sides of this equality by a natural number x. Then ax = (bq)x, from which, based on the associative property of multiplication, (bq)x – b(qx) and, therefore, ax = b(qx), where qx is a natural number. According to the definition of the divisibility relation ax b, which is what needed to be proved.
From the proven theorem it follows that if one of the factors of a product is divisible by a natural number b, then the entire product is divisible by b.
For example, the product 24 – 976 – 305 is divisible by 12, since the factor 24 is divisible by 12.
Let's consider three more theorems related to the divisibility of a sum and a product, which are often used in solving divisibility problems.
Theorem 8. If in the sum one term is not divisible by the number b, and all other terms are divisible by the number b, then the entire sum is not divisible by the number b.
Proof. Let s = a 1 + a 2 + ... + a n + c and it is known
that a 1 b, a 2 b ... a n b, but . Let us prove that then .
Let's assume the opposite, i.e. let s b. Let us transform the sum s to the form c = s - (a 1 + a 2 + ... + a n). Since s b by assumption, (a 1 + a 2 + ... + a n) b according to the divisibility test for a sum, then by the theorem on the divisibility of the difference with b. We came to a contradiction with what was given. Hence, .
For example, the sum 34 + 125 + 376 + 1024 is not divisible by 2, since 34 2, 376 2,124 2, but .
Theorem 9. If in the product ab the factor a is divided by the natural number m, and the factor b is divided by the natural number n, then ab is divided by mn.
The validity of this statement follows from the theorem on the divisibility of a product.
Theorem 10. If the product ac is divisible by the product bc, and c is a natural number, then i is also divisible by b.
Proof. Since ac is divisible by bc, there is a natural number q such that ac = (bc)q, whence ac = (bq)c and, therefore, a = bq, i.e. a b.
Signs of divisibility
The properties of the divisibility relation considered in paragraph 88 make it possible to prove the known signs of the divisibility of numbers written in the decimal number system by 2, 3,4, 5, 9.
Divisibility tests allow you to determine by writing a number whether it is divisible by another, without performing division.
Theorem 11 (test of divisibility by 2). In order for a number x to be divisible by 2, it is necessary and sufficient that its decimal notation ends in one of the digits 0, 2, 4, 6, 8.
Proof. Let the number x be written in the decimal number system, i.e. x = a n ·10 n + a n-1 ·10 n-1 + ... + a 1 ·10 + a 0, where a n, a n-1,..., a 1, take values 0, 1,2, 3, 4, 5, 6, 7, 8, 9, and n ≠ 0 and a 0 takes the values 0,2,4,6,8. Let us prove that then x is 2.
Since 10 2, then 10 2 2, 10 3 2, ..., 10 n 2 and, therefore, (a n ·10 n + a n-1 ·10 n-1 + ... + a 1 ·10 ) 2. By condition a 0 is also divisible by 2, and therefore the number x can be considered as the sum of two terms, each of which is divisible by 2. Therefore, according to the divisibility test for the sum, the number x is divisible by 2.
Let's prove the opposite: if the number x is divisible by 2, then its decimal notation ends in one of the digits 0, 2,4, 6, 8.
Let us write the equality x = a n ·10 n + a n-1 ·10 n-1 + ... + a 1 ·10+a in this form:
a o = x-(a n ·10 n + a n-1 ·10 n-1 + ... + a 1 ·10). But then, according to the theorem on the divisibility of the difference, a o 2, since x 2 and (a n ·10 n + a n-1 ·10 n-1 + ... + a 1 ·10) 2. So that a single-digit number a 0 divided by 2, it must take the values 0, 2, 4, 6, 8.
Theorem 12 (test of divisibility by 5). In order for a number x to be divisible by 5, it is necessary and sufficient that its decimal notation ends in the number 0 or 5.
The proof of this test is similar to the proof of the test of divisibility by 2.
Theorem 13 (test of divisibility by 4). In order for the number x to be divisible by 4, it is necessary and sufficient that the two-digit number formed by the last two digits of the decimal notation of the number x is divisible by 4.
Proof. Let the number x be written in the decimal number system, i.e. x = a n ·10 n + a n-1 ·10 n-1 + ... + a 1 ·10 + a 0 and the last two digits in this entry form a number that is divisible by 4. Let us prove that then x 4 .
Since 100 4, then (a n ·10 n + a n-1 ·10 n-1 + ... + a 1 ·10) 4. By condition, a 1 ·10 + a 0 (this is the recording of the two-digit numbers) is also divisible by 4. Therefore, the number x can be considered as the sum of two terms, each of which is divisible by 4. Therefore, according to the divisibility test for the sum, the number x itself is divisible by 4.
Let us prove the opposite, i.e. If the number x is divisible by 4, then the two-digit number formed by the last digits of its decimal notation is also divisible by 4.
Let us write the equality x = a n 10 n + a n-1 10 n-1 + ... + a 1 10 + a 0 in this form: a 1 10 + a o = x- (a n 10 n + a n-1 ·10 n-1 + ... + a 2 ·10 2). Since x 4 and (a n ·10 n + a n-1 ·10 n-1 + ... + a 2 ·10 2) 4, then by the theorem on the divisibility of the difference (a 1 ·10 + a o) 4 But the expression a 1 · 10 + a 0 is a recording of a two-digit number formed by the last digits of the number x.
Loading...
