GCD & the Euclidean Algorithm

By the end, you can

• Define the GCD and explain the tiling visualisation.
• State Euclid's identity and the base case, and explain why the identity holds.
• Trace the Euclidean algorithm by hand, computing each remainder step.
• Prove that the algorithm always terminates using the strictly-decreasing remainder argument.
• Explain why the modulo form is faster than the subtraction form.
• State the O(log min(a, b)) complexity and identify Fibonacci inputs as the worst case.
• Describe what the Extended Euclidean Algorithm produces (Bézout coefficients).
• Apply the GCD to reduce fractions, compute the LCM, and determine when a modular inverse exists.