Prove a x b=(a,b) x [a,b] (HCF x LCM)

By Anonymous on Saturday, September 23, 2000 - 08:31 am :

Hi,

I came by the following question:

Prove ab = (a,b)[a,b]

I thought of letting d = ab/(a,b)

And showing that this is a multiple of [a,b] or something

I'm not sure!

Hope you can help!

By Anonymous on Sunday, September 24, 2000 - 04:30 pm :

Funnily enough, I have also come across the above question!

However, here's another more interesting one:

If (a,b) =1, then prove that (a-b, a+b) =1 or 2

Good luck

By David Loeffler (P865) on Sunday, September 24, 2000 - 05:46 pm :

The second is quite a fun one. Here is a fairly nice proof I once came across.

Clearly if X divides two numbers M and N, it must divide M-N and M+N. So if d divides a+b and a-b, d must divide (a-b)+(a+b) = 2a, and it must also divide (a+b)-(a-b) = 2b. Thus any common divisor of a-b and a+b must be a common divisor of 2a and 2b; so it can be at most (2a, 2b) = 2. Therefore, in general, we have (a+b, a-b) = 1 or 2. QED.

(It will be one if a and b differ in parity, i.e. one is even and one is odd. If both are odd a-b and a+b are both even, so (a-b,a+b)=2.)

I can't think of a nice explanation of the first one offhand - that will take a better mathematician than I, I think.

By Kerwin Hui (P1312) on Sunday, September 24, 2000 - 08:47 pm :

Well, since there is unique factorisation, consider the maximum power a to which a prime p can be raised such that

p^a | a

and similarly for b. Asssume, WLOG, that

a \geq b

then a is the maximum power to which p can be raised such that p^a divides {a,b}, and b is the corresponding case for (a,b). so the power of p in ab=a +b =power of p in (a,b){a,b} QED

Kerwin

By Barkley Bellinger (Bb246) on Thursday, October 19, 2000 - 09:30 pm :

Here is another proof of

a b = (a, b) [a, b]

which follows the line of thought suggested by the original questioner.

It relies on a result known as Bezout's Theorem.

This states that there exists integers $p$ , $q$ such that $p a + q b = c$ if and only if $(a, b)$ divides $c$ .

I shall assume this and use it where necessary.

In the questioner's notation, let $d = a b / (a, b) = A b = a B$ , where $a = A (a, b)$ $b = B (a, b)$

We see that $d$ is a multiple of both $a$ and $b$ , so all we need to do is whos that there is none smaller.

Let $m$ be any common multiple of $a$ and $b$ .

Now, $(A, B) = 1$ , if you think about it.

So, by Bezout's Theorem, there exists integers $p$ , $q$ such that $p A + q B = 1$

$\Rightarrow m p A + m q B = m$

But $d = A b$ divides $m p A$ (since $b$ divides $m$ )

and $d = a B$ divides $m q B$ (since $a$ divides $m$ )

Therefore $d$ divides $m$ . But $m$ was any common multiple of $a$ and $b$ , so $d$ must be the least common multiple.