Dismiss Notice
Join Physics Forums Today!
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

  1. Apr 23, 2006 #1
    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. jcsd
  3. Apr 23, 2006 #2

    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