- #1
Andrusko
- 44
- 0
Hey all, I'm an absolute noob to number theory stuff and I've got this assignment to do with a few proofs.
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
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!
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!