Euclid's algorithm finds gcd(a, b) by repeatedly replacing (a, b) with (b, a mod b) until b becomes zero. The remaining a is the gcd. This method is fast, elegant, and foundational for modular arithmetic and cryptography.
int gcd(int a, int b) {
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return abs(a);
}gcd(a, b) equals gcd(b, a mod b). Repeating this reduction quickly shrinks the numbers.
Remainders strictly decrease and eventually become zero, so the loop always terminates.
Used in modular inverses, CRT, and many competitive programming and cryptography routines.
Quiz coming soon for this algorithm.