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

Diophantine and coprime solutions x,y

  1. Nov 13, 2009 #1
    Hi everyone,

    I saw that for the linear diophantine equation [tex]d=ax+by[/tex], where d=(a,b), that x and y must be coprime.

    Why is this? I feel like there are properties of coprime numbers that I am not aware of, because there are a few things like this that I have encountered.

    Any help appreciated :-)

  2. jcsd
  3. Nov 13, 2009 #2


    User Avatar
    Science Advisor

    If x and y are NOT coprime, that is, if x= mu and y= mv for some integers m, u, and v, then the Diophantine equation becomes d= amu+ bmv= m(au+bv). Since the right hand side is divisible by m, the left side, d, must be also, say, d= mc. Then we could divide the entire equation by m to get the simpler equation c= au+ bv. But since d= (a,b) that is impossible.
  4. Nov 14, 2009 #3
    Oh! So d /should/ divide c, because d=(a,b)... but this contradicts d=mc, which suggests d cannot divide c, as d > c. (as m>1 because m=(x,y) and we said that (x,y) != 1)

    Thanks, HallsofIvy :-)
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Diophantine and coprime solutions x,y
  1. X^y=y^x proof (Replies: 4)