- #1

- 19

- 0

I'm going through the book

Prove that

[tex]\operatorname{lcm}(a,b) = \frac{{ab}}{{\operatorname{gcd}(a,b)}}[/tex].

--------------------

Ok, so I guess a good place to start is the definitions.

gcd(

My proof:

--------------------

1.

First, we show that [itex]\frac{{ab}}{{\operatorname{gcd}(a,b)}}[/itex] is a common multiple of

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

[tex]\frac{{q_a \gcd (a,b)q_b \gcd (a,b)}}{{\gcd (a,b)}}[/tex]

which is

[tex]q_a q_b \operatorname{gcd}(a,b)[/tex]

which we see:

[tex]a|\bold{q_a \operatorname{gcd}(a,b)} q_b[/tex] and [tex]b|\bold{q_b \operatorname{gcd}(a,b)} q_a[/tex].

--------------------

2.

Next, we consider a number

We set [itex]f = k_1 a[/itex] and [itex]f = k_2 b[/itex]

which is

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

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

which becomes

[tex]k_1 q_a = k_2 q_b[/tex]

which we can write as

[tex]\frac{{k_1 }}{{k_2 }} = \frac{{q_b }}{{q_a }}[/tex].

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

Therefore, [itex]f \geqslant q_a q_b \operatorname{gcd}(a,b)[/itex].

--------------------

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.

*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

[tex]\operatorname{lcm}(a,b) = \frac{{ab}}{{\operatorname{gcd}(a,b)}}[/tex].

--------------------

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*.

*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 [itex]\frac{{ab}}{{\operatorname{gcd}(a,b)}}[/itex] is a common multiple of

*a*and*b*.We set [itex]a = q_a \operatorname{gcd}(a,b)[/itex] and [itex]b = q_b \operatorname{gcd}(a,b)[/itex] so that [itex]\frac{{ab}}{{\operatorname{gcd}(a,b)}}[/itex] becomes

[tex]\frac{{q_a \gcd (a,b)q_b \gcd (a,b)}}{{\gcd (a,b)}}[/tex]

which is

[tex]q_a q_b \operatorname{gcd}(a,b)[/tex]

which we see:

[tex]a|\bold{q_a \operatorname{gcd}(a,b)} q_b[/tex] and [tex]b|\bold{q_b \operatorname{gcd}(a,b)} q_a[/tex].

--------------------

2.

Next, we consider a number

*f*such that*a*|*f*and*b*|*f*.We set [itex]f = k_1 a[/itex] and [itex]f = k_2 b[/itex]

which is

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

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

which becomes

[tex]k_1 q_a = k_2 q_b[/tex]

which we can write as

[tex]\frac{{k_1 }}{{k_2 }} = \frac{{q_b }}{{q_a }}[/tex].

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

Therefore, [itex]f \geqslant q_a q_b \operatorname{gcd}(a,b)[/itex].

--------------------

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.

Last edited: