### Approach 1. Integer numbers prime factorization:

#### Prime Factorization of a number: finding the prime numbers that multiply together to make that number.

#### 16 = 2^{4};

16 is not a prime, is a composite number;

#### 45 = 3^{2} × 5;

45 is not a prime, is a composite number;

** Positive integers that are only dividing by themselves and 1 are called prime numbers. A prime number has only two factors: 1 and itself. *

* A composite number is a positive integer that has at least one factor (divisor) other than 1 and itself.

### Calculate the least common multiple, lcm:

#### Multiply all the prime factors, by the largest exponents (if any).

#### lcm (16; 45) = 2^{4} × 3^{2} × 5;

## lcm (16; 45) = 2^{4} × 3^{2} × 5 = 720

Numbers have no common prime factors: 720 = 16 × 45.

## Approach 2. Euclid's algorithm:

### Calculate the greatest (highest) common factor (divisor), gcf, hcf, gcd:

#### This algorithm involves the operation of dividing and calculating remainders.

#### 'a' and 'b' are the two positive integers, 'a' >= 'b'.

#### Divide 'a' by 'b' and get the remainder, 'r'.

#### If 'r' = 0, STOP. 'b' = the GCF (HCF, GCD) of 'a' and 'b'.

#### Else: Replace ('a' by 'b') & ('b' by 'r'). Return to the division step above.

#### Step 1. Divide the larger number by the smaller one:

45 ÷ 16 = 2 + 13;

Step 2. Divide the smaller number by the above operation's remainder:

16 ÷ 13 = 1 + 3;

Step 3. Divide the remainder from the step 1 by the remainder from the step 2:

13 ÷ 3 = 4 + 1;

Step 4. Divide the remainder from the step 2 by the remainder from the step 3:

3 ÷ 1 = 3 + 0;

At this step, the remainder is zero, so we stop:

1 is the number we were looking for, the last remainder that is not zero.

This is the greatest common factor (divisor).

### Calculate the least common multiple, lcm:

#### Least common multiple, formula:

lcm (a; b) = ^{ (a × b) } / _{ gcf, hcf, gcd (a; b); }

#### lcm (16; 45) =

^{ (16 × 45) }/_{ gcf, hcf, gcd (16; 45) } =

^{ 720 }/_{ 1 } =

#### 720;

## lcm (16; 45) = 720 = 2^{4} × 3^{2} × 5

## Final answer:

Least common multiple

lcm (16; 45) = 720 = 2^{4} × 3^{2} × 5

Numbers have no common prime factors: 720 = 16 × 45.

### Why do we need the least common multiple?

#### In order to add, subtract or compare fractions you have to first build their denominators the same. This common denominator is nothing else than the least common multiple of fractions' denominators, also called the least common denominator, lcd.

#### By definition, the least common multiple of two integers, LCM, is the smallest positive integer larger than 0 that is a multiple of both.

## More operations of this kind: