Euclidean algorithm

For positive integers $a,b$, the Euclidean algorithm repeatedly performs division with remainder: write $a=qb+r$ with $0\le r<b$, then replace $(a,b)$ by $(b,r)$ until the second entry is zero. The final nonzero entry is their greatest common divisor. A remainder preserves the set of common divisors: an integer divides $a$ and $b$ exactly when it divides $b$ and $a-qb$. The positive remainders strictly decrease, so the calculation terminates.

The complete calculation for $252$ and $198$ isHence $\gcd (252,198)=18$. The fraction $252/198$ reduces to $14/11$ by dividing numerator and denominator by that common factor. The same remainder calculation has a geometric interpretation: remove squares from a $252$-by-$198$ rectangle, then repeat on the remaining strip. Each division step records how many equal squares fit and the width of the new strip.

The procedure does more than test individual divisors. Each step replaces the whole common-divisor problem by a smaller equivalent one. Euclid's Book VII, Proposition 2 describes the corresponding repeated-subtraction construction; batching those subtractions into division with remainder gives the present formulation. ^[ref]

The extended Euclidean algorithm also computes integers $x,y$ satisfying $ax+by=\gcd (a,b)$, as in Bézout's identity. Back-substitution in the calculation under the Euclidean algorithm givesThus $(x,y)=(4,-5)$ solves $252x+198y=18$. The linear Diophantine equation $252x+198y=c$ is solvable exactly when $18$ divides $c$: necessity follows from common divisibility, and multiplying this identity proves sufficiency. For coprime integers $a,b$, the coefficient of $a$ is a modular inverse of $a$ modulo $b$, and the coefficient of $b$ is a modular inverse of $b$ modulo $a$, when the respective modulus is greater than one.

A linear Diophantine equation in two variables has the form $ax+by=c$ with integer coefficients and seeks integer solutions.

If $a,b$ are nonzero integers, $d=\gcd (a,b)$, and $(x_0,y_0)$ is one solution of the linear Diophantine equation $ax+by=c$, then all solutions areSubtract two solutions and use the fact that $a/d$ and $b/d$ are coprime integers. The linear Diophantine equation solvability criterion says that a particular solution exists exactly when $d$ divides $c$; the extended Euclidean algorithm constructs one. This parametrization separates existence from the complete family of answers.

The equation $ax+by=c$ has an integer solution exactly when $\gcd (a,b)$ divides $c$. Bézout's identity proves sufficiency, while every integer linear combination of $a,b$ is divisible by their greatest common divisor.