Let us link the process we followed in the "Activity" to Euclid's algorithm to get HCF of 60 and 100.

When 100 is divided by 60,the remainder is 40

100=(60×1)+4

Now consider the division of 60 with the remainder 40 in the above equation and apply the dision algothrim

60=(40×1)+20

Now consider the divisionof 40 with the remainder 20,and apply the division lemma

40=(20×2)+0

Notice that the remainder has become zero and we cannot proceed any furthure.We claim that the HCF of 60 and 100 is the divisior at this stage,i.e.20.(You can easily verify this by listing all the factors of 60 and 100.)We observe that it is a series of well defined stepss to find HCF of 60 and 100.So,let us state Euclid's algorithrim clearly.

To obtain the HCF of two positive intergers,say c and d with c>d,follow the steps below:

Step 1 :

Apply Euclid's division lemma,to c and d.So, we find unique pair of whole numbers,q and r such that c =dq+r,0

Step 2 :

If r=0,d is the HCF of c and d.If r≠0,apply the divisior lemma to d and r.

Step 3 :

Continue the process till the remainder is zero.The divisior at this stage will be the requried HCF.

This algorithrim works because HCF(c,d)=HCF(d,r)where the symbol HCF(m,n)denotes the HCF of any two positive intergers m and n.

Do this