Divisibility and the greatest common divisor

A non-zero integer $b$ divides $a$ if $a = mb$ for some integer $m$ — dividing $a$ by $b$ leaves no remainder. This is written $b \mid a$, and $b$ is called a divisor of $a$. For example, $13 \mid 182$ because $182 = 14 \times 13$, and $17 \mid 289$ because $289 = 17 \times 17$.

Four properties follow directly from the definition:

• If $a \mid 1$, then $a = \pm 1$.
• If $a \mid b$ and $b \mid a$, then $a = \pm b$.
• Any $b \neq 0$ divides $0$.
• Transitivity: if $a \mid b$ and $b \mid c$, then $a \mid c$.

Transitivity holds because $a \mid b$ and $b \mid c$ mean $b = am$ and $c = bn$ for some integers $m, n$. Substituting the first into the second gives $c = amn$, so $a \mid c$. The lecture gives two instances of this: $3 \mid 9$ and $9 \mid 27$ give $3 \mid 27$; $11 \mid 66$ and $66 \mid 198$ give $11 \mid 198$.

A stronger property extends this to combinations. If $b \mid g$ and $b \mid h$, then $b$ divides $mg + nh$ for any integers $m$ and $n$ — not just $g + h$ or $g - h$. This is the linear combination property. The lecture’s example: $11 \mid 66$ and $11 \mid 77$, so $11$ divides $m \cdot 66 + n \cdot 77$ for any $m, n$. Writing $66 = 11k$ and $77 = 11l$, $m \cdot 66 + n \cdot 77 = m \cdot 11k + n \cdot 11l = 11(mk + nl),$ which is a multiple of $11$ regardless of what $m$ and $n$ are.

The division algorithm formalises ordinary long division. For a positive integer $n$ and a non-negative integer $a$, $a = qn + r, \quad 0 \le r < n, \quad q = \left\lfloor \frac{a}{n} \right\rfloor.$ $q$ is the quotient, $r$ is the remainder, and $\lfloor \cdot \rfloor$ is the floor function: the greatest integer no larger than the argument. The remainder is always non-negative and strictly less than $n$ — this constraint is what makes $q$ and $r$ unique for a given $a$ and $n$.

The greatest common divisor of $a$ and $b$, $\gcd(a, b)$, is the largest integer that divides both. Equivalently, $\gcd(a, b) = \max\{k : k \mid a \text{ and } k \mid b\}$. Because the definition requires a positive result, $\gcd(a, b) = \gcd(|a|, |b|)$ — sign does not matter. $\gcd(a, 0) = |a|$ since every integer divides $0$, and $\gcd(0, 0)$ is defined to be $0$. Two integers are relatively prime if their only common positive divisor is $1$, equivalently $\gcd(a, b) = 1$.

The Euclidean algorithm finds $\gcd(a, b)$ by repeated application of the division algorithm: replace $(a, b)$ with $(b, a \bmod b)$ and repeat until the remainder is $0$. The last non-zero remainder is the gcd. Each step is smaller than the last, so the algorithm always terminates.