GCD of integers

 

• for two integers for which , we define their quotient and remainder as two integers for which

  

  where

• if we denote the greatest common divisor of as and if is nonzero, then

  

• divides both and ; it also divides so it also has to divide

• the Euclidean algorithm for calculating the greatest common divisor is based on this identity

• Euclidean algorithm for calculating the GCD of two integers

        gcd := GCDI(a, b) :=
          [a, b are integers
           algorithm used:
             rem(a, b) - remainder after dividing integer a by integer b]
        1. if  a  <  b  then
              r := a
              a := b
              b := r
           fi
        2. while  b != 0  do                           %!= means not equal
              r := rem(a, b)
              a := b
              b := r
           od
        3. return a