Question

If $a=107,b=13$, using Euclid's division algorithm find the values of ${}^{\prime }{q}^{\prime }$ and ${}^{\prime }{r}^{\prime }$ such that $a=bq+r$.

Answer 1

Apply Euclid’s division lemma, to a and b. So, we find whole numbers, q and r such that a = b*q + r, 0 ≤ r < b.

107 = 13*1 + 94

107 = 13*2 + 81

107 = 13*3 + 68

107 = 13*4 + 55

107 = 13*5 + 42

107 = 13*6 + 29

107 = 13*7 + 16

107 = 13*8 + 3

So, here the set of values of q and r :(q,r) = (1,94), (2,81), (3,68), (4,55), (5,42), (6,29), (7,16), (8,3). We can also find the HCF of 107 and 13. Procedure is as follows:

Step:1 Since 107 > 13 we apply the division lemma to 107 and 13 to get ,

107 = 13 * 8 + 3

Step:2 Since 3 ≠ 0 , we apply the division lemma to 13 and 3 to get ,

13 = 3 * 4 + 1

Step:3 Since 1 ≠ 0 , we apply the division lemma to 3 and 1 to get ,

3 = 1 * 3 + 0

The remainder has now become zero, so our procedure stops. Since the divisor at this Step is 1, the HCF of 107 and 13 is