- 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

Richard Liska