EUCLIDEAN ALGORITHM


Example: Use the Euclidean Algorithm to find gcd( 175, 77 ).

175 = 2 x 77 + 21,    gcd( 175, 77 ) = gcd( 77, 21 )
          --

 77 = 3 x 21 + 14,                   = gcd( 21 , 14 )
          --

 21 = 1 x 14 +  7,                   = gcd( 14 ,  7 )
          --

 14 = 2 x  7 +  0,                   = 7
           -

Note that I like to underline the term that came from the
remainder in the previous equation.  This is useful for
bookkeeping purposes.

Note also that each number on the right (the remainders
like 21, 14, 7, and 0) travel one unit southwest as we
go from one equation to the next.  Thus the motion
of numbers in the Euclidean algorithm looks like

                      175   77   21
                           /    /
                          /    /
                         /    /
                        V    V
                       77   21   14
                           /    /
                          /    /
                         /    /
                        V    V
                       21   14    7
                           /    /
                          /    /
                         /    /
                        V    V
                       14    7    0.