Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proving a Diophantine equation.

  1. Oct 20, 2007 #1
    Prove that the Diophantine equation ax+by+cz+d has an integer solution if and only if the gcd(a,b,c) divides d.

    Got this on my homework for my proofs class. Help would be greatly appreciated.

  2. jcsd
  3. Oct 21, 2007 #2
    Start with a simpler equation, ax+d, and then try to add the other terms one by one.
  4. Oct 22, 2007 #3
    I goofed...it is actually ax+by+cz=d...does that make a difference?
  5. Oct 22, 2007 #4
    the Linear Equation Theorem says that the equation ax + by = gcd(a, b) always has a solution(s, u) in integers, and this solution can be found by the Euclidean algorithm, which we use to compute the gcd of a and b.
  6. Oct 23, 2007 #5
    I figured it out....thanks for the help
  7. Oct 24, 2007 #6


    User Avatar
    Science Advisor

    Well, yes! It's an equation! ax+ by+ cz+ d isn't an equation.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook