# Greatest Common Divisor (factor) - Least Common Multiple

Keywords: Greatest Common Divisor (factor) - Least Common Multiple

## Greatest Common Factor GCF

Greatest common factor of two integers m and n is:

$$GCF(m;n)=(m;n)=l$$

**Eeuclidean algorithm for computing the greates common factor GCF**

**Example: GCF (246;132)=(246;132)=6**

$$\begin{array}{ccc}{246}& =& {132}\xb71+{114}\\ {132}& =& {114}\xb71+{18}\\ {114}& =& {18}\xb76+{6}\\ {6}& =& \overline{)6}\xb71+0\end{array}\begin{array}{}\\ \\ \\ \end{array}$$

## Least Common Multiple LCM

Least common multiple of two integers m and n is:

{formula_2329}

## Connection between the greatest common divisor (GCD) and the least common multiple (LCM)

$$(m;n)\xb7[m;n]=m\xb7n$$

Example:** LCM (246;132)= [246;132]=5412**

$$\left[246;132\right]=\frac{246\xb7132}{(246;132)}=\frac{246\xb7132}{6}=5412$$

## Relative Primes

Two integers **m** and **n** are relatively prime if they share no common positive factors (divisors) except 1. **GCF(m;n)=[m;n]=1**