GCD and Extended Euclid
The basic divisibility toolkit for reducing fractions, solving linear equations, and building modular arithmetic routines.
GCD and Extended Euclid
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
The greatest common divisor is one of the smallest ideas in number theory, but it sits underneath modular inverses, CRT, fraction normalization, and linear Diophantine equations. Extended Euclid is the version worth remembering in contests because it produces coefficients, not just the gcd itself.
When to Use It
Use this when:
divisibility is part of the condition,
you need to simplify a fraction or a ratio,
the equation looks like \(ax + by = c\),
a modular inverse exists only when the gcd condition is satisfied.
Core Idea
Euclid's algorithm repeatedly replaces \((a, b)\) by \((b, a \bmod b)\). The gcd does not change under that step, and the numbers get smaller quickly.
Extended Euclid keeps track of coefficients \(x, y\) such that \[ ax + by = \gcd(a, b). \] Those coefficients are exactly what later number-theory algorithms need.
Key Insight
The recursive remainder relation \[ \gcd(a, b) = \gcd(b, a \bmod b) \] is not just a gcd trick. It lets every remainder step be unwound into a linear combination of the original numbers. That is why extended Euclid can recover the coefficients.
Operations / Main Technique
gcd: decide divisibility and reduce ratios.
lcm: compute by \(a / \gcd(a,b) \cdot b\) to avoid overflow as much as possible.
extended gcd: recover coefficients.
Diophantine existence: \(ax + by = c\) is solvable iff \(\gcd(a,b)\) divides \(c\).
Worked example.
If \(\gcd(18, 30) = 6\), then \(18x + 30y = 12\) is solvable, but \(18x + 30y = 5\) is not.
Correctness Intuition
Each Euclid step preserves the set of common divisors, so it preserves the gcd. Extended Euclid simply records how the current pair came from the previous pair. Unwinding those steps reconstructs the linear combination for the original inputs.
Complexity Analysis
Euclid and extended Euclid run in \(O(\log \min(a, b))\) time and \(O(\log \min(a, b))\) recursion depth.
Implementation
The code includes:
gcd_ll,lcm_ll,ext_gcdproducing coefficients,a small solver for \(ax + by = c\).
Common Pitfalls
Forgetting that a modular inverse requires gcd \(= 1\).
Overflow in the direct formula \(a \cdot b / \gcd(a,b)\).
Losing sign conventions when negative numbers are allowed.
Treating one particular Diophantine solution as the only one.
Variants / Extensions
Modular inverse via extended Euclid.
Chinese remainder theorem.
Solving linear congruences.
Practice Problems
Count or construct solutions to \(ax + by = c\).
Normalize slope or direction pairs by gcd.
Check whether two periodic processes ever align.
References
Code
Contest-ready reference implementation for the idea explained above.
long long gcd_ll(long long a, long long b) {
while (b != 0) {
long long r = a % b;
a = b;
b = r;
}
return a >= 0 ? a : -a;
}
long long lcm_ll(long long a, long long b) {
return a / gcd_ll(a, b) * b;
}
long long ext_gcd(long long a, long long b, long long& x, long long& y) {
if (b == 0) {
x = (a >= 0 ? 1 : -1);
y = 0;
return a >= 0 ? a : -a;
}
long long x1, y1;
long long g = ext_gcd(b, a % b, x1, y1);
x = y1;
y = x1 - (a / b) * y1;
return g;
}
bool solve_linear_diophantine(long long a, long long b, long long c, long long& x, long long& y, long long& g) {
g = ext_gcd(a, b, x, y);
if (c % g != 0) {
return false;
}
x *= c / g;
y *= c / g;
return true;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.