Question

Using Euclid's division algorithm, find the H.C.F. of 504 and 1188.

Hint:

To keep the process organized, always remember the pattern: the divisor of the current step becomes the dividend of the next step, and the remainder of the current step becomes the divisor of the next step.

Answer 1

Step 1: Understanding the Concept:
Euclid's division algorithm is a method for finding the Highest Common Factor (H.C.F.) of two integers. It is based on the principle that the H.C.F. of two numbers does not change if the larger number is replaced by its difference with the smaller number. The algorithm uses the division lemma \(a = bq + r\), where the H.C.F. of \(a\) and \(b\) is the same as the H.C.F. of \(b\) and \(r\).

Step 2: Detailed Explanation:
Let \(a = 1188\) and \(b = 504\). We apply the division lemma repeatedly until the remainder becomes 0.

Step 1: Divide 1188 by 504. \[ 1188 = 504 \times 2 + 180 \] The remainder is 180. Now, the new dividend is 504 and the new divisor is 180.

Step 2: Divide 504 by 180. \[ 504 = 180 \times 2 + 144 \] The remainder is 144. Now, the new dividend is 180 and the new divisor is 144.

Step 3: Divide 180 by 144. \[ 180 = 144 \times 1 + 36 \] The remainder is 36. Now, the new dividend is 144 and the new divisor is 36.

Step 4: Divide 144 by 36. \[ 144 = 36 \times 4 + 0 \] The remainder is 0. The algorithm stops. The H.C.F. is the last non-zero remainder.

Step 3: Final Answer:
The last non-zero remainder is 36. Therefore, the H.C.F. of 504 and 1188 is 36.