I'm going through the book(adsbygoogle = window.adsbygoogle || []).push({}); Number Theoryby 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 numberdsuch that:lcm(

- It is a common divisor:
d|aandd|b.- It is the greatest common divisor: For every
cwhich is a common divisor ofaandb,c|d.a,b) is a numbermsuch that:

- It is a common multiple:
a|mandb|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 ofaandb.

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 numberfsuch thata|fandb|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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Basic Number Theory: LCM/GCD Proof

**Physics Forums | Science Articles, Homework Help, Discussion**