Greatest Common Divisor

Look at the factors of the numbers $24$ and $36$:

• $Div(24) = \{1, 2, 3, 4, 6, 8, 12, 24\}$

• $Div(36) = \{1, 2, 3, 4, 6, 9, 12, 18, 36\}$

From these lists:

1. a) Write down the common factors of both numbers.
2. b) Identify the highest of these common factors. What do we call this number?

Two numbers are called co-prime if their only common factor is $1$. Check whether the following pairs of numbers are co-prime by calculating their highest common factor:

1. a) $8$ and $15$
2. b) $14$ and $21$
3. c) $9$ and $20$

In an 8th grade class, there are $24$ male students and $16$ female students. The PE teacher wants to form equal-sized teams, as large as possible, so that each team contains only boys or only girls.

1. a) How many students will there be in each team?
2. b) How many boys' teams and how many girls' teams will be formed?

Calculate the greatest common divisor (g.c.d.) of the following numbers using the prime factorization method (remember: you take the common factors raised to the lowest exponent):

1. a) $12$ and $18$
2. b) $20$ and $30$
3. c) $15$ and $25$

Find the Highest Common Factor of the following groups of numbers using prime factorisation:

1. a) $m.c.d.(120, 150)$
2. b) $m.c.d.(72, 108, 144)$
3. c) $m.c.d.(45, 60, 105)$

Remember to first express each number as a product of its prime factors and then select the common factors raised to the lowest power.

The Euclidean algorithm is an ancient and effective method for finding the $m.c.d.$ of two numbers using successive division. It consists of dividing the larger number by the smaller one; if the remainder is not zero, the divisor is divided by the remainder, and so on until the remainder is zero. The last divisor used is the $m.c.d.$

Use this method to find the $m.c.d.(525, 225)$. Check the result by doing the usual prime factorisation afterwards.

Use the Euclidean algorithm to find the $m.c.d.(2\,310, 1\,485)$. Once found, state whether the numbers are coprime and justify your answer based on the divisors obtained during the algorithm process.

It is known that the product of two natural numbers is $2160$ and that their lowest common multiple ($m.c.m.$) is $180$. Using the relationship between the product of two numbers, their $m.c.d.$ and their $m.c.m.$, find out what the Highest Common Factor of those numbers is.

We have two natural numbers $A$ and $B$ such that their $m.c.d.(A, B) = 15$. If we multiply the number $A$ by $12$ and the number $B$ by $12$, what will be the new highest common factor of the resulting numbers? Justify your answer by applying the properties of factors.

Find two natural numbers, which we will call $x$ and $y$, knowing that their product is $x \times y = 11\,250$ and that their lowest common multiple is $m.c.m.(x, y) = 750$.

Determine all pairs of natural numbers whose sum is $168$ and whose highest common factor is $m.c.d.(a, b) = 24$.

Help: If the HCF is 24, you can write the numbers as $a = 24 \times p$ and $b = 24 \times q$, where $p$ and $q$ must be coprime.

At an adventure camp in the Sierra Madre, the instructors have two climbing ropes: one measures $20$ meters and the other $28$ meters. They want to cut them into equal pieces of the maximum possible length, with no rope left over. How long should each piece be?

We want to decorate a wall in the music room measuring $120$ cm high by $180$ cm wide using square pieces of card. If we want the pieces of card to be as large as possible and cover the wall exactly without having to cut them:

1. a) What length should each side of the pieces of card be?
2. b) How many pieces of card will we need in total?

For the school sports day tournament, $48$ 1st ESO students and $60$ 2nd ESO students have signed up. Teams are to be formed with the same number of people, without mixing students from different year groups, making the teams as large as possible.

1. a) How many students will there be in each team?
2. b) How many 1st ESO teams will there be in total? And 2nd ESO?

A food bank has received $210$ tins of tuna, $126$ packets of rice and $84$ jars of pulses. They want to prepare the maximum possible number of identical aid boxes containing all three types of food, with nothing left over.

1. a) How many aid boxes will they be able to prepare?
2. b) How many items of each type will there be in each box?

A logistics company wants to transport three types of goods in identical cubic containers, as large as possible, to make the most of the space in a large cargo warehouse. The quantities of goods are measured by volume:

• Technology boxes: $1\,512$ $m^3$

• Food boxes: $1\,848$ $m^3$

• Textile boxes: $1\,260$ $m^3$

If each container must be filled with a single type of good and no space can be left over in any of them, what must the volume of each cubic container be? How many textile containers will there be in the warehouse?

A marine wildlife rescue center has received a donation of three heavy-duty hoses to clean the tanks. The lengths of the hoses are $156$ meters, $144$ meters and $108$ meters.

They want to cut them into pieces of equal length, with nothing left over, to distribute them among different volunteer teams. The head of the center sets the condition that the pieces must be as long as possible, but for safety reasons, no piece can measure more than $15$ meters.

What length should each piece be to meet all conditions? How many volunteers will receive a hose?