HCF by Elucid's Division Lemma Method

Elucid's Division Lemma Method

Prime Factorisation Method

Successive Division Method

This method of division says that, Given positive integers a and b, there exist unique integers q and r satisfying a = bq + r, where: a is dividend, b is divisor, q is quotient and r is remainder r is > or equal to 0 b > r a > b Now, if r = 0, b is the HCF of given positive integers a and b. Let's understand this method with the help of following examples: Example 1: Find HCF of 24 and 18 Answer: Using Elucid's Divsion Lemma theorem i.e.: a = bq + r here let's take: a = 24, b = 18 and on adding the values we get: 24 = 18 X 1 + 6 Since r is not equals to zero, repeat the process i.e. Take 18 as dividend, 6 as divisor and we get: 18 = 6 X 3 + 0 since r = 0, therefore 6 is the HCF of 24 and 18 Example 2: Find HCF of 420 and 130 Answer: Using Elucid's Division Lemma theorem i.e.: a = bq + r here let's take: a = 420, b = 130 and on adding the values we get: 420 = 130 X 3 + 30 Since r is not equals to zero, repeat the process i.e. Take 130 as dividend, 30 as divisor and we get: 130 = 30 X 4 + 10 Since r is not equals to zero, repeat the process i.e. Take 30 as dividend, 10 as divisor and we get: 30 = 10 X 3 + 0 since r = 0, therefore 10 is the HCF of 24 and 18