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

Printable View

- Nov 29th 2012, 05:05 PMflorianGreatest 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, 08:16 PMRBowmanRe: 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, 04:54 PMflorianRe: 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, 05:07 PMRBowmanRe: 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, 03:59 PMflorianRe: Greatest Common Divisor
Many Thanks. That certainly makes it more clear.(Happy)

- Dec 7th 2012, 04:40 PMflorianRe: 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, 10:44 AMjohan121Re: Greatest Common Divisor
4 example problems of determining the greatest common factor of two numbers by factoring the 2 numbers first.