Greatest common divisor ($\gcd$)

The greatest common divisor of integers $a$ and $b$ is the largest positive integer dividing both.

For positive integers $m,n,k$, the greatest common divisor scales by the common multiplier $k$. If $d=\gcd (m,n)$, then $kd$ is a common divisor of $km,kn$. Meanwhile Bézout's identity expresses $kd$ as an integer linear combination of $km,kn$, so their greatest common divisor divides $kd$. These two comparisons prove the identity without prime factorization.

Two integers $a$ and $b$ are coprime when $\gcd (a,b)=1$.