| (i)a = 13, b = 3 (ii)a = 80, b = 8 (iii)a = 125, b = 5 (iv)a = 132, b = 11 |
| THINK AND DISCUSS |
| In questions of above "DO THIS", what is the nature of q and r? |
Theorem-1.1 :(Division Algorithm) :Given positive integers a and b, there exist unique pair of integers q and r satisfying a = bq + r, 0 ≤ r < b.
This result, was first recorded in Book VII of Euclid's Elements. Euclid's algorithm is based on this division algorithm.
Euclid's algorithm is a technique to compute the Highest common factor (HCF) of two given integers. Recall that the HCF of two positive integers a and b is the greatest positive integer d that divides both a and b.
Let us find the HCF of 60 and 100, through the following activity.
| ACTIVITY
Take two paper strips of equal width and having lengths 60 cm, and 100 cm long. Our task is to find the maximum length of a strip which can measure both the strips without leaving any part. Take 60 cm strip and measure the 100 cm strip with it. Cut off the left over 40 cm. Now, take this 40 cm strip and measure the 60 cm strip with it. Cut off the left over 20 cm. Now, take this 20 cm strip and measure the 40cm with it. Since nothing is left over, we may conclude that 20cm strip is the longest strip which can measure both 60 cm and 100 cm strips without leaving any part. |
page no:3