 GCD and Euclid's Algorithm - Maple Help

Home : Support : Online Help : Math Apps : Discrete Mathematics : GCD and Euclid's Algorithm

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:

 •
 • $\mathrm{GCD}\left(a,b\right)=\mathrm{GCD}\left(b,a\right)$
 • for any integer $c$
 •

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\ge b$ (otherwise we can use rules 1 and 2 above).

Now, let , ${r}_{2}=b$, $n=2$.

while ${r}_{n}>0$ do

Let ${r}_{n+1}$ be the remainder of dividing ${r}_{n-1}$ by ${r}_{n}$

Increment $n$

end

return ${r}_{n-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