Euclidean Division Algorithm

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$

Page

Toolbox

Search

Euclidean Division Algorithm