How Do You Prove the Relationship Between LCM and GCD in Number Theory?

[Tokipin]

I'm going through the book Number Theory by George E. Andrews. I'm having particular difficulty constructing proofs, which I'm sure is quite common. Problem 4 of section 2-2:

Prove that

\operatorname{lcm}(a,b) = \frac{{ab}}{{\operatorname{gcd}(a,b)}}.--------------------
Ok, so I guess a good place to start is the definitions.

gcd( a, b ) is a number d such that:

• It is a common divisor: d|a and d|b.
• It is the greatest common divisor: For every c which is a common divisor of a and b, c|d.

lcm( a, b ) is a number m such that:

• It is a common multiple: a|m and b|m.
• It is the smallest common multiple.

My proof:
--------------------
1.
First, we show that \frac{{ab}}{{\operatorname{gcd}(a,b)}} is a common multiple of a and b.

We set a = q_a \operatorname{gcd}(a,b) and b = q_b \operatorname{gcd}(a,b) so that \frac{{ab}}{{\operatorname{gcd}(a,b)}} becomes

\frac{{q_a \gcd (a,b)q_b \gcd (a,b)}}{{\gcd (a,b)}}

which is

q_a q_b \operatorname{gcd}(a,b)

which we see:

a|\bold{q_a \operatorname{gcd}(a,b)} q_b and b|\bold{q_b \operatorname{gcd}(a,b)} q_a.--------------------
2.
Next, we consider a number f such that a|f and b|f.

We set f = k_1 a and f = k_2 b

which is

f = k_1 q_a \operatorname{gcd}(a,b) and f = k_2 q_b \operatorname{gcd}(a,b).

We set k_1 q_a \operatorname{gcd}(a,b) = k_2 q_b \operatorname{gcd}(a,b)

which becomes

k_1 q_a = k_2 q_b

which we can write as

\frac{{k_1 }}{{k_2 }} = \frac{{q_b }}{{q_a }}.

Because \frac{{q_b }}{{q_a }} is irreducible as q_b and q_a are relatively prime since q_a = \frac{{a}}{{\operatorname{gcd}(a,b)}} and q_b = \frac{{b}}{{\operatorname{gcd}(a,b)}}, it follows that k_1 \geqslant q_b and k_2 \geqslant q_a.

Therefore, f \geqslant q_a q_b \operatorname{gcd}(a,b).--------------------
I'm pretty sure 1 is fine. I'm not really sure about 2. I've been mulling over this problem for about a week as I wanted something fairly solid to show for an attempt before seeking help. Any advice is appreciated.

 

[matt grime]

I want to congratulate you on the care you've taken with this question; it is most pleasing to see someone writing maths so well at such an early stage in their learning.

All that you have is fine, but I'd prefer to say, in the part where you've reached

k_1 q_a = k_2 q_b

for you to simply say that as q_a and q_b are coprime k_1 must divide q_b and k_2 must divide q_a hence... and then for you to complete it without recourse to invoking inequalities.

For instance, all this remains true in the integers rather than the natural numbers, and there are infinitely many numbers smaller than the least common multiple of a and b that are both divisible by a and b (such as -ab).

 

[Gokul43201]

Ah, what a breath of fresh air ! I dream of the day that all threads in this forum will look like this.

I can see a brute force proof using prime factorization. But the above method looks a lot more elegant and satisfying.

PS : At most, I might throw in the two lines it takes to show that q_a, q_b are coprime.

 

[Tokipin]

Thank you both for your words.

A large part of the reason I'm being careful is because I've tried to learn more advanced things and failed. A few pages into Weiss' Algebraic Number Theory and I realized 1) I don't know what a topology is and 2) I don't know what a prime divisor is. Another example is Karl Rubin's Euler Systems, which I realized a few words in that I wasn't going to get anywhere with. It was like trying to read a novel without knowing the alphabet and being blind.

I have many books that I wish I could understand right now because their equations look so beautiful. I am always trying to understand things that are out of my reach. It is only recently that I realized I have to start from the ground and work my way up rigorously. This time around I know how important a strong footing is. And although I am not one for the rigor of axiomatic math, at the very least it ensures my understanding is solid, and that alone is a good enough reason to use it.


-----------------
Matt:

In

k_1 q_a = k_2 q_b,

did you mean that since q_a and q_b are coprime, q_a must divide k_2 and q_b must divide k_1? Hence, f is a multiple of q_a q_b \operatorname{gcd}(a,b). That is quite nicer, since in the positive-only case it takes care of the inequalities implicitly, and it works with all the integers as well. This actually solves another problem from the same chapter where I needed to show that all common multiples of a and b are multiples of lcm(a,b).

I'm a bit confused about the signs. Can a GCD be negative? What about the LCM? My current understanding is that both the GCD and LCM are always positive. What can be negative are the k_1 and k_2 for an arbitrary common multiple f. However, http://en.wikipedia.org/wiki/Gcd says that for any integer m, gcd(ma,mb) = m gcd(a,b), so I guess it can be negative (as when m is -1) unless I misread.

 

[matt grime]

Well, it looks like you've found an error in wikipedia. It defines gcd to be positive for any pair of integers and indeed states that gcd(ma,mb)=mgcd(a,b) for any integer m. This is indeed not consistent. Of course wikipedia is not infallible. No one is. And no book is infallible (and that is worth rememebering). What is true is that gcd(ma,mb)=|m|gcd(a,b).

Often in maths some things are defined 'up to' something. In number theory, gcd is usaully defined 'up to units'. That is given two objects we can work out a gcd, and if we do it twice we might end up with two answers X and Y, but X will differ by Y only by mutliplication by something invertible (plus or minus 1 in the case of the integers).