**1. The problem statement, all variables and given/known data**

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

**2. Relevant equations**

**3. 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!