Given two or more positive integers, the greatest common divisor (gcd), or highest common factor (hcf), is the largest positive integer that divides the numbers without a remainder.
If we are given the prime factorization of the numbers, finding the greatest common divisor is straightforward. Let and , where are positive prime integers and . Then
However, in general, factorizing numbers is a very difficult problem, so instead we use the Euclidean Algorithm.
To find the greatest common divisor using the Euclidean Algorithm, we perform long division several times. Starting with a pair of numbers , we obtain , where is the quotient and is the remainder. We then repeat the sequence with the pair .
As a concrete example, the following is the Euclidean Algorithm performed to calculate :
The process stops since we reached 0, and we obtain
1. Show that if , then .
Solution: Let be the set of primes that divide either or . Let be the set of primes that divide either , or . Let be the exponent of in the term . If , then , hence , so . If , then , so . Hence, .
2. (IMO '59) Prove that is irreducible for every natural number .
Solution: is irreducible if and only if the numerator and denominator have no common factor, i.e. their greatest common divisor is 1. Applying the Euclidean Algorithm,
Hence, , which shows that the fraction is irreducible.