(a) Let a and b be integers with gcd(a,b)=d, and assume that ma+nb=d for integers m and n. Show that the solutions in Z to
(b) Let a and b be integers with gcd(a,b)=d. Show that the equation
has a solution (x,y)∈ ZxZ if and only if d|c.
Z refers to integers.
The Attempt at a Solution
Ok so I'm pretty sure I figured out part (a).
Part (b) on the other hand is causing me problems. I know since it's an "if and only if" question, I have to prove it both ways.
This is what I have so far.
So we have some x and y, such as
Then we multiply both sides by some arbitrary element, such as n. Giving us,
So that's the first part. Now I'm supposed to go the other way with it, showing that
xa+yb=c -> c=nd, n∈ Z.