Let's solve the problem. We have two types of cookies. Some are chocolate and others are plain. There are 48 chocolate cookies, and 36 plain ones. You need to make as many of these cookies as possible. possible number gifts, but you need to use them all.
First, let's write down all the divisors of each of these two numbers, since both of these numbers must be divisible by the number of gifts.
We get,
- 48: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48.
- 36: 1, 2, 3, 4, 6, 9, 12, 18, 36.
Let us find among the common divisors that both the first and second numbers have.
Common factors will be: 1, 2, 3, 4, 6, 12.
The greatest common factor of all is the number 12. This number is called the greatest common factor of the numbers 36 and 48.
Based on the results obtained, we can conclude that 12 gifts can be made from all the cookies. One such gift will contain 4 chocolate cookies and 3 regular cookies.
Finding the Greatest Common Divisor
- The largest natural number that divides two numbers a and b without a remainder is called the greatest common divisor of these numbers.
Sometimes the abbreviation GCD is used to shorten the entry.
Some pairs of numbers have one as their greatest common divisor. Such numbers are called mutually prime numbers. For example, the numbers 24 and 35 have GCD =1.
How to find the greatest common divisor
In order to find the largest common divisor It is not necessary to write down all the divisors of these numbers.
You can do it differently. First, factor both numbers into prime factors.
- 48 = 2*2*2*2*3,
- 36 = 2*2*3*3.
Now, from the factors that are included in the expansion of the first number, we will cross out all those that are not included in the expansion of the second number. In our case, these are two deuces.
- 48 = 2*2*2*2*3 ,
- 36 = 2*2*3 *3.
The factors remaining are 2, 2 and 3. Their product is 12. This number will be the greatest common divisor of the numbers 48 and 36.
This rule can be extended to the case of three, four, etc. numbers.
General scheme for finding the greatest common divisor
- 1. Divide numbers into prime factors.
- 2. From the factors included in the expansion of one of these numbers, cross out those that are not included in the expansion of other numbers.
- 3. Calculate the product of the remaining factors.
To learn how to find the greatest common divisor of two or more numbers, you need to understand what natural, prime and complex numbers are.
A natural number is any number that is used to count whole objects.
If a natural number can only be divided into itself and one, then it is called prime.
All natural numbers can be divided by themselves and one, but the only even prime number is 2, all others can be divided by two. Therefore, only odd numbers can be prime.
There are a lot of prime numbers full list they don't exist. To find GCD it is convenient to use special tables with such numbers.
Most natural numbers can be divided not only by one, themselves, but also by other numbers. So, for example, the number 15 can be divided by another 3 and 5. All of them are called divisors of the number 15.
Thus, the divisor of any A is the number by which it can be divided without a remainder. If a number has more than two natural divisors, it is called composite.
The number 30 can have divisors such as 1, 3, 5, 6, 15, 30.
You will notice that 15 and 30 have the same divisors 1, 3, 5, 15. The greatest common divisor of these two numbers is 15.
Thus, the common divisor of the numbers A and B is the number by which they can be divided entirely. The largest can be considered the maximum total number, into which they can be divided.
To solve problems, the following abbreviated inscription is used:
GCD (A; B).
For example, gcd (15; 30) = 30.
To write down all the divisors of a natural number, use the notation:
D (15) = (1, 3, 5, 15)
GCD (9; 15) = 1
IN in this example Natural numbers have only one common factor. They are called relatively prime, so unity is their greatest common divisor.
How to find the greatest common divisor of numbers
To find the gcd of several numbers, you need:
Find all divisors of each natural number separately, that is, factor them into factors (prime numbers);
Select all identical factors of given numbers;
Multiply them together.
For example, to calculate the greatest common divisor of the numbers 30 and 56, you would write the following:
To avoid confusion, it is convenient to write down factors using vertical columns. On the left side of the line you need to place the dividend, and on the right side - the divisor. Under the dividend, you should indicate the resulting quotient.
So, in the right column there will be all the factors needed for the solution.
Identical divisors (found factors) can be underlined for convenience. They should be rewritten and multiplied and the greatest common divisor written down.
GCD (30; 56) = 2 * 5 = 10
This is how easy it really is to find the greatest common divisor of numbers. If you practice a little, you can do this almost automatically.
Key words of the summary:Integers. Arithmetic operations over natural numbers. Divisibility of natural numbers. Prime and composite numbers. Factoring a natural number into prime factors. Divisibility signs by 2, 3, 5, 9, 4, 25, 10, 11. Greatest common divisor (GCD), as well as least common multiple (LCD). Division with remainder.
Integers- these are numbers that are used to count objects - 1, 2, 3, 4 , ... But the number 0 is not natural!
The set of natural numbers is denoted by N. Record "3 ∈ N" means that the number three belongs to the set of natural numbers, and the notation "0 ∉ N" means that the number zero does not belong to this set.
Decimal number system - positioning system radix 10 .
Arithmetic operations on natural numbers
For natural numbers the following actions are defined: addition, subtraction, multiplication, division, exponentiation, root extraction. The first four actions are arithmetic.
Let a, b and c be natural numbers, then
1. ADDITION. Term + Term = Sum
Properties of addition
1. Communicative a + b = b + a.
2. Conjunctive a + (b + c) = (a + b) + c.
3. a + 0= 0 + a = a.
2. SUBTRACT. Minuend - Subtrahend = Difference
Properties of Subtraction
1. Subtracting the sum from the number a - (b + c) = a - b - c.
2. Subtracting a number from the sum (a + b) - c = a + (b - c); (a + b) - c = (a - c) + b.
3. a - 0 = a.
4. a - a = 0.
3. MULTIPLICATION. Multiplier * Multiplier = Product
Properties of Multiplication
1. Communicative a*b = b*a.
2. Conjunctive a*(b*c) = (a*b)*c.
3. 1 * a = a * 1 = a.
4. 0 * a = a * 0 = 0.
5. Distribution (a + b) * c = ac + bc; (a - b) * c = ac - bc.
4. DIVISION. Dividend: Divisor = Quotient
Properties of division
1. a: 1 = a.
2. a: a = 1. You can't divide by zero!
3. 0: a= 0.
Procedure
1. First of all, the actions in parentheses.
2. Then multiplication, division.
3. And only at the end addition and subtraction.
Divisibility of natural numbers. Prime and composite numbers.
Divisor of a natural number A is the natural number to which A divided without remainder. Number 1 is a divisor of any natural number.
The natural number is called simple, if it only has two divisor: one and the number itself. For example, the numbers 2, 3, 11, 23 are prime numbers.
A number that has more than two divisors is called composite. For example, the numbers 4, 8, 15, 27 are composite numbers.
Divisibility test works several numbers: if at least one of the factors is divisible by a certain number, then the product is also divisible by this number. Work 24 15 77 divided by 12 , since the multiplier of this number 24 divided by 12 .
Divisibility test for a sum (difference) numbers: if each term is divisible by a certain number, then the entire sum is divided by that number. If a: b And c: b, That (a + c) : b. And if a: b, A c not divisible by b, That a+c not divisible by a number b.
If a: c And c: b, That a: b. Based on the fact that 72:24 and 24:12, we conclude that 72:12.
Representation of a number as a product of powers prime numbers called factoring a number into prime factors.
Fundamental Theorem of Arithmetic: any natural number (except 1 ) or is simple, or it can be factorized in only one way.
When decomposing a number into prime factors, the signs of divisibility are used and the “column” notation is used. In this case, the divisor is located to the right of the vertical line, and the quotient is written under the dividend.
For example, task: factor a number into prime factors 330 . Solution:
Signs of divisibility into 2, 5, 3, 9, 10, 4, 25 and 11.
There are signs of divisibility into 6, 15, 45 etc., that is, into numbers whose product can be factorized 2, 3, 5, 9 And 10 .
Greatest common divisor
The largest natural number by which each of two given natural numbers is divisible is called greatest common divisor these numbers ( GCD). For example, GCD (10; 25) = 5; and GCD (18; 24) = 6; GCD (7; 21) = 1.
If the greatest common divisor of two natural numbers is equal to 1 , then these numbers are called mutually prime.
Algorithm for finding the greatest common divisor(NOD)
GCD is often used in problems. For example, 155 notebooks and 62 pens were divided equally between students in one class. How many students are in this class?
Solution: Finding the number of students in this class comes down to finding the greatest common divisor of the numbers 155 and 62, since the notebooks and pens were divided equally. 155 = 5 31; 62 = 2 31. GCD (155; 62) = 31.
Answer: 31 students in the class.
Least common multiple
Multiples of a natural number A is a natural number that is divisible by A without a trace. For example, number 8 has multiples: 8, 16, 24, 32 , ... Any natural number has infinitely many multiples.
Least common multiple(LCM) is the smallest natural number that is a multiple of these numbers.
Algorithm for finding the least common multiple ( NOC):
LCM is also often used in problems. For example, two cyclists simultaneously started along a cycle track in the same direction. One makes a circle in 1 minute, and the other in 45 seconds. In what minimum number of minutes after the start of the movement will they meet at the start?
Solution: The number of minutes after which they will meet again at the start must be divided by 1 min, as well as on 45 s. In 1 min = 60 s. That is, it is necessary to find the LCM (45; 60). 45 = 32 5; 60 = 22 3 5. LCM (45; 60) = 22 32 5 = 4 9 5 = 180. The result is that the cyclists will meet at the start in 180 s = 3 min.
Answer: 3 min.
Division with remainder
If a natural number A is not divisible by a natural number b, then you can do division with remainder. In this case, the resulting quotient is called incomplete. The equality is fair:
a = b n + r,
Where A- divisible, b- divider, n- incomplete quotient, r- remainder. For example, let the dividend be equal 243 , divider - 4 , Then 243: 4 = 60 (remainder 3). That is, a = 243, b = 4, n = 60, r = 3, then 243 = 60 4 + 3 .
Numbers that are divisible by 2 without remainder, are called even: a = 2n, n ∈ N.
The remaining numbers are called odd: b = 2n + 1, n ∈ N.
This is a summary of the topic "Integers. Signs of divisibility". To continue, select next steps:
- Go to next summary:
This article is about finding the greatest common divisor (GCD) two and more numbers. First, let's look at the Euclid algorithm; it allows you to find the gcd of two numbers. After this, we will focus on a method that allows us to calculate the gcd of numbers as the product of their common prime factors. Next, we will look at finding the greatest common divisor of three or more numbers, and also give examples of calculating the gcd of negative numbers.
Page navigation.
Euclidean algorithm for finding GCD
Note that if we had turned to the table of prime numbers from the very beginning, we would have found out that the numbers 661 and 113 are prime numbers, from which we could immediately say that their greatest common divisor is 1.
Answer:
GCD(661, 113)=1 .
Finding GCD by factoring numbers into prime factors
Let's consider another way to find GCD. The greatest common divisor can be found by factoring numbers into prime factors. Let's formulate a rule: GCD of two integers positive numbers a and b equal to the product all common prime factors found in the prime factorizations of numbers a and b.
Let's give an example to explain the rule for finding GCD. Let us know the decompositions of the numbers 220 and 600 into prime factors, they have the form 220=2·2·5·11 and 600=2·2·2·3·5·5. General simple factors The numbers involved in the expansion of the numbers 220 and 600 are 2, 2 and 5. Therefore, GCD(220, 600)=2·2·5=20.
Thus, if we factor the numbers a and b into prime factors and find the product of all of them common factors, then this will find the greatest common divisor of the numbers a and b.
Let's consider an example of finding GCD according to the stated rule.
Example.
Find the greatest common divisor of the numbers 72 and 96.
Solution.
Let's factor the numbers 72 and 96 into prime factors: 
That is, 72=2·2·2·3·3 and 96=2·2·2·2·2·3. Common prime factors are 2, 2, 2 and 3. Thus, GCD(72, 96)=2·2·2·3=24.
Answer:
GCD(72, 96)=24 .
In conclusion of this paragraph, we note that the validity of the above rule for finding GCD follows from the property of the greatest common divisor, which states that GCD(m a 1 , m b 1)=m GCD(a 1 , b 1), where m is any positive integer.
Finding the gcd of three or more numbers
Finding the greatest common divisor of three or more numbers can be reduced to sequential finding GCD of two numbers. We mentioned this when studying the properties of GCD. There we formulated and proved the theorem: the greatest common divisor of several numbers a 1, a 2, …, a k equal to the number d k , which is found by sequentially calculating GCD(a 1 , a 2)=d 2 , GCD(d 2 , a 3)=d 3 , GCD(d 3 , a 4)=d 4 , …, GCD(d k- 1 , a k)=d k .
Let's see what the process of finding the gcd of several numbers looks like by looking at the solution to the example.
Example.
Find the greatest common factor of four numbers 78, 294, 570 and 36.
Solution.
In this example, a 1 =78, a 2 =294, a 3 =570, a 4 =36.
First, using the Euclidean algorithm, we determine the greatest common divisor d 2 of the first two numbers 78 and 294. When dividing, we obtain the equalities 294=78·3+60; 78=60·1+18 ; 60=18·3+6 and 18=6·3. Thus, d 2 =GCD(78, 294)=6.
Now let's calculate d 3 =GCD(d 2, a 3)=GCD(6, 570). Let's apply the Euclidean algorithm again: 570=6·95, therefore, d 3 = GCD(6, 570)=6.
It remains to calculate d 4 =GCD(d 3, a 4)=GCD(6, 36). Since 36 is divisible by 6, then d 4 = GCD(6, 36) = 6.
Thus, the greatest common divisor of the four given numbers is d 4 =6, that is, gcd(78, 294, 570, 36)=6.
Answer:
GCD(78, 294, 570, 36)=6 .
Factoring numbers into prime factors also allows you to calculate the gcd of three or more numbers. In this case, the greatest common divisor is found as the product of all common prime factors of the given numbers.
Example.
Calculate the gcd of the numbers from the previous example using their prime factorizations.
Solution.
Let's factor the numbers 78, 294, 570 and 36 into prime factors, we get 78=2·3·13, 294=2·3·7·7, 570=2·3·5·19, 36=2·2·3· 3. The common prime factors of all these four numbers are numbers 2 and 3. Hence, GCD(78, 294, 570, 36)=2·3=6.
Definition. The largest natural number by which the numbers a and b are divided without remainder is called greatest common divisor (GCD) these numbers.
Let's find the greatest common divisor of the numbers 24 and 35.
The divisors of 24 are the numbers 1, 2, 3, 4, 6, 8, 12, 24, and the divisors of 35 are the numbers 1, 5, 7, 35.
We see that the numbers 24 and 35 have only one common divisor - the number 1. Such numbers are called mutually prime.
Definition. Natural numbers are called mutually prime, if their greatest common divisor (GCD) is 1.
Greatest Common Divisor (GCD) can be found without writing out all the divisors of the given numbers.
Factoring the numbers 48 and 36, we get:
48 = 2 * 2 * 2 * 2 * 3, 36 = 2 * 2 * 3 * 3.
From the factors included in the expansion of the first of these numbers, we cross out those that are not included in the expansion of the second number (i.e., two twos).
The factors remaining are 2 * 2 * 3. Their product is equal to 12. This number is the greatest common divisor of the numbers 48 and 36. The greatest common divisor of three or more numbers is also found.
To find greatest common divisor
2) from the factors included in the expansion of one of these numbers, cross out those that are not included in the expansion of other numbers;
3) find the product of the remaining factors.
If all given numbers are divisible by one of them, then this number is greatest common divisor given numbers.
For example, the greatest common divisor of the numbers 15, 45, 75 and 180 is the number 15, since all other numbers are divisible by it: 45, 75 and 180.
Least common multiple (LCM)
Definition. Least common multiple (LCM) natural numbers a and b is the smallest natural number that is a multiple of both a and b. The least common multiple (LCM) of the numbers 75 and 60 can be found without writing down the multiples of these numbers in a row. To do this, let's factor 75 and 60 into prime factors: 75 = 3 * 5 * 5, and 60 = 2 * 2 * 3 * 5.
Let's write down the factors included in the expansion of the first of these numbers, and add to them the missing factors 2 and 2 from the expansion of the second number (i.e., we combine the factors).
We get five factors 2 * 2 * 3 * 5 * 5, the product of which is 300. This number is the least common multiple of the numbers 75 and 60.
They also find the least common multiple of three or more numbers.
To find least common multiple several natural numbers, you need:
1) factor them into prime factors;
2) write down the factors included in the expansion of one of the numbers;
3) add to them the missing factors from the expansions of the remaining numbers;
4) find the product of the resulting factors.
Note that if one of these numbers is divisible by all other numbers, then this number is the least common multiple of these numbers.
For example, the least common multiple of the numbers 12, 15, 20, and 60 is 60 because it is divisible by all of those numbers.
Pythagoras (VI century BC) and his students studied the question of the divisibility of numbers. Number, equal to the sum They called all its divisors (without the number itself) a perfect number. For example, the numbers 6 (6 = 1 + 2 + 3), 28 (28 = 1 + 2 + 4 + 7 + 14) are perfect. The next perfect numbers are 496, 8128, 33,550,336. The Pythagoreans only knew the first three perfect numbers. The fourth - 8128 - became known in the 1st century. n. e. The fifth - 33,550,336 - was found in the 15th century. By 1983, 27 perfect numbers were already known. But scientists still don’t know whether there are odd perfect numbers or whether there is a largest perfect number.
The interest of ancient mathematicians in prime numbers is due to the fact that any number is either prime or can be represented as a product of prime numbers, i.e. prime numbers are like bricks from which the rest of the natural numbers are built.
You probably noticed that prime numbers in the series of natural numbers occur unevenly - in some parts of the series there are more of them, in others - less. But the further we move along number series, the less common prime numbers are. The question arises: is there a last (largest) prime number? The ancient Greek mathematician Euclid (3rd century BC), in his book “Elements”, which was the main textbook of mathematics for two thousand years, proved that there are infinitely many prime numbers, i.e. behind every prime number there is an even greater prime number.
To find prime numbers, another Greek mathematician of the same time, Eratosthenes, came up with this method. He wrote down all the numbers from 1 to some number, and then crossed out one, which is neither prime nor composite number, then crossed out through one all the numbers coming after 2 (numbers that are multiples of 2, i.e. 4, 6, 8, etc.). The first remaining number after 2 was 3. Then, after two, all numbers coming after 3 (numbers that were multiples of 3, i.e. 6, 9, 12, etc.) were crossed out. in the end only the prime numbers remained uncrossed.
