Euclid’s algorithm

Extended Euclid’s algorithm

The extended Euclid’s algorithm can be used to find a pair such that as required by Bézout’s lemma.

Modular multiplicative inverse

To calculate the inverse of in

1. Create an equation in the form of .
2. Create a new equation where and
3. Continue until
4. Convert each equation to the form
5. Starting from the equation where , substitute your values slowly working upwards
6. In the final steps, any s disappear and .

---

tidy | en | sembr