Euclidean Division Algorithm
The Euclidean Division Algorithm (or Euclid's Algorithm) is an algorithm that finds the Greatest common divisor (GCD) of two elements of a Euclidean Domain (generally ℤ, the set of integers) without factoring them.
The basic idea is that
This also means that one can use modular arithmetic to fine the GCD.
Another method, essentially the same thing, is as follows: