Diophantine and coprime solutions x,y

[thomas430]

Hi everyone,

I saw that for the linear diophantine equation d=ax+by, 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 :-)


Thomas.

 

[HallsofIvy]

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.

 

[thomas430]

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 :-)