Originally Posted by

**bumcheekcity** I have to prove this both ways, because of the iff statement. So first, I let d = hcf(a,b) and *assume* it divides c, to show that xa+yb=c has integer solutions.

1) xy + yb = c

2) (xa)/d + (yb)/d = c/d

3) x(a/d) + y(b/d) = c/d

4) By the definition of the HCF, d|a, d|b, so a/d, b/d are integers. If c/d (by assumption) is an integer too, there will be integers x, y that satisfy the above equasion.

Now, I have to assume that xa+yb=c has integer solutions, and then show that d|c to finish the proof, but I dont know where to start, does anyone have any suggestions?

1) ???

I've attempted the above problem, and been advised to prove that both sides of the equasion divide the other, and hence, they're both equal. However, I've hit at some contradictions, and I'd like to know where I'm going wrong.

1) Let c = hcf(na,nb), and d = n*hcf(a,b). Note that n|d.

2) Note that c|na, c|nb and thus, c|n.

3) c|n and n|d => c|d.

4) Now, consider c/d = c/n * c/hcf(a,b).

Now, I want to show that both of those are integers, thus making c/d an integer, thus showing that d|c and proving the statement. But, I can't seem to show how. Can anyone help me with my proof?