Euclid's Algorithm

A pair of positive integers (x, y) satisfies the equation 31x + 29 y = 1125. What is x + y? ans - x+y=37

31x+29y=1125

31x+29y=1 we get for x=-14 and y=15

general solution is x =-14*1125+29*t y = 15*1125-31t

14*1125/29 <= t<= 15*1125/31 t is an integer
we get t as 544

plug in t back in the equations above
to get x =26 and y=11
so x+y=37

Get online teaching jobs. Work from the comfort of your home, be an online tutor with TutorVista.com. Know more about teaching jobs.