Greatest common divisor (GCD) of two numbers
Categories: number theory
The greatest common divisor (GCD) of two non-zero integers a and b is the largest positive integer that divides into both a and b.
It is usually written as gcd(a, b).
Here are some examples:
- The GCD of 12 and 18 is 6, because that is the largest number that divides into both.
- The GCD of 60 and 100 is 20.
- The GCD of 16 and 27 is 1. There is no other number that divides into both 16 and 27. If two numbers have no common divisor, we say that they are relatively prime.
GCD and prime factors
The GCD can be found from the prime factors of the two numbers. For example:
$$ \begin{align} 12 = 2 \times 2 \times 3 \newline 18 = 2 \times 3 \times 3 \end{align} $$
For each prime factor we take the lowest multiplicity for either number:
- For 2, the lowest multiplicity is 21 that occurs in the number 18.
- For 3, the lowest multiplicity is 31 that occurs in the number 12.
The LCM of 12 and 18 is therefore:
$$ 2^1 \times 3^1 = 2 \times 3 = 6 $$
Looking at the second example, 60 and 100:
$$ \begin{align} 60 = 2 \times 2 \times 3 \times 5\newline 100 = 2 \times 2 \times 5 \times 5 \end{align} $$
- For 2, the lowest multiplicity is 2 that occurs in the both 60 and 100.
- For 3, the lowest multiplicity is 0 that occurs in the number 100 - 3 is not a factor of 100, so it can't be a factor of the GCD.
- For 5, the lowest multiplicity is 1 that occurs in the number 60.
The LCM of 60 and 100 is therefore:
$$ 2^2 \times 5^1 = 4 \times 5 = 20 $$
Euclid's algorithm
Euclid's algorithm provides a simple way to find gcd(a, b) of two different, positive integers a and b:
- Find the positive difference between a and b, and call it c.
- Replace the larger of a or b with value c.
- Repeat from step 1 until a and b have equal values.
The final value of a and b is the GCD.
Let's take the example of finding the GCD of 60 and 100:
- Initially a is 60, b is 100.
- The positive difference gives c = 40.
- Replace the larger (b) with c. Now a is 60, b is 40.
- The positive difference gives c = 20.
- Replace the larger (a) with c. Now a is 20, b is 40.
- The positive difference gives c = 20.
- Replace the larger (b) with c. Now a is 20, b is 20.
The values are now equal, so the GCD is 20.
See also
Join the GraphicMaths Newletter
Sign up using this form to receive an email when new content is added:
Popular tags
adder adjacency matrix alu and gate angle area argand diagram binary maths cartesian equation chain rule chord circle cofactor combinations complex polygon complex power complex root cosh cosine cosine rule cpu cube decagon demorgans law derivative determinant diagonal directrix dodecagon ellipse equilateral triangle eulers formula exponent exponential exterior angle first principles flip-flop focus gabriels horn gradient graph hendecagon heptagon hexagon horizontal hyperbola hyperbolic function infinity integration by substitution interior angle inverse hyperbolic function inverse matrix irregular polygon isosceles trapezium isosceles triangle kite koch curve l system locus maclaurin series major axis matrix matrix algebra minor axis nand gate newton raphson method nonagon nor gate normal not gate octagon or gate parabola parallelogram parametric equation pentagon perimeter permutations polar coordinates polynomial power probability probability distribution product rule pythagoras proof quadrilateral radians radius rectangle regular polygon rhombus root set set-reset flip-flop sine sine rule sinh sloping lines solving equations solving triangles square standard curves star polygon straight line graphs surface of revolution symmetry tangent tanh transformations trapezium triangle turtle graphics vertical volume of revolution xnor gate xor gate