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\]
. 
