GCD and Euclid's Algorithm - Maple Help

Online Help

All Products    Maple    MapleSim

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:



 GCDa,  b = GCDa,b




 GCDa+bc,  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 ab (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 rn1 by rn

   Increment n



return rn1


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