Highest common factor

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?

You are going to calculate the greatest common divisor of $48$ and $80$, but before applying any algorithm you must anticipate what the solution will look like:

1. a) Estimate: Without decomposing the numbers into prime factors, answer with reasoning:

• Can the result be greater than $48$? Why?

• Knowing that both $48$ and $80$ are even, could the result be an odd number?

• Check mentally whether $10$ could be a common divisor of both. Why is it immediately ruled out?

1. b) Check: Decompose $48$ and $80$ into prime factors, calculate the $\text{gcd}(48, 80)$, and verify whether the value obtained satisfies all the deductions you made in your estimation.

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$

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$

Cian has to calculate the greatest common divisor of $72$ and $120$. After decomposing both numbers into prime factors, he writes in his notebook:

And he concludes: "Since the gcd is the greatest, I choose all the factors that appear raised to their highest exponent: $\text{gcd}(72, 120) = 2^3 \times 3^2 \times 5 = 360$".

1. a) Without doing complex calculations, explain why Cian's result is impossible by reasoning about the meaning of the word "divisor".
2. b) What concept has Cian actually calculated instead of the gcd?
3. c) Explain the correct rule for calculating the gcd from the prime factorizations and find the correct result.

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.

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.

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$.

We are looking for two three-digit natural numbers, $a$ and $b$ (with $a < b$), whose initial values are unknown, but we know that they simultaneously satisfy two conditions:

1. a) Apply the property relating the product of two numbers to their gcd and their lcm to calculate the exact value of the product $a \times b$.
2. b) If we write $a = 18 \times x$ and $b = 18 \times y$, deduce what value the product $x \times y$ must have and reason why $x$ and $y$ must necessarily be coprime (that is, they cannot share any common factor).
3. c) Decompose the product $x \times y$ into prime factors, analyze all possible pairs of factors $(x, y)$ that are coprime, and deduce which are the only values of $a$ and $b$ that satisfy that both have exactly three digits.

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

A council worker wants to tile a rectangular area of a park measuring $24$ metres long by $18$ metres wide. To do this, they will use square tiles that are as large as possible and do not want to cut any.

1. a) Determine the side length of each tile.
2. b) Calculate the total number of tiles needed to cover the entire surface.

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

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 centre sets the condition that the pieces must be as long as possible, but for safety reasons, no piece can measure more than $15$ metres.

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