Euclid's Algorithm

Euclid's algorithm is the most efficient algorithm for finding the
greatest common factor of two numbers *a* and *m*. If they are
relatively prime, which means the greatest common factor is 1, then
Euclid's algorithm can also efficiently solve the modular equation

for an integer