Question

If d is HCF to 40 and 65, find the value of integers x and y which satisfy d = 40 x + 65 y.

Answer 1

Hint: First look at the definition of the highest common factor. Apply Prime factorization to 40, 65. Find the largest possible common factor between these 2. Now apply Euclid’s division lemma on 40, 65 till you get the highest common factor on the left-hand side. By this, you get the relation between highest common factors 40 and 65. Now compare this relation with the given equation to get the values of x, y. This will be your result. Euclid’s division lemma is given by:
Dividend = (Divisor) (quotient) + Remainder.

Complete step-by-step solution -
Highest common factor: Mathematically, the greatest number which divides both given numbers is called the highest common factor. It is called the greatest common divisor.
Euclid’s Division Lemma: A Lemma is a proven statement used for proving other statements. If we have 2 positive integers a, b these would be whole numbers q, r satisfying a = bq +r.
We need to find the Highest common factor of 40, 65: -
Prime factorization of 40 gives the numbers as follows:
\[\Rightarrow 40=5\times {{2}^{3}}\]
Prime factorization of 65 gives the numbers as follows: -
\[\Rightarrow 65=5\times 13\]
From these two equations, we can say the highest common factor as:
HCF (40, 65) = 5.
By applying Euclid’s division lemma to 40, 65 we get:
\[\Rightarrow 65=40\times 1+25\] ----- (1)
By applying Euclid’s lemma to pairs of (40, 25), (25, 15), (15, 10), (10, 15) we get:
\[\Rightarrow 40=25\times 1+15\] ----- (2)
\[\Rightarrow 25=15\times 1+10\] ----- (3)
\[\Rightarrow 15=10\times 1+5\] ------ (4)
\[\Rightarrow 10=5\times 2+0\] ------- (5)
Equations (1), (2), (3) can be also written in the form of:
\[\Rightarrow 65-40\times 1=25\] ----- (6)
\[\Rightarrow 40-25\times 1=15\] ----- (7)
\[\Rightarrow 25-15\times 1=10\] ----- (8)
\[\Rightarrow 15-10\times 1=5\] ------ (9)
By equation (5) we have: 5 = 15 –10
We can write it as \[5=15\times 2-25\times 1\] by using the above equations
Substituting equation (7) we get: 5 = $(40 - 25)2 – 25 $
By substituting equation (6) we get: 5 = $(40 – 65 + 40)2 – 65 + 40$
By simplifying the equation, we get \[5=40\times 2-65\times 2+40\times 2-65+40\]
By simplifying more, we get the equation \[5=40\times 5-65\times 3\]
By comparing this equation to the equation $d = 40x + 65y$
We get values of $(x, y)$ to be $(5, -3)$.
Therefore x value is 5 and y value is -3.

Note: Be careful while applying Euclid’s lemma because you will use each of the questions in further steps. Generally, students make mistakes at equation (5) when you get 0 you must stop. That will take you to the next level of writing HCF in terms of the 2 numbers. Students forget that constant 2 which will make the whole answer go wrong.