Difference between revisions of "Euclidean Division Algorithm"
Lemondemon (talk | contribs) (Created the article.) |
(No difference)
|
Revision as of 14:11, 19 February 2007
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.
Then
For example:
Another method, essentially the same thing, is as follows:
for
and so