# Greatest Common Divisor

• Nov 29th 2012, 04:05 PM
florian
Greatest Common Divisor
Hi all!
I'm an OAP(male) from the UK
I dabble in maths irregularly.
I have a degree from the OU (thats the Open University)
I do maths for fun!
I have the following problem. Can you help?

if gcd(m,n)=1, prove that gcd(mn,m+n)=1
• Nov 29th 2012, 07:16 PM
RBowman
Re: Greatest Common Divisor
Suppose gcd(m,n) = 1.

Let d be a common divisor of mn and (m+n). Then there exist x, y s.t.

xd = mn and yd = m+n.

xd = m(yd - m) or (my - x)d = m^2. And similarly,
xd = (yd - n)n or (ny - x)d = n^2.

So d divides m^2 and n^2,
d is a common divisor of m and n,
d must be 1,
gcd(mn, m+n) = 1.

Hope this helps.
• Nov 30th 2012, 03:54 PM
florian
Re: Greatest Common Divisor
I'm not sure I follow:
You have (my - x)d = m^2 and you say d divides m^2. How do we know that (my-x) does not divide m^2?
• Nov 30th 2012, 04:07 PM
RBowman
Re: Greatest Common Divisor
They both do. Remember,

ab = c implies that both a and b are divisors of c.

We didn't need to show that (my-x) divides m^2, so it wasn't mentioned.

Hope that makes it more clear.
• Dec 1st 2012, 02:59 PM
florian
Re: Greatest Common Divisor
Many Thanks. That certainly makes it more clear.(Happy)
• Dec 7th 2012, 03:40 PM
florian
Re: Greatest Common Divisor
While the above is OK, it is rather long. I have come across the following solution which I think is rather neat.

Consider a prime p which divides mn and m+n. From the first of these, p must divide m or n. From the second, if it divides m then it must also divide n, and conversely. Hence p divides both m and n. But there is no such prime since m and n are coprime. Hence no such p exists, so the two numbers are coprime.

Regards - florian
• Dec 8th 2012, 09:44 AM
johan121
Re: Greatest Common Divisor
4 example problems of determining the greatest common factor of two numbers by factoring the 2 numbers first.