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, 460 as divident and smaller integer 35 as divisor. Then we use Euclid’s lemma to get:
460 = 35 × 13 + 5
Step 2.) Now consider the divisor 35 and the remainder 5 , and apply the division lemma to get
35 = 5 × 7 + 0
Step 3.)Continue the process till the remainder is zero. The divisor at this stage will be the required HCF.
Answer: HCF = 5
