The Euclidean Algorithm
Before finishing our discussion on congruences, we'll take a little side tangent into the Euclidean Algorithm. You'll soon see why.
Readings
Euclidean Algorithm
There are many ways to think of/view the Euclidean Algorithm. I have two videos below, one showing an intuitive sense of how and why it works, and another showing a more visual idea. Both are valuable, but after you've watched both videos, you should decide which method will help you personally remember how the euclidean algorithm works.
Below, I've also written the algorithm in Python. You should play around, using different numbers, and see if you can match the output given by the computer!
While I've just shown this algorithm can be coded, understanding how it works, and being able to follow it, will help you reason through other problems. Right now, we're looking through the lense of GCD, but try to think of what other problems it could solve!