# Difference between revisions of "Euclidean Division Algorithm"

Lemondemon (talk | contribs) (Created the article.) |
Lemondemon (talk | contribs) m (Fixed a spelling error.) |
||

Line 5: | Line 5: | ||

---- | ---- | ||

− | This also means that one can use modular arithmetic to | + | This also means that one can use modular arithmetic to find the GCD. |

<math>x \bmod p = r_1</math> | <math>x \bmod p = r_1</math> |

## Revision as of 14:20, 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 find the GCD.

Then

For example:

Another method, essentially the same thing, is as follows:

for

and so