Difference between revisions of "Euclidean Division Algorithm"

Latest revision as of 13:02, 20 February 2007

Redirect to:

@@ 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_{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>