Difference between revisions of "Euclidean Division Algorithm"

(Created the article.)
(Changed to a redirect to "Euclidean algorithm")
(One intermediate revision by the same user not shown)
Line 1: Line 1:
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.
#REDIRECT [[Euclidean algorithm]]
The basic idea is that <math>GCD({a,b}) = GCD({a,a - b})</math>
This also means that one can use modular arithmetic to fine the GCD.
<math>x \bmod p = r_1</math>
<math>p \bmod r_1 = r_2</math>
<math> \vdots</math>
<math>r_{n-1} \bmod r_n = 0</math>
Then <math>GCD({x,p}) = r_n</math>
For example:
<math>119 \bmod 34 = 17</math>
<math>34 \bmod 17 = 0</math>
Another method, essentially the same thing, is as follows:
for <math>r_{k+1} < r_k < r_{k-1}</math>
<math>p=r_1 q_2 + r_2</math>
<math>r_1=r_2 q_3 + 0</math>
<math>r_{n-1}=r_n q_{n=1} +r_{n+2}</math>
and so <math>GCD({x,p}) = r_n</math>

Latest revision as of 13:02, 20 February 2007

Invalid username
Login to AoPS