Given that x and y are positive integers such that:(adsbygoogle = window.adsbygoogle || []).push({});

13x + 4y = 100

Then, what is x + y like?

Personally, I found the answer using Euclid's algorithm.

d = gcd(13,4)=1

13 * u + 4 * v = 1

(u, v) = (1,-3)

(x,y) = (100, -300)

13 * (x - 100) = 4 * (y + 300)

(Gauss)

x = 4 * k & y = 13 * k - 1

we set k = 1;

ergo is x = 4 and y = 12

x + y = 4 + 12 = 16

However, my teacher told me that it exist a much easier way to solve the equation. Anyone that know his solution to the problem?

Thanks in advance

**Physics Forums | Science Articles, Homework Help, Discussion**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Diophantine Equation and Euclid's algorithm

**Physics Forums | Science Articles, Homework Help, Discussion**