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 13: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