Highest common factor

Find all the divisors of the numbers $12$ and $18$. Then, state which are the common divisors and point out which of them is the Greatest Common Divisor (GCD).

You can use a diagram like the one in the figure: write the divisors of each number in each circle and, in the area where they overlap, the ones that are common.

Work out in your head the $MCD$ of the following pairs of numbers. These are small numbers where you can identify the highest common factor at a glance:

1. a) $MCD(4, 8)$
2. b) $MCD(5, 10)$
3. c) $MCD(7, 14)$
4. d) $MCD(10, 20)$

What do all these results have in common?

Look at the prime factorisations of these two numbers and find their $MCD$:

• $A = 2^{2} \times 3 \times 5$

• $B = 2 \times 3^{2}$

Remember the rule: "For the HCF, we take the common factors raised to the lowest power".

Lucas has to calculate the greatest common divisor of $72$ and $120$. In his notebook, he writes down the prime factorisation as follows:

$72 = 2^3 \times 3^2$

$120 = 2^3 \times 3 \times 5$

$\text{GCD}(72, 120) = 2^3 \times 3^2 \times 5 = 8 \times 9 \times 5 = 360$

When his teacher asks him about the procedure, Lucas argues: “I chose the factors with the highest exponent and also the non-common ones because the rule is called greatest divisor, so the result has to be the largest possible divisor”.

1. a) Without recalculating, explain with reasons why the result $360$ is absurd and impossible as a divisor of $72$ and $120$.
2. b) What mathematical concept did Lucas actually calculate by mistake when applying that rule?
3. c) Correct Lucas's solution: explain the correct criterion for selecting prime factors when calculating the GCD, and find the correct value of $\text{GCD}(72, 120)$.

You are going to calculate the greatest common divisor of two numbers: $48$ and $72$.

1. a) Before operating, reason about the bounds of the result: could the GCD be equal to $96$? And could it be equal to $48$? Explain why the GCD of two numbers can never be greater than the smaller of them.
2. b) Knowing that both numbers are even (divisible by $2$) and that the sum of the digits of both is a multiple of $3$ (divisible by $3$), estimate which of the following four values is the most reasonable candidate to be the GCD before factorising: $5$, $12$, $24$, or $36$. Justify why you rule out the other three.
3. c) Factorise $48$ and $72$ into prime factors, calculate $M.C.D.(48, 72)$ accurately, and check whether your estimation from the previous section was correct.

Calculate the Highest Common Factor ($M.C.D.$) of the following sets of numbers using prime factorisation:

1. a) $48$ and $72$
2. b) $30, 45$ and $60$
3. c) $120$ and $150$

Look at the following prime factorisations of three numbers and, without performing the multiplications, state their $\text{HCF}$:

$A = 2^3 \times 3^2 \times 5$

$B = 2^2 \times 3^3$

$C = 2^2 \times 3^2 \times 7$

Make up two distinct natural numbers, $a$ and $b$, such that the following condition is met:

$M.C.D.(a, b) = 12$

Reason your answer by showing the prime factorisation of the chosen numbers.

To calculate the greatest common divisor, you have two main strategies:

• Method 1 (Listing divisors): Write all the divisors of each number, identify the ones they have in common, and choose the largest.

• Method 2 (Prime factorisation): Decompose into prime factors and multiply only the common factors with their lowest exponent.

You are given two calculation situations:

• Case A: Find $M.C.D.(15, 25)$.

• Case B: Find $M.C.D.(210, 294)$.

1. a) For Case A, which method do you choose as being more direct and requiring fewer steps? Apply it and find the result.
2. b) For Case B, explain in detail why Method 1 would be long, tedious, and carry a high risk of forgetting divisors compared to Method 2.
3. c) Solve Case B applying Method 2 step by step: show the factorisation of $210$ and $294$, state which factors you select, and calculate $M.C.D.(210, 294)$.

We know that the Greatest Common Divisor of two numbers is $12$ and that one of those numbers is $48$. If the other number is greater than $50$ but less than $70$:

1. a) Find what that second number is.
2. b) Justify your answer using prime factorisation.

Two numbers are said to be coprime if their only common factor is $1$. Check whether the following pairs of numbers are coprime by calculating their $M.C.D.$:

1. a) $14$ and $15$
2. b) $22$ and $33$
3. c) $21$ and $25$

A pharmaceutical laboratory needs to package two types of tablets, $A$ and $B$, into identical blister packs. We do not know the exact quantity of tablets of each type, but control records indicate that they strictly meet the following five conditions:

1. Both are two-digit numbers ($A < 100$ and $B < 100$).

2. Their greatest common divisor is $15$: $M.C.D.(A, B) = 15$.

3. Neither of the two numbers is a multiple of the other (that is, $A$ does not divide $B$ and $B$ does not divide $A$).

4. The quantity $A$ is an even number and the quantity $B$ is an odd number.

5. The sum of both numbers is exactly $135$ pills ($A + B = 135$).

1. a) If $M.C.D.(A, B) = 15$, we can write $A = 15 \times a$ and $B = 15 \times b$. Deduce what essential mathematical condition the numbers $a$ and $b$ must satisfy with respect to each other, and what the sum $a + b$ must equal.
2. b) Find the exact values of $A$ and $B$, checking that all five conditions are met.
3. c) Prove with reasoning why no other pair of numbers exists that satisfies all the conditions in the statement.

During a classroom debate on numerical properties, two students make the following statements:

• Aoife states: “If two numbers are composite (that is, neither of them is prime), it is impossible for them to be coprime, because having several divisors they will always share one greater than $1$”.

• Cian states: “If we take any two numbers that are coprime, adding $1$ to both numbers will always result in a new pair that is still coprime”.

1. a) Analyse Aoife's statement. Recall the definition of “coprime numbers” and prove that her statement is false by providing a counterexample with two composite numbers less than $30$. Calculate their GCD to justify it.
2. b) Analyse Cian's statement. Prove that his statement is also false by finding a pair of numbers $x$ and $y$ that are coprime ($\text{GCD}(x, y) = 1$), but such that $x + 1$ and $y + 1$ have a common divisor greater than $1$.
3. c) Reason and prove the following theoretical property: if we take any two consecutive natural numbers ($n$ and $n + 1$), what is always their GCD? (Hint: think about what relationship exists between the difference of two numbers and the divisors they can share).

In the technology workshop, the students have two wooden battens measuring $36$ cm and $48$ cm in length. They need to cut them into pieces of the same length, with this length being the maximum possible.

1. a) What will be the length of each piece?
2. b) How many pieces will they get in total from the two battens?

In a library, they want to organise $45$ adventure books and $60$ science fiction books on shelves so that each shelf has the same number of books and this number is the maximum possible.

1. a) How many books will they put on each shelf?
2. b) How many shelves will they use for the adventure books and how many for the science fiction books?

At the school, a day of group activities has been organized. There are $54$ students in 1st Year and $42$ students in 2nd Year. The students are to be split into teams so that each team consists only of students from the same year (students from 1st and 2nd year are not mixed). All teams must have exactly the same number of people, and that number must be as large as possible without anyone being left over.

1. a) How many students will there be in each team?

1. b) How many teams of 1st Year and how many teams of 2nd Year will be formed?

For a food bank, a supermarket donates $36$ tins of pulses, $48$ cartons of milk and $60$ bags of rice. They want to prepare the maximum possible number of identical bags to distribute, such that each bag contains the same number of items of each type.

1. a) What is the maximum number of bags they can prepare?
2. b) What will each bag contain?

In a cooperative oil mill in Kilkenny, the harvest has finished with two special tanks of extra virgin olive oil: one contains $420$ litres of the Picual variety and the other contains $300$ litres of the Arbequina variety. To market it in gourmet shops, they want to bottle all the oil into identical jugs of the greatest possible capacity in whole litres, so that all the jugs are identical, no variety is mixed in the same container, and no oil is left over in the tanks.

1. a) Model the problem mathematically: identify which divisibility concept represents the capacity of the jugs and calculate how many litres each one must contain.
2. b) How many jugs of Picual oil and how many of Arbequina oil will be filled in total?
3. c) If weight handling regulations in transport state that no jug can exceed $25$ litres, is the previous distribution valid? If it is not, use the common divisors of both quantities to determine what the largest allowed capacity per jug would be that still meets all the original conditions.

A street artist wants to design a mural on a rectangular wall measuring $210$ cm high by $165$ cm wide. For her design, she wants to divide the whole wall into equal squares, such that these are as large as possible and she does not have to cut any pieces.

1. a) What must be the length of the side of each square to cover the entire wall?
2. b) How many squares will the mural have in total?

We are looking for the largest possible number that, when dividing the numbers $159$ and $195$, leaves a remainder of $3$ units in both cases. Reason through the steps you follow to find it using the concept of Highest Common Factor.

A gardener wants to surround a rectangular vegetable patch $90$ metres long and $126$ metres wide with fence posts. The owner of the patch has asked him to place a post at each corner and for the distance between consecutive posts to always be the same and as large as possible.

1. a) What distance should he leave between each post?
2. b) How many posts will he need in total to surround the entire perimetre of the vegetable patch?

Topic challenge. Organise a charity donation drive at home!

1. Collection and criteria: Count two types of non-perishable food items from your pantry (for example, $A$ cans and $B$ cartons, with $A, B \ge 18$). Identify their factors and immediate multiples, and check if they meet the divisibility rules for $2$, $3$, and $5$.

2. PFD, GCD, and LCM: Find the prime factor decomposition (PFD) of $A$ and $B$. Find the $\gcd(A, B)$ to create the maximum number of identical packs with no waste, and the $\operatorname{lcm}(A, B)$ to anticipate every how many days both products will run out at the same time (if you use one unit of each per day and restock the same amount when it runs out).

3. Equations and integer division: Set up and solve a linear equation to calculate how many additional cans $x$ you need to buy to fill $6$ full boxes: $A + x = 6 \times k$ (choosing the nearest higher multiple). Verify the integer division algorithm ($D = d \times q + r$) and calculate the budget if each can costs $\text{€}\ 1.25$.

4. Final product: Design a spreadsheet with the data tables, divisibility formulas, and a reasoned proposal for the food bank.

Assessment criteria:

• Rigorous application of divisibility rules and prime factor decomposition (PFD).

• Contextualised calculation of $\gcd$ and $\operatorname{lcm}$.

• Algebraic formulation of the equation and correct use of integer division.

• Structure, formulas, and clarity in the spreadsheet.