Euclid’s division algorithm is a technique to compute the Highest Common Factor (HCF) of two given positive integers.
Step 1.) Start with the larger integer, that is, 455 as divident and smaller integer 42 as divisor. Then we use Euclid’s lemma to get:
455 = 42 × 10 + 35
Step 2.) Now consider the divisor 42 and the remainder 35 , and apply the division lemma to get
42 = 35 × 1 + 7
Step 3.)Continue the process till the remainder is zero. The divisor at this stage will be the required HCF.
35 = 7 × 5 + 0
Answer: HCF = 7
