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.Prove that xa+yb=c has integer solution x, y iff hcf(a,b)|c.
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?
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.Prove that hcf(na,nb) = n*hcf(a,b) for a, b, n integers, and n > 0
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?