gcd(a,b)=gcd(b,a mod b); lcm(a,b)=|a/gcd(a,b)*b|; values ax+by are exactly multiples of gcd(a,b).
Recognition signals
A largest common unit is requested
Ratios need canonical keys
Multiple periods must align
Divisibility groups or step reachability appear
Only the intersection of prime factors matters
False friends
Signal
Why it is different
Full prime exponents are required
GCD summarizes common factors; factorize when individual exponents matter.
Approximate real-valued ratios
GCD is exact integer arithmetic; floating-point comparisons need an error model.
Core invariant
Each Euclidean step preserves the set of common divisors while the second argument strictly decreases to zero.
State, transition, and processing order
Item
Definition
State
The current integer pair (a,b), plus a sign convention for normalization.
Transition
Repeat (a,b)=(b,a%b); on termination |a| is the GCD.
Frontier / order
The remainder carries the common-factor information not yet eliminated and decreases numerically.
Python skeleton
def gcd(a, b):
a, b = abs(a), abs(b)
while b:
a, b = b, a % b
return a
def lcm(a, b):
return 0 if a == 0 or b == 0 else abs(a // gcd(a,b) * b)
def normalize_ratio(x, y):
if y == 0: return (1 if x > 0 else -1 if x < 0 else 0, 0)
if y < 0: x, y = -x, -y
g = gcd(x, y)
return (x // g, y // g)
Correctness sketch
Every divisor of a and b also divides a-qb=a%b.
Every divisor of b and the remainder also divides a, so common divisors are preserved.
Remainders decrease, ending at (g,0).
Dividing a ratio by g yields a unique form under a fixed sign convention.
Complexity
Time
Space
Parameters
O(log min(|a|,|b|))
O(1)
integer inputs a and b; fold the operation for many values
Edge cases
gcd(0,0) is conventionally zero
Normalize negative inputs
LCM with zero is zero
Divide before multiplying to avoid overflow
A zero denominator needs a separate canonical form
Error patterns
Pattern
Why it fails / fix
Multiplying before LCM division
This can overflow; divide by gcd first.
Inconsistent signs
Equivalent ratios become different keys.
Floating-point division for ratio keys
Precision and zero denominators break equivalence.
Selection and exclusion rules
Common units, divisibility steps, or canonical ratios: think GCD first.
Need every factor or exponent: factorize.
Period alignment uses LCM, with range checks.
For hashable ratios, force a sign convention and handle the zero vector.