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 .
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 .