# Greatest Common Factor and Least Common Multiple

## Greatest Common Factor

Main idea: The Greatest Common Factor of two positive integers and , is the largest counting number , that divides both, and . Definition: The Greatest Common Factor of two positive integers and , is an integer , such that:
• divisibility condition: divides both a and b.
• maximality ﻿condition: If there exists another integer that divides both and , then divides .
Notation: If is the 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 and , is the largest counting number , which can be divided by both, and . Definition: The Least Common Multiple of two positive integers and , is an integer , such that: divisibility condition: is divided by both and . minimality ﻿condition: If there exists another integer that is divided by both and , then is divided by . Notation: If m the Least Common Multiple of integers a and b, then we will write .