> For the complete documentation index, see [llms.txt](https://cryptohack.gitbook.io/cryptobook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cryptohack.gitbook.io/cryptobook/fundamentals/division-and-gcd/euclidean-algorithm.md).

# 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 $$a = b \cdot q + r$$and $$d = \gcd(a, b)$$ then $$d | r$$. Therefore $$\gcd(a, b) = \gcd(b, r)$$

### Algorithm 

We write the following:

$$a = q\_0 \cdot b + r\_0 \  b = q\_1 \cdot r\_0 + r\_1 \  r\_0 = q\_2 \cdot r\_1 + r\_2 \  \vdots \ r\_{n-2} = r\_ {n-1} \cdot q\_{n - 1} + r\_n \ r\_n = 0$$ 

Or iteratively $$r\_{k-2} = q\_k \cdot r\_{k-1} + r\_k$$ until we find a $$0$$. Then we stop

Now here's the trick: 

$$
\gcd(a, b) = gcd(b, r\_0) = gcd(r\_0, r\_1) = \dots = \gcd(r\_{n-2}, r\_{n-1}) = r\_{n-1} = d
$$

If $$d = \gcd(a, b)$$ then $$d$$ divides $$r\_0, r\_1, ... r\_{n-1}$$

{% hint style="success" %}
Pause and ponder. Make you you understand why that works.
{% endhint %}

**Example:** 

Calculate $$\gcd(24, 15)$$

$$24 = 1 \cdot 15 + 9 \ 15 = 1 \cdot 9 + 6 \ 9 = 1 \cdot 6 + 3 \ 6 = 2 \cdot 3 + 0 \Rightarrow 3 = \gcd(24, 15)$$

**Code**

```python
def my_gcd(a, b):
    # If a < b swap them
    if a < b: 
        a, b = b, a
    # If we encounter 0 return a
    if b == 0: 
        return a
    else:
        r = a % b
        return my_gcd(b, r)

print(my_gcd(24, 15))
# 3
```

**Exercises**:

1. Pick 2 numbers and calculate their $$\gcd$$by hand.&#x20;
2. Implement the algorithm in Python / Sage and play with it. **Do not copy paste the code**

## Extended Euclidean Algorithm

{% hint style="danger" %}
This section needs to be expanded a bit.
{% endhint %}

**Bezout's identity**

> Let $$d = \gcd(a, b)$$. Then there exists $$u, v$$ such that $$au + bv = d$$&#x20;

The extended euclidean algorithm aims to find $$d = \gcd(a, b), \text{ and }u, v$$given $$a, b$$

```python
# In sage we have the `xgcd` function
a = 24
b = 15
g, u, v = xgcd(a, b)
print(g, u, v)
# 3 2 -3 

print(u * a + v * b)
# 3 -> because 24 * 2 - 15 * 3 = 48 - 45 = 3
```