Greatest Common Divisor and the Euclidean Algorithm
Main Concept
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=GCDb,a
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
Increment n
end
return rn−1
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:
& is:
More MathApps
MathApps/DiscreteMathematics
Download Help Document
