The greatest common divisor of integers $a$ and $b$, not both zero, is the largest positive integer dividing both. It is written

$$\gcd(a,b).$$

Two integers are coprime when their gcd is $1$.

Euclidean algorithm

If

$$a=bq+r,$$

then

$$\gcd(a,b)=\gcd(b,r).$$

Repeatedly replacing the larger pair by the divisor and remainder eventually reaches a zero remainder. The last nonzero remainder is the gcd.

For example,

$$252=105\cdot2+42,$$ $$105=42\cdot2+21,$$ $$42=21\cdot2,$$

so

$$\gcd(252,105)=21.$$

Running the substitutions backwards expresses the gcd as an integer combination

$$\gcd(a,b)=ax+by,$$

which is Bézout's identity and is central to modular inverses.