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

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

You have no rights to post comments