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:
for any integer
The Euclidean Algorithm is a sequence of steps that use the above rules to find the GCD for any two integers and .
First, assume and are both non-negative and (otherwise we can use rules 1 and 2 above).
Now, let , , .
while do
Let be the remainder of dividing by
Increment
end
return
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 and , and repeatedly subtracts squares, until what remains is a square. That square has sides of length the GCD of and !
The GCD of:
& is:
More MathApps
MathApps/DiscreteMathematics
Download Help Document
