Divisibility and the greatest common divisor

Divisibility means no remainder, and it survives any combination

Every later idea in this module rests on one question: does one number split evenly into another? RSA key generation depends on it directly. An encryption exponent $e$ only has a working decryption partner $d$ because $\gcd(e, \varphi(n)) = 1$. Modular inverses and the extended Euclidean algorithm on the next page start from the same machinery.

A non-zero integer $b$ divides $a$ if $a = mb$ for some integer $m$, so dividing $a$ by $b$ leaves no remainder. This is written $b \mid a$, and $b$ is 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: $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$ whatever $m$ and $n$ are.

Recall

Why does 11 | 66 and 11 | 77 guarantee 11 divides m·66 + n·77 for every integer m and n?

Because $66 = 11k$ and $77 = 11l$ for some integers $k, l$. Substituting, $m \cdot 66 + n \cdot 77 = 11(mk + nl)$, which is $11$ times an integer, so $11$ divides it whatever $m$ and $n$ are.

The division algorithm gives a unique quotient and a non-negative remainder

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$. That constraint is what makes $q$ and $r$ unique for a given $a$ and $n$.

Formula

Division algorithm

$$a = qn + r, \quad 0 \le r < n, \quad q = \left\lfloor \frac{a}{n} \right\rfloor$$

$a$

the dividend

$n$

the divisor (positive)

$q$

the quotient

$r$

the remainder, 0 <= r < n

Pitfall

$q = \lfloor a/n \rfloor$, not $a/n$ rounded or truncated toward zero. For non-negative $a$ and positive $n$ these agree, but do not carry the habit of “round toward zero” into modular arithmetic on the next page, where negative dividends make the two rules disagree.

The Euclidean algorithm finds the gcd by repeated division

The greatest common divisor of $a$ and $b$, $\gcd(a, b)$, is the largest integer that divides both: $\gcd(a, b) = \max\{k : k \mid a \text{ and } k \mid b\}$. The definition requires a positive result, so $\gcd(a, b) = \gcd(|a|, |b|)$. Every integer divides $0$, so $\gcd(a, 0) = |a|$, 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$.

Exam detail

Neither number has to be prime itself. $8$ and $15$ are relatively prime: the divisors of $8$ are $1, 2, 4, 8$, the divisors of $15$ are $1, 3, 5, 15$, and $1$ is the only entry on both lists.

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 remainder is smaller than the last, so the algorithm always terminates.

Try it — worked example

Use the Euclidean algorithm to find gcd(710, 310).

Show answer and steps

Answergcd(710, 310) = 10

The lecture names this exact example, but the figure showing its working did not survive extraction from the source PDF. The steps below apply the division algorithm repeatedly, exactly as defined above.

1. $710 = 2 \times 310 + 90$: divide 710 by 310, quotient 2, remainder 90.
2. $310 = 3 \times 90 + 40$: repeat on (310, 90).
3. $90 = 2 \times 40 + 10$: repeat on (90, 40).
4. $40 = 4 \times 10 + 0$: the remainder is 0, so the algorithm stops.
5. The last non-zero remainder was $10$, so $\gcd(710, 310) = 10$.