2 a Show that 7 and 16 are coprime b You are given an unlimi

2. (a) Show that 7 and 16 are co-prime.

(b) You are given an unlimited supply of water, a large container, and two jugs whose

capacities are 7 L and 16 L, respectively. How would you put exactly one liter of

water in the container?

[5 marks]

a. 2 nos are coprime when gcd of the 2 nos=1

ie a,b are coprime when (a,b)=1 where (a,b) = gcd of a,b

there is no common factor for 7,16 othere than 1

hence (7,16)=1 the 2 nos are coprime

when a,b are coprime there exist 2 integers x,y such that ax+by=1 where x,y are in Z

here 7, 16 are coprime . hence there exist 2 integers x,y such that 7x+16y=1

the above eqn satisfied for x= 7 and y= - 3 ( 49 -48=1)

using the values of x,y the given problem can be solved

Pour 7 L water 7 times ( using the 1st jug ) in the big container

remove 16 L water 3 times ( using the 2nd jug ) from the big container

THE SOLUTION IS NOT UNIQUE

other possibilities are : x= - 9 , y=4 ( 7x+16y= -63+64=1)