Divisibility turns multiplication into an order relation on integers, and the Euclidean algorithm makes that relation computational. Its invariant is the ideal generated by two integers, which anticipates the ideal-theoretic language of algebraic number theory.
Divisibility and greatest common divisors
Definition. For \(a,b\in\mathbb Z\), \(a\mid b\) if \(b=ac\) for some \(c\in\mathbb Z\). A greatest common divisor of \(a,b\), not both zero, is the unique positive integer \(d\) satisfying \[ d\mid a,\quad d\mid b,\quad c\mid a,\ c\mid b\Longrightarrow c\mid d. \]
Theorem (division algorithm). For \(a\in\mathbb Z\) and \(b>0\), there are unique integers \(q,r\) such that \[ a=bq+r,\qquad0\le r<b. \]
Proof. The set \(\{a-bq:q\in\mathbb Z,\ a-bq\ge0\}\) is nonempty. Let \(r\) be its least element. If \(r\ge b\), then \(r-b\) is a smaller nonnegative element, a contradiction. If two decompositions exist, subtracting shows that \(b\mid(r-r')\); since \(|r-r'|<b\), one has \(r=r'\) and then \(q=q'\).
The Euclidean algorithm
Repeated division produces \[ \begin{aligned} a&=q_0b+r_1,\\ b&=q_1r_1+r_2,\\ &\ \vdots\\ r_{k-1}&=q_kr_k,\qquad r_k>0. \end{aligned} \] Because remainders strictly decrease, the process terminates.
Theorem. The last nonzero remainder is \(\gcd(a,b)\). Moreover there exist \(x,y\in\mathbb Z\) such that \[ \gcd(a,b)=ax+by. \]
Proof. At each division, \[ \gcd(u,v)=\gcd(v,u-qv), \] because the two pairs have exactly the same common divisors. Iterating proves the first claim. Substituting the remainder equations backward expresses \(r_k\) as an integer linear combination of \(a,b\), proving Bezout's identity.
Example. \[ 252=1\cdot198+54,\quad 198=3\cdot54+36,\quad 54=1\cdot36+18. \] Thus \(\gcd(252,198)=18\), and back-substitution gives \[ 18=4\cdot252-5\cdot198. \]
Linear Diophantine equations
Theorem. The equation \[ ax+by=c \] has an integer solution if and only if \(\gcd(a,b)\mid c\). If \((x_0,y_0)\) is one solution and \(d=\gcd(a,b)\), all solutions are \[ x=x_0+\frac{b}{d}t,\qquad y=y_0-\frac{a}{d}t,\qquad t\in\mathbb Z. \]
Proof. Necessity follows because every common divisor of \(a,b\) divides \(ax+by\). If \(d\mid c\), multiply a Bezout identity \(d=au+bv\) by \(c/d\). For the parametrization, subtract two solutions: \(a(x-x_0)=-b(y-y_0)\); after dividing by \(d\), coprimality of \(a/d\) and \(b/d\) gives the stated multiples.
More conceptually, \[ (a,b)=a\mathbb Z+b\mathbb Z=d\mathbb Z. \] The gcd is the positive generator of the ideal spanned by \(a,b\), while the lcm satisfies \(\gcd(a,b)\operatorname{lcm}(a,b)=|ab|\).