# Greatest Common Factor and Least Common Multiple

- Author:
- Omar G. Monteagudo

- Topic:
- Arithmetic, Division

## Greatest Common Factor

**Main idea:**The

*Greatest Common Factor*of two positive integers

**Definition:**

*The*

**Greatest Common Factor**of two positive integers

*divisibility condition:*divides both a and b. *maximality condition*: If there exists another integerthat divides both and , then divides .

**Notation:**If

*Greatest Common Factor*of integers a and b, then we will write

## How to find gcf(a, b) of two integers by exhaustive search

It works great for small integer numbers, but tends to be non efficient for large numbers.

## How to find gcf(a, b) by factoring

It works great for small integer numbers whose factored form can be easily found, but tends to be non efficient for large numbers.

## How to find gcf(a, b) by using Euclid's Algorithm

It works great in any case!

## Least Common Multiple

**Main idea:**The

*Least Common Multiple*of two positive integers

**Definition:**The

**Least Common Multiple**of two positive integers

*divisibility condition*:

*minimality condition*: If there exists another integer

**Notation:**If m the

*Least Common Multiple*of integers a and b, then we will write