# Help with a problem involving the GCD, LCM.

• Oct 4th 2010, 02:36 PM
auitto
Help with a problem involving the GCD, LCM.
Let a and b be positive integers, and let m be an integer such that $ab=m(a,b).$ Without using the prime factorization theorem, prove that $(a,b)[a,b]=ab$ by verifying that m satisfies the necessary properties of $[a,b].$

Note that $(a,b)$ denotes the GCD of a and b and $[a,b]$ denotes the LCM of a and b.

Here is the definition for LCM that I have (the two properties that I need to show.)

A positive integer m is called the least common multiple of the nonzero integers a and b if

(i) m is a multiple of both a and b, and

(ii) any multiple of both a and b is also a multiple of m.

Property (i) was not very difficult to show, but I am struggling with the second one. Here is what I have so far.

Let $a|q$ and $b|q$, where $q\in\mathbb{Z}.$

Then $q=ax$ and $q=by,$ where $x,y\in\mathbb{Z}$

$==>\quad qb=abx\quad$ and $qa=aby$

$==>\quad qb=mdx\quad$ and $qa=mdy$

$==>\quad qhd=mdx\quad$ and $qkd=mdy$

$==>\quad qh=mx\quad$ and $qk=my$

$==>\quad m|qh\quad$ and $m|qk.$

That is as much as I can get. How can I show that $m|q$?

Any hints would be appreciated.
• Oct 4th 2010, 04:02 PM
undefined
Edit: See here

Basic Number Theory: LCM/GCD Proof

(Make sure to read posts #1 through #4 to get a full treatment of part (2).)

Although the proof for part (1) is lengthy for my taste, since

$\displaystyle ab=m(a,b)\implies m=a\left(\frac{b}{(a,b)}\right)$

And since (a,b) | b, we know $\frac{b}{(a,b)}$ is an integer, hence a | m, and by symmetry b | m also.

Edit 2: I think aman_cc's proof for part (2) below is nicer than the one on the other forum.
• Oct 4th 2010, 08:11 PM
aman_cc
Hint use the fact that

xa + yb = (a,b) for some integers x,y
xaq + ybq = (a,b)q
divide the whole eq by ab
xq/b + yq/a = q/m
it should be easy from here