One of the most important integers associated with a given set of integers is their highest common factor, h.c.f., or greatest common divisor, g.c.d., i.e. the largest positive integer that divides all of them. It is denoted by (a,b). It is easy to determine the h.c.f. when the prime decompositions of the integers are given:
When the prime factors are not known a method can be used that involves successive use of the division algorithm.
Example: Find (30 031, 16 579)
From the division algorithm,
The g.c.d. is 59, reached after 6 divisions. i.e. (30 031, 16 579) = 59
Use the calculator to find the g.c.d. of any two numbers.
The g.c.d. of a and b is the smallest positive linear combination
of a and b.
How do we get this linear combination?
One way is the Euclidean algorithm in reverse:
Created by Jamie Coventry