# Homework Help: Diophantine Equation and Euclid's algorithm

1. Apr 23, 2006

### Spruance

Given that x and y are positive integers such that:

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

2. Apr 23, 2006

### abercrombiems02

13x +4y = 100 and x and y are integers

first off if this is to be true then x HAS to be a positive even number.
also notice that 13*8 is 80+24=104 therefore x can only be 2 4 or 6.

Next, 13 and 4 have no common factors therefore we must choose that x is equal to 4 for it to be guaranteed that y is also an integer. So if x = 4, then y is 100/4 - 13 = 12.

Hope this helps!

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook