# Fundamental Theorem of Arithmetic

• Mar 15th 2007, 12:53 PM
jmc1979
Fundamental 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, 12:58 PM
ThePerfectHacker
Quote:

Originally Posted by jmc1979
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!

What does that mean?
(a,b) probably means gcd(a,b).

But what does [a,b] mean?
• Mar 15th 2007, 01:17 PM
Plato
I suspect the problem is: gcd(a,b)=gcd(a+b, lcm(a,b)).
• Mar 15th 2007, 01:18 PM
jmc1979
Least common multiple
[a,b] means the Least Common Multiple

Thank you!
• Mar 15th 2007, 01:20 PM
jmc1979
You are correct
Plato, you are correct!
• Mar 15th 2007, 01:25 PM
Plato
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, 01:38 PM
jmc1979
Thanx
Thank you Plato!
• Mar 15th 2007, 01:45 PM
ThePerfectHacker
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,

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, 02:53 PM
jmc1979
One 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 st. 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!