Intro to Proofs: Greatest Common Divisors

[rdr3]

Homework Statement

(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

xa+yb=d

are exactly

x=m+k(b/d), y=n-k(a/d)

where k∈Z.

(b) Let a and b be integers with gcd(a,b)=d. Show that the equation

xa+yb=c

has a solution (x,y)∈ ZxZ if and only if d|c.

Z refers to integers.

Homework Equations

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

x₀a+y₀b=d

Then we multiply both sides by some arbitrary element, such as n. Giving us,

(nx₀)a+(ny₀)b=nd=c

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.

 

[kru_]

How about the contrapositive for the other direction? That might be easier.

 

[rdr3]

So maybe this?

Suppose d∤c...

Then c≠nd

In which case, c≠nd≠(nx₀)a+(ny₀)b.

So like that? Or am I way off? Sorry I'm not very good at this... The teacher explains things way over everyone's head.