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: Easy Linear Equation question

  1. Feb 6, 2010 #1
    1. The problem statement, all variables and given/known data

    I just have a general question.

    Suppose a,b and c are integers with a and b not both 0. There exists d=gcd(a,b) and ax+by=c.
    From this I know that d|a and d|b but how do I know that there exists x,y such that d|(ax+by) where ax+by does not equal d and d|c ?

    I cannot simply state that because d|ax and d|by, it must divide their sum. Or can I?

    Last edited: Feb 6, 2010
  2. jcsd
  3. Feb 6, 2010 #2
    If d|a and d|b, then d|(ax + by) for all integers x and y. This is very easy to see in different notation: If d|a and d|b, then a = a'd and b = b'd and ax + by = a'dx+b'dy = d(a'x+b'd).

    If d|(ax +by) and ax+by=c, then d|c obviously enough.

    However, it is possible that d = c. In fact, the Extended Euclidean Algorithm will produce an x and y such that ax + by = gcd(a,b).
  4. Feb 6, 2010 #3
    Thanks owlpride, that's what I was thinking but I just needed some reassurance.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook