## Proff That the product of Two Integers is the Produict of the Greatest Common Divisor and the Lowest Common Multiple

For any integers

\[a, \; b\]

, if gcd means 'greatest common divisor', and lcm means 'lowest common multiple', then \[gcd(a, \; b) \times ;cm(a, \; b)=ab\]

.Proof

Let

\[d=gcd)a, \; b), \; l=lcm(a, \; b)\]

. Since \[d | a\]

it also divides \[ab\]

so there exists an integer \[n\]

such that \[ab=dn\]

. Since \[d | a, \; d | b\]

there exist integers \[u, \; v\]

such that \[n=bu, \; n=av\]

. This shows that

\[n\]

is a common multiple of \[a, \; b\]

. Let \[m\]

be any other common multiple of \[a, \; b\]

then there exist integers \[r, \; s\]

such that \[m=ar, \; m=bs\]

.Since

\[d=gcd(a,b)\]

we can write \[d\]

as an integer combination of \[a, \; b\]

i.e. \[d=ax+by\]

.Multiply this expression throughout by

\[m\]

, obtaining\[md=max+mby=bsax+arby=ab(sx+ry)=dn(sx+by)\]

Cancel

\[d\]

to give \[m=n(sx+by)\]

.Hence

\[n | m \rightarrow n \le m\]

.