The greatest common divisor can be found without listing every divisor. The key is to replace a pair of integers by a smaller pair with exactly the same common divisors, then repeat.

Greatest common divisors

Let $a,b\in\mathbb Z$ and suppose they are not both zero. Their greatest common divisor, written $\gcd(a,b)$, is the greatest positive integer that divides both $a$ and $b$. Equivalently, $d=\gcd(a,b)$ means

$$\boxed{ d>0,\qquad d\mid a,\qquad d\mid b, \qquad c\mid a\text{ and }c\mid b\Longrightarrow |c|\le d. }$$

The absolute value in the last condition accounts for negative common divisors. In particular, for $a\ne0$,

$$\gcd(a,0)=|a|.$$

The pair $(0,0)$ is excluded because every nonzero integer divides both entries, so there is no greatest positive common divisor.

For example, the positive common divisors of $16$ and $24$ are $1,2,4,8$, so

$$\gcd(16,24)=8.$$

Why listing divisors does not scale

For a positive integer $n$, a direct method tests possible divisors up to $\sqrt n$. A divisor found below that point also reveals its complementary divisor $n/d$, so the method still recovers divisors larger than $\sqrt n$. If $n$ has binary input length $L$, then $L\approx\log_2 n$, while the number of trial divisions is roughly

$$\sqrt n=2^{\frac12\log_2 n}\approx(\sqrt2)^L.$$

That is exponential in the number of input bits. Euclid's algorithm avoids this divisor search.

The division algorithm

For every $a,b\in\mathbb Z$ with $b\ne0$, there are unique integers $q$ and $r$ such that

$$\boxed{a=qb+r, \qquad 0\le r<|b|.}$$

The integer $q$ is the quotient, and $r$ is the remainder. The remainder condition is part of the theorem; without it, many different pairs would satisfy $a=qb+r$.

Existence

First suppose $b>0$. If $a\ge b$, long division—or repeated subtraction of $b$—produces a quotient and a remainder in the required range. If $a<b$, choose a nonnegative integer $k$ large enough that $a+kb\ge b$. Apply the first case to $a+kb$:

$$a+kb=q'b+r, \qquad 0\le r<b.$$

Subtracting $kb$ gives $a=(q'-k)b+r$. If $b<0$, apply the positive-divisor case to $-b$ and rewrite $q'(-b)$ as $(-q')b$. These cases cover every nonzero integer $b$.

Negative-dividend example

The quotient is allowed to be negative. For $a=-5$ and $b=3$,

$$-5=3(-2)+1, \qquad 0\le1<3.$$

Thus the quotient is $-2$ and the remainder is $1$.

Uniqueness proof

Suppose two quotient–remainder pairs both satisfy the theorem:

$$\begin{aligned} a&=q_1b+r_1, & 0&\le r_1<|b|,\\ a&=q_2b+r_2, & 0&\le r_2<|b|. \end{aligned}$$

Subtract the two equations:

$$0=(q_1-q_2)b+(r_1-r_2), \qquad r_2-r_1=(q_1-q_2)b.$$

Therefore $b\mid(r_2-r_1)$. The remainder bounds also give

$$-|b|<r_2-r_1<|b|.$$

The only multiple of $b$ strictly between $-|b|$ and $|b|$ is $0$. Hence $r_2-r_1=0$, so $r_1=r_2$. Returning to the subtracted equation and using $b\ne0$ then gives

$$(q_1-q_2)b=0 \quad\Longrightarrow\quad q_1=q_2.$$

Both the quotient and the remainder are unique.

The gcd reduction theorem

Let $a,b,q,r\in\mathbb Z$, with $(a,b)\ne(0,0)$. If

$$a=qb+r,$$

then

$$\boxed{\gcd(a,b)=\gcd(b,r).}$$

The theorem does more than preserve the value of the gcd: the two pairs have exactly the same common divisors.

Proof by matching common-divisor sets

Let

$$C(u,v)=\{c\in\mathbb Z\mid c\mid u\text{ and }c\mid v\}.$$

We prove both inclusions.

Take $c\in C(a,b)$. Then $c\mid a$ and $c\mid b$. Since a divisor of $b$ also divides $qb$, the difference property gives

$$c\mid(a-qb)=r.$$

Thus $c$ divides both $b$ and $r$, so $c\in C(b,r)$. Therefore $C(a,b)\subseteq C(b,r)$.

Conversely, take $c\in C(b,r)$. Then $c\mid b$ and $c\mid r$, so $c$ divides their integer linear combination

$$qb+r=a.$$

Thus $c$ divides both $a$ and $b$, so $c\in C(a,b)$. Therefore $C(b,r)\subseteq C(a,b)$.

The two inclusions show

$$C(a,b)=C(b,r),$$

so the greatest positive element of each set is the same. Hence $\gcd(a,b)=\gcd(b,r)$.

Euclid's algorithm

For positive inputs, set $r_{-2}=a$ and $r_{-1}=b$, then repeatedly apply the division algorithm:

$$\begin{aligned} a&=q_0b+r_0, & 0&\le r_0<b,\\ b&=q_1r_0+r_1, & 0&\le r_1<r_0,\\ r_0&=q_2r_1+r_2, & 0&\le r_2<r_1,\\ &\hspace{2.5em}\vdots \end{aligned}$$

Each step preserves the gcd. Stop at the first index $m$ for which $r_m=0$, then return the positive divisor $r_{m-1}$. If the first division already has remainder zero, this returns $r_{-1}=b$.

Why it terminates

Every nonzero remainder is a nonnegative integer strictly smaller than the preceding positive divisor. If the first remainder is not already zero, the positive remainders form a strictly decreasing sequence. Such a sequence cannot continue forever, so a zero remainder must eventually appear.

If $r_m=0$ is the first zero remainder, then the final division has positive divisor $r_{m-1}$. Repeated use of the reduction theorem gives

$$\gcd(a,b)=\gcd(r_{-2},r_{-1})=\cdots=\gcd(r_{m-2},r_{m-1})=r_{m-1}.$$

Example: $\gcd(35,21)$

$$\begin{aligned} 35&=1(21)+14,\\ 21&=1(14)+7,\\ 14&=2(7)+0. \end{aligned}$$

The last nonzero remainder is $7$, so

$$\gcd(35,21)=7.$$

Bézout's identity

Let $a,b\in\mathbb Z$ be not both zero, and let $d=\gcd(a,b)$. Bézout's identity says that there are integers $s$ and $t$ such that

$$\boxed{d=sa+tb.}$$

The numbers $s$ and $t$ are called Bézout coefficients. They need not be positive or unique.

Why back-substitution works

Each Euclidean step can be rearranged as

$$r_i=r_{i-2}-q_i r_{i-1}.$$

The starting values $r_{-2}=a$ and $r_{-1}=b$ are already integer linear combinations of $a$ and $b$. The displayed equation shows inductively that every later remainder is also an integer linear combination of $a$ and $b$. Since the divisor immediately before the first zero remainder equals $d$, reversing the Euclidean steps expresses $d$ as $sa+tb$.

The zero-input cases are direct. If $b=0$, then $d=|a|$: choose $s=1,t=0$ when $a>0$, and $s=-1,t=0$ when $a<0$. If $a=0$, choose $s=0,t=1$ when $b>0$, and $s=0,t=-1$ when $b<0$. When both inputs are nonzero, apply the positive-input argument to $|a|$ and $|b|$, then change the corresponding coefficient signs when an original input is negative. This completes the proof for all integer inputs that are not both zero.

For the smaller example above,

$$7=21-14=21-(35-21)=-35+2(21).$$

Thus one pair of Bézout coefficients for $35$ and $21$ is $s=-1$, $t=2$.

Extended example: $\gcd(515,42)$

Run Euclid's algorithm:

$$\begin{aligned} 515&=12(42)+11,\\ 42&=3(11)+9,\\ 11&=1(9)+2,\\ 9&=4(2)+1,\\ 2&=2(1)+0. \end{aligned}$$

The last nonzero remainder is $1$, so $\gcd(515,42)=1$. Now substitute backward:

$$\begin{aligned} 1 &=9-4(2)\\ &=9-4(11-9)\\ &=5(9)-4(11)\\ &=5(42-3(11))-4(11)\\ &=5(42)-19(11)\\ &=5(42)-19(515-12(42))\\ &=233(42)-19(515). \end{aligned}$$

Therefore,

$$\boxed{1=-19(515)+233(42).}$$

This simultaneously verifies the gcd and gives Bézout coefficients $s=-19$ and $t=233$.