# Thread: Help with elem. proof

1. ## Help with elem. proof

Prove that if (a,b)=[a,b] then a=b.

I'm not sure how to start this one. I thought maybe using the fact that
(a,b)[a,b]=ab would get me somewhere, but so far it hasn't worked out to anything useful...

Any hints?

2. Please clarify your notation. Is (a,b) an ordered pair? And what is [a,b]?

3. Originally Posted by DrSteve
Please clarify your notation. Is (a,b) an ordered pair? And what is [a,b]?
Sorry, should have done that.
(a,b)=gcd(a,b)
[a,b]=lcm(a,b)

So basically, if two numbers have the same gcd and lcm, then they must be equal. But how can I prove that?

4. Originally Posted by paupsers
Prove that if (a,b)=[a,b] then a=b.

I'm not sure how to start this one. I thought maybe using the fact that
(a,b)[a,b]=ab would get me somewhere, but so far it hasn't worked out to anything useful...

Any hints?
Given $\displaystyle a=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$ and $\displaystyle b=p_1^{b_1}p_2^{b_2}\cdots p_k^{b_k}$

Then $\displaystyle (a,b) = p_1^{\min(a_1,b_1)}p_2^{\min(a_2,b_2)}\cdots p_k^{\min(a_k,b_k)}$ and $\displaystyle [a,b] = p_1^{\max(a_1,b_1)}p_2^{\max(a_2,b_2)}\cdots p_k^{\max(a_k,b_k)}$

5. Aha - that makes more sense!

I can think of one way to do it using the fundamental theorem of arithmetic. I'll give you the main idea, and see if you can write it up rigorously:

a and b can each be factored uniquely as a product of primes. You get the gcd by taking the lowest power of each prime that appears. You get the lcm by taking the highest power of each prime that appears. If the gcd and lcm are equal, then the lowest power of each prime equals the highest power of each prime. So a and b have the same prime factorizations, and thus they are the same.

6. Originally Posted by paupsers
Prove that if (a,b)=[a,b] then a=b.

I'm not sure how to start this one. I thought maybe using the fact that
(a,b)[a,b]=ab would get me somewhere, but so far it hasn't worked out to anything useful...

Any hints?
I assume that $a$ and $b$ are nonnegative.

We have $(a,b)\leq a$ and $b\leq[a,b]$. From $(a,b)=[a,b]$ it follows that $b\leq a$.
Similiarly, write $(a,b)\leq b$ and $a\leq[a,b]$; so $a\leq b$. The two inequalities give $a=b$.

For any integers $a$ and $b$ the result is that $a=\pm b$. (Using the abolute values...)

7. Thanks! I actually wasn't able to use the Fundamental Theorem of Arithmetic (since we don't "know" that yet) but your proof was simple and makes perfect sense!