Extended Euclidean Algorithm and Modular Inverse
Introduction The next topic we will cover in mathematics foundations is the Extended Euclidean Algorithm (EEA) and modular inverse. In the topic Introduction to Modular Arithmetic we discussed that division is tricky in modular arithmetic. Today we are going to tackle this problem and see how division works and when we can use it. But first, we need to talk about greatest common divisor and the Euclidean Algorithm. So let’s take this step-by-step. ...