Greatest Common Divisor and the Euclidean Algorithm
The greatest common divisor (GCD) of two integers (not both 0) is the largest positive integer which divides both of them.
There are four simple rules which allow us to compute the GCD of two integers:
GCD−a, b = GCDa,b
GCDa+b⋅c, b = GCDa,b for any integer c
GCDa, 0 = a
The Euclidean Algorithm is a sequence of steps that use the above rules to find the GCD for any two integers a and b.
First, assume a and b are both non-negative and a≥b (otherwise we can use rules 1 and 2 above).
Now, let r1=a, r2=b, n=2.
while rn>0 do
Let rn+1 be the remainder of dividing rn−1 by rn
Input two integers in the boxes below. Click "Find GCD" and then "Next Step" to follow the steps of the Euclidean Algorithm to find the greatest common divisor of the two integers. Click "Zoom" if the image gets too small to see. The animation starts with a rectangle with the dimensions of a and b, and repeatedly subtracts squares, until what remains is a square. That square has sides of length the GCD of a and b!
The GCD of:
Download Help Document