Euclidean Algorithm

Math for CS · Axiom Academy

Fast computation of GCD using remainder operations The Euclidean algorithm is one of the oldest and most efficient algorithms in computer science. It computes the GCD of two integers using a simple repeated division process. Extended Euclidean Algorithm (Preview) A more powerful version, the Extended Euclidean Algorithm, finds integers x, y such that: This is crucial for finding modular inverses in RSA encryption and solving linear Diophantine equations. We'll explore this in depth in a later lesson! The Euclidean algorithm uses the recurrence: Terminates when remainder is 0; last non-zero remainder is the GCD Time complexity is — extremely efficient Only uses basic operations: division and modulo Foundation for extended algorithm and cryptographic applications

This is the written version of the interactive lesson above. See the full Math for CS course.