

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 find the GCD.
 
−   
−  <math>x \bmod p = r_1</math>
 
−   
−  <math>p \bmod r_1 = r_2</math>
 
−  <math> \vdots</math>
 
−   
−  <math>r_{n1} \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_{k1}</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_{n1}=r_n q_{n=1} +r_{n+2}</math>
 
−   
−  and so <math>GCD({x,p}) = r_n</math>
 