Some proofs involving greatest common divisors

[Andrusko]

Hey all, I'm an absolute noob to number theory stuff and I've got this assignment to do with a few proofs.

Homework Statement

Proove that:

i) if gcd(a,b) = c then gcd(a,a+b) = c

ii) if gcd(a,b) = c and a = a'c and b = b'c then gcd(a',b') = 1

iii) if there exists r,s such that rx + sy = 1 then gcd(x,y) = 1

Homework Equations

The Attempt at a Solution

i) pretty sure this is right, I used a contradiction thing at the end:

prove that if gcd(a,b) = c then gcd(a,a+b) = c

c|a and c|b
a = a'c and b = b'c
so a+b = a'c + b'c
= (a' + b')c
implies c|(a+b)

suppose there exists d: gcd(a,a+b) = d, d>=c

we know c|a and c|(a+b)
and d|a and d|(a+b)

thus d|c

d cannot be greater than c

so d = c

------------------------------

ii) this one's a bit shaky:

prove that if gcd(a,b) = c and a = a'c and b = b'c then gcd(a',b') = 1

now c = ra + sb (r,s integers)
so c = r(a'c) + s(b'c)
= ra'c + sb'c
= (ra' + sb')c

dividing through by c gives:

1 = ra' + sb'

and doesn't this imply that gcd(a',b') = 1?

I don't think this is the right way to prove it.

iii) No idea where to start with this. I guess I would use a method as above, but I doubt the validity of it.

Thanks for any help!

 

[CompuChip]

The second one is very intuitive: if there were any number d dividing both a' and b', then it would also divide a and b and therefore should be a factor in the gcd (i.e. it is already in c). Perhaps you can use this in your proof (suppose that gcd(a', b') = d, not equal to 1, then c is not the gcd).

For iii) I suggest writing d = gcd(x, y), x = x' d, y = y' d and showing that d must be 1.