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>x=pq_1+r_1</math>
 
 
 
<math>p=r_1 q_2 + r_2</math>
 
 
 
<math>r_1=r_2 q_3 + 0</math>
 
 
 
<math>\vdots</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 12:02, 20 February 2007