Euclid’s algorithm

Extended Euclid’s algorithm

The extended Euclid’s algorithm can be used to find a pair 𝑠,𝑡 ∈ℤ such that gcd(𝑎,𝑏) =𝑠𝑎 +𝑡𝑏 as required by Bézout’s lemma.

Modular multiplicative inverse

To calculate the inverse of 𝑎 in mod𝑛

1. Create an equation in the form of 𝑛 =𝑎(𝑞) +𝑟.
2. Create a new equation where 𝑎 →𝑛 and 𝑟 →𝑎
3. Continue until 𝑟 =1
4. Convert each equation to the form 𝑟 =𝑛 +𝑎( −𝑞)
5. Starting from the equation where 𝑟 =1, substitute your values slowly working upwards
6. In the final steps, any 𝑛s disappear and −𝑥 →𝑛 −𝑥.

---

tidy | en | SemBr