### The Euclidean Algorithm:

This is best explained using an example. What is the greatest common divisor between 120 and 16?- First
calculate 120 mod 16 = 8.

- Then
replace 120 with 16, and 16 with the
remainder of the last step,
8. 16 mod 8 = 0

- The
result of zero signals the end of the algorithm, and the last
divisor
(8) is the greatest common divisor of 120 and 16.

- 150
mod 23 = 12

- 23
mod 12 = 11

- 12
mod 11 = 1

- 11
mod 1 = 0

### The Extended Euclidean Algorithm:

The Extended Euclidean Algorithm is, as its name suggests, an extension to this algorithm.Each stage in the Euclidean Algorithm can be written as an iterative equation:

$r_i
= ax_i + by_i$

and
the remainders as:

$r_i
= r_{i-2} – q_i \cdot r_i$

Or,
in words, the remainder value two steps ago (120 on the first
example) minus the last quotient (7) times the value one step ago
(16).
$r_2
= 120 – 7 \cdot 16$

$r_2
= 8$.

Substituting:
$r_i
= (ax_{i-2} + by_{i-2}) – q_{i – 1} \cdot (ax_{i – 1} + by_{i –
1} )$

Our
initial values are:
$r_1
= a = a \times 1 + b \times 0$

$r_2
= b = b \times 0 + b \times 1$

$x_1
= 1, y_1 = 0$

$x_2
= 0, y_2 = 1$

And
(using the formula for the remainders):
$x_i
= x_{i– 2} – q_{i – 1} \cdot x_{i–
1 } $

$y_i
= x_{i– 2} – q_{i – 1} \cdot y_{i – 1} $

q | r | x | y |
---|---|---|---|

120 | 1 | 0 | |

16 | 0 | 1 | |

7 | (120*1 + 16*0) – 7*(120*0 + 16*1) =8 |
1 – 7*0
= 1 |
0 – 7*1
= -7 |

2 | (120*0 + 16*1) – 2 *(120*1 + 16* -7) = 0 |

Taking the second last set of values, 120 * 1 + 16* – 7 = 8.

## No comments:

## Post a Comment