Euclidean Division Algorithm

Revision as of 14:20, 19 February 2007 by Lemondemon (talk | contribs) (Fixed a spelling error.)

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}$


$p=r_1 q_2 + r_2$

$r_1=r_2 q_3 + 0$


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

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

Invalid username
Login to AoPS