Difference between revisions of "Euclidean Division Algorithm"

(Created the article.)
 
m (Fixed a spelling error.)
Line 5: Line 5:
 
----
 
----
  
This also means that one can use modular arithmetic to fine the GCD.
+
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 $GCD({a,b}) = GCD({a,a - b})$


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

$x \bmod p = r_1$

$p \bmod r_1 = r_2$ $\vdots$

$r_{n-1} \bmod r_n = 0$

Then $GCD({x,p}) = r_n$


For example:

$119 \bmod 34 = 17$

$34 \bmod 17 = 0$


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

for $r_{k+1} < r_k < r_{k-1}$

$x=pq_1+r_1$

$p=r_1 q_2 + r_2$

$r_1=r_2 q_3 + 0$

$\vdots$

$r_{n-1}=r_n q_{n=1} +r_{n+2}$

and so $GCD({x,p}) = r_n$