- #1

Math100

- 690

- 180

- Homework Statement:
- Prove that the greatest common divisor of two positive integers divides their least common multiple.

- Relevant Equations:
- None.

Proof: Suppose gcd(a, b)=d.

Then we have d##\mid##a and d##\mid##b for some a, b##\in## ##\mathbb{Z}##.

This means a=md and b=nd for some m, n##\in## ##\mathbb{Z}##.

Now we have lcm(a, b)=##\frac{ab}{gcd(a, b)}##

=##\frac{(md)(nd)}{d}##

=dmn

=dk,

where k=mn is an integer.

Thus, d##\mid##lcm(a, b), and so gcd(a, b)##\mid##lcm(a, b).

Therefore, the greatest common divisor of two positive integers divides their least common multiple.

Then we have d##\mid##a and d##\mid##b for some a, b##\in## ##\mathbb{Z}##.

This means a=md and b=nd for some m, n##\in## ##\mathbb{Z}##.

Now we have lcm(a, b)=##\frac{ab}{gcd(a, b)}##

=##\frac{(md)(nd)}{d}##

=dmn

=dk,

where k=mn is an integer.

Thus, d##\mid##lcm(a, b), and so gcd(a, b)##\mid##lcm(a, b).

Therefore, the greatest common divisor of two positive integers divides their least common multiple.