I solve this problem but I did not get the right solition.

Show that ifaandbare positive integers, then (a,b)=(a+b,[a,b])

Thank you!

Printable View

- Mar 15th 2007, 01:53 PMjmc1979Fundamental Theorem of Arithmetic
I solve this problem but I did not get the right solition.

Show that if*a*and*b*are positive integers, then (a,b)=(a+b,[a,b])

Thank you! - Mar 15th 2007, 01:58 PMThePerfectHacker
- Mar 15th 2007, 02:17 PMPlato
I suspect the problem is: gcd(a,b)=gcd(a+b, lcm(a,b)).

- Mar 15th 2007, 02:18 PMjmc1979Least common multiple
[a,b] means the Least Common Multiple

Thank you! - Mar 15th 2007, 02:20 PMjmc1979You are correct
Plato, you are correct!

- Mar 15th 2007, 02:25 PMPlato
Use the fundamental to write both a and b in prime factor form.

Note that gcd(a,b) is a divisor of a+b. Moreover, ab=gcd(a,b)lcm(a,b). - Mar 15th 2007, 02:38 PMjmc1979Thanx
Thank you Plato!

- Mar 15th 2007, 02:45 PMThePerfectHacker
Here is an outline of the proof.

You do not need to use the fundamental theorem here.

We need to show.

gcd(a+b,lcm(a,b))=gcd(a,d)

Iff,

gcd(a+b,ab/d)=d where d=gcd(a,b)

Iff,

gcd(ad+bd,ab)=d^2

Now you can imagine why that is true.

Look d^2 divides ad and bd.

And d^2 divides ab.

Now argue by contradiction to complete the proof. - Mar 19th 2007, 03:53 PMjmc1979One solution but not acepted
This is one solution I found:

Show that if a and b are positive integers then gcd(a,b)=gcd(a+b, lcm(a,b)).

Solution: Let p be a prime that divides a or b. Then p divides a+b and [a,b]. Hence p divides both sides of the equation. Define s,t by p^s || a, p^t || b, say that a=xp^s and b=yp^t. Without loss of generality, suppose s ≤ t. Then a+b = p^s (x + p^(t-s)), so p^s || a+b. Also, p^(max(s,t)) || lcm(a,b). But max(s,t)=t, so p^t || lcm(a,b). Therefore p^(min(s,t)) || gcd(a+b,lcm(a,b)). But min(s,t)=s, so the same power of p divides both sides of the equation. Therefore the two sides must be equal.

This solution but is not accepted by the professor because he states that the first two sentences are not enough explanation for this exercise or with another solution with explanation. Can anyone help me with this exercise with an explanation? Thank you!