Proof of GCD() / Bezout's Theorem thing

Webmonkey

Hey again,

Yet another thing I'm a little stuck on - well I think I am anyways.

Question is:
If a,b Elements of Z (Integers) and d = gcd(a,b)
then if C element of Z there exists s,t Elements of Z such that C = as + bt IF and only IF d/c (D divides C)

So my solution kinda is:

Since d/c -> c = ld for some l in Z.
And since gcd(a,b) = d , by Bezout's Theorem: d = ua + vb for some u,b in Z.
So filling in for d we get:

c = l(ua + vb)
c = lua + lvb
c = a(lu) + b(lv)

Since l,u,v elements in Z -> lu element of Z and lv element of Z.
Take lu = s and lv = t

then

c = as + bt QED

Is this correct? - this is a proof I came up with myself but don't know if its the correct way of going about it.

Don't know how common this topic is so hopefully someone out there can help!

Thanks.

Fremen

Yep, that looks fine to me.
The statement of the problem called for "if and only if", though, so you have to assume c = as + bt and show c is divisible by d to finish off the problem. You might lose marks in an exam otherwise.

Webmonkey

Cool thanks Fremen once again.

Will work the other way with it so and see how I get on - probably won't even come up anyways!