gcd by repeated remainders, then x and y with ax + by = gcd by back-substitution, and modular inverses.
This interactive visualization needs JavaScript.