1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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: Number theory - gcd and linear diophantine equations

  1. Aug 15, 2009 #1
    1. The problem statement, all variables and given/known data

    Suppose that gcd(a, b) = 1 with a, b > 0, and let x0, y0 be any integer solution to the equation ax + by = c. Find a necessary and sufficient condition, possibly depending on a, b, c, x0, y0 that the equation have a solution with x > 0 and y > 0.

    2. Relevant equations

    3. The attempt at a solution
    I'm pretty lost. Can anyone point me in the right direction?
  2. jcsd
  3. Aug 16, 2009 #2
    Well, if one of [tex] x_0 [/tex] or [tex] y_0 [/tex] is negative, then you have to look for another solution [tex] (x_1, y_1) [/tex] with [tex] x_1, y_1 > 0 [/tex]. By subtracting equations, you get [tex] a(x_1 - x_0) + b(y_1 - y_0) = 0 [/tex]. Can you see why this equation implies that [tex] x_1 - x_0 = kb [/tex] and [tex] y_1 - y_0 = -ka [/tex] for some integer [tex] k [/tex]? Once you do, your problem is reduced to a search for a value of [tex] k [/tex] such that [tex] x_0 + kb > 0 [/tex] and [tex] y_0 - ka > 0 [/tex]. You should be able to take it from here.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook