Thread: 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

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.

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?

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.

Many Thanks. That certainly makes it more clear.

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

4 example problems of determining the greatest common factor of two numbers by factoring the 2 numbers first.