Highest Common Factor
The highest common factor divides both and , and every common divisor of and satisfies .
Definition 4.5 (Highest Common Factor)
Given , a natural number is the highest common factor or the greatest common divisor of and if
- and ;
- for any such that and , we have .
We write or .
Example
The factors of are , and the factors of are . The common factors of and are , so the highest common factor is : that is, .
From prime factorisations
If and with for all , then
Indeed, by uniqueness of prime factorisation the common factors of and are exactly the numbers with . For example,
Related
Stated in
- Definition 4.5 (Highest Common Factor)§4.2 Highest Common Factor