Some proofs involving greatest common divisors (1 Viewer)

Users Who Are Viewing This Thread (Users: 0, Guests: 1)

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

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!


Science Advisor
Homework Helper
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.

The Physics Forums Way

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving