Use Euclid’s Division Algorithm to Find the HCF and LCM of 135 and 225

Use Euclid’s Division Algorithm to Find the HCF and LCM of 135 and 225

Before finding the HCF and LCM of 135 and 225 using Euclid’s Division algorithm it is important to understand the meaning of Euclid’s algorithm. Euclid’s algorithm is a method to find HCF or also known as the Highest Common Factor of the two integers that are positive in nature. The Highest Common Factor or the HCF of the given two positive numbers let’s say a and b happens to be the largest positive number d that divides the a and b.

As per the division algorithm of Euclid if two integers (positive in nature) exist, let’s say a and b then there also happens to be the presence of two unique numbers q and r. These unique numbers q and r fulfil the rule, a=bq+r with the condition of 0 lesser or equal to r and it is lesser or equal to b. This rule suggests that when a and b are divided, the remainder happens to be zero.

Steps:

225, 135.

225 >135.

Using Euclid equation we get,

225 = 135*1 + 90

In the above equation, the remainder is not zero thus the application of the division lemma

135 = 90*1 + 45

Applying the division lemma again to 90 and 45

90 = 45*2 + 0

Thus, the remainder is 0 and the divisor is Highest Common Factor or HCF

Therefore the HCF of 225 and 135 is 45.