Question

Find HCF of 65 and 117 and find a pair of integral values of m and n such that HCF = 65m + 117n.

Answer 1

Hint: In this question, we are given two numbers and we have to find highest common factor of them. Also we have to find two numbers such that linear combination of their sum can be equal to highest common factor obtained. For this, we will use Euclid's division algorithm and find the highest common factor. Using steps involved in the Euclid division algorithm, we will alter the values and obtain our required value. Euclid's division algorithm is given as:
\[\text{Dividend}=\text{Divisor}\times \text{Quotient}+\text{Remainder}\]

Complete step by step answer:
Here, we are given two numbers as 65 and 117. By Euclid's division algorithm, we know that,
\[\text{Dividend}=\text{Divisor}\times \text{Quotient}+\text{Remainder}\]
So, let's divide 117 by 65 to get quotient and remainder. Here, dividend is 117 and divisor is 65, we get
\[117=65\times 1+52\cdots \cdots \cdots \left( 1 \right)\]
Here 1 is the quotient which when multiplied by 65 leaves remainder 52 to be equal to 117. Now, divisor of our previous equation will be divided by the remainder, so dividend = 65, divisor = 52 and quotient and remainder will become 1 and 13 respectively. Therefore,
\[65=52\times 1+13\cdots \cdots \cdots \left( 2 \right)\]
Since, remainder is 13 not zero, so we will continue this procedure. Now, dividend will be 52 and divisor be 13. We get:
\[52=13\times 4+0\cdots \cdots \cdots \left( 3 \right)\]
Now, remainder is found 0. Therefore, divisor of last equation will be required highest common factor.
Therefore, HCF of 65, 117 will be 13.
Now using (1), (2) and (3) we will obtain values of m and n such that 13 = 65m + 117n.
From (2) value of 13 will be,
\[13=65+52\times \left( -1 \right)\]
From (1) value of 52 can be put in above equation we get:
\[13=65+\left( 117-65\times 1 \right)\times \left( -1 \right)\]
Let's rearrange this equation we get:
\[\begin{align}
  & 13=65+\left( 117\left( -1 \right)+65 \right) \\
 & \Rightarrow 13=65\times 2+117\times \left( -1 \right) \\
\end{align}\]

Comparing 13 = 65m + 117n, we get m = 2 and n = -1.
Hence, these are our required values of variables.

Note: Students can also calculate the highest common factor using the prime factorization method but problems will arise when we need to find values of m and n. For that, we can use a hit and trial method too. While dealing with negative and positive values, take care not to mix up the signs. Highest common factor can also be found using a long division method.