1. PF Contest - Win "Conquering the Physics GRE" book! Click Here to Enter
    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!

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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Threads - Easy Linear Equation Date
Easy Bases Linear Algebra Nov 24, 2011
Easy Bases Linear Algebra Nov 22, 2011
Linear Algebra Problems (Easy?) Feb 17, 2010
Linear Algebra - Is this set a vector space [Easy?] Oct 19, 2009
Easy linear algebra question Dec 5, 2005