|
|
| 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>
| |
