Euclidean Algorithm

Introduction

Although we have functions that can compute our $\gcd$easily it's important enough that we need to give and study an algorithm for it: the euclidean algorithm.

It's extended version will help us calculate modular inverses which we will define a bit later.

Euclidean Algorithm

Important Remark

If and then . Therefore

Algorithm

We write the following:

Or iteratively until we find a . Then we stop

Now here's the trick:

If then divides

Example:

Calculate

Code

Exercises:

1. Pick 2 numbers and calculate their by hand.

2. Implement the algorithm in Python / Sage and play with it. Do not copy paste the code

Extended Euclidean Algorithm

Bezout's identity

Let . Then there exists such that

The extended euclidean algorithm aims to find given