Using Euclid’s division algorithm, find the H.C.F. of 135 and 714.

We are asked to find the H.C.F. (Highest Common Factor) of 135 and 714 using Euclid's division algorithm.

Step 1: Apply Euclid's division algorithm

Euclid's division algorithm states that for two positive integers a and b, where a > b, we can write:

a = b * q + r, where:

q is the quotient
r is the remainder
We continue this process by dividing the divisor (b) by the remainder (r) until the remainder is 0. The divisor at that stage will be the H.C.F.

Step 2: Start with 714 and 135

First, divide 714 by 135:

714 ÷ 135 = 5 (quotient) So, the remainder is:

714 - 135 * 5 = 714 - 675 = 39

Now, we have:

714 = 135 * 5 + 39

Step 3: Divide 135 by 39

Next, divide 135 by 39:

135 ÷ 39 = 3 (quotient) So, the remainder is:

135 - 39 * 3 = 135 - 117 = 18

Now, we have:

135 = 39 * 3 + 18

Step 4: Divide 39 by 18

Next, divide 39 by 18:

39 ÷ 18 = 2 (quotient) So, the remainder is:

39 - 18 * 2 = 39 - 36 = 3

Now, we have:

39 = 18 * 2 + 3

Step 5: Divide 18 by 3

Next, divide 18 by 3:

18 ÷ 3 = 6 (quotient) So, the remainder is:

18 - 3 * 6 = 18 - 18 = 0

Now, we have:

18 = 3 * 6 + 0

Since the remainder is now 0, the divisor at this stage is 3.

Step 6: Conclusion

The H.C.F. of 135 and 714 is 3.