Integers and divisibility

This section answers one question: why does every whole number break into primes in exactly one way? Existence is easy; uniqueness is not obvious (in some number systems it fails). The route is a chain where each result is the tool for the next:

1. Divisibility (Def. 1.1) and its basic rules (Prop. 1.2).
2. The division algorithm (Theorem 1.3): every $a$ is $qn + r$ with $0\le r < n$.
3. gcd (Def. 1.4), computed by Euclid's algorithm (Theorem 1.6), which is repeated division.
4. Bézout (Theorem 1.7): running Euclid backwards writes $\gcd(a, b) = ax + by$. This is the key step.
5. Coprime cancellation (Prop. 1.11): if $a\mid bc$ and $\gcd(a, b) = 1$ then $a\mid c$.
6. Euclid's lemma (Theorem 1.14): a prime dividing $ab$ divides $a$ or $b$.
7. Unique factorisation (Theorem 1.15). Then applications: lcm, equations $ax + by = c$, and irrationality of $\sqrt n$.

For integers $a, b$, we say $a$ divides $b$, written $a\mid b$, if $b = ak$ for some integer $k$. Then $a$ is a divisor (or factor) of $b$ and $b$ is a multiple of $a$. If not, write $a\nmid b$. Note: $a\mid b$ is a statement (true or false), while $a/b$ is a number. Everything divides $0$ ($0 = a\cdot0$); $0$ divides only $0$; $\pm1$ divide everything. An integer is even if $2\mid n$ and odd otherwise.

For integers $a, b, c$: (i) if $a\mid b$ and $b\mid c$ then $a\mid c$; (ii) if $a\mid b$ and $a\mid c$ then $a\mid bx + cy$ for all $x, y\in\mathbb{Z}$; (iii) if $a\mid b$ and $b\ne0$ then $|a|\le|b|$; (iv) if $a\mid b$ and $b\mid a$ then $a = \pm b$.

For every integer $a$ and every integer $n\ge1$ there are unique integers $q$ (the quotient) and $r$ (the remainder) with

And $n\mid a$ exactly when $r = 0$. Examples: $47 = 6\cdot7 + 5$; $-17 = (-4)\cdot5 + 3$ (remainders are never negative).

For integers $a, b$ not both $0$, the greatest common divisor $\gcd(a, b)$ is the largest integer dividing both $a$ and $b$. (It exists since common divisors are bounded by $\max(|a|, |b|)$, and it is $\ge1$.) Basic facts: $\gcd(a, b) = \gcd(b, a) = \gcd(|a|, |b|)$; $\gcd(a, 0) = |a|$; $\gcd(a, 1) = 1$.

For all integers $a, b, q$: the common divisors of $a$ and $b$ are exactly the common divisors of $b$ and $a - qb$. Hence $\gcd(a, b) = \gcd(b, a - qb)$; in particular $\gcd(a, b) = \gcd(b, r)$ when $a = qb + r$.

Let $a\ge b > 0$. Define $r_0 = a$, $r_1 = b$, and while $r_k\ne0$ divide: $r_{k-1} = q_kr_k + r_{k+1}$ with $0\le r_{k+1} < r_k$. The process stops, and the last non-zero remainder is $\gcd(a, b)$. Example: $252 = 1\cdot198 + 54$, $198 = 3\cdot54 + 36$, $54 = 1\cdot36 + 18$, $36 = 2\cdot18$, so $\gcd(252, 198) = 18$.

Motivation. Running Euclid's algorithm backwards expresses the gcd using $a$ and $b$; for $252, 198$: $18 = 54 - 36 = 4\cdot54 - 198 = 4\cdot252 - 5\cdot198$. This always works: For integers $a, b$ not both $0$, there are integers $x, y$ with $ax + by = \gcd(a, b)$. In fact $\gcd(a, b)$ is the smallest positive integer of the form $ax + by$. The coefficients are found by running Euclid's algorithm backwards (the extended Euclidean algorithm; see Check 1.20).

If $c\mid a$ and $c\mid b$ then $c\mid\gcd(a, b)$. So $\gcd(a, b)$ is the unique non-negative common divisor that every common divisor divides; and $\gcd(ma, mb) = m\gcd(a, b)$ for $m\ge1$.

$a$ and $b$ are coprime (relatively prime) if $\gcd(a, b) = 1$. Examples: $8$ and $15$ are coprime (neither is prime, but they share no factor); $n$ and $n + 1$ are always coprime.

$a$ and $b$ are coprime if and only if there are integers $x, y$ with $ax + by = 1$.

Let $a, b, c\in\mathbb{Z}$ with $a\mid bc$ and $\gcd(a, b) = 1$. Then $a\mid c$. Consequence: if $a\mid n$, $b\mid n$ and $\gcd(a, b) = 1$, then $ab\mid n$.

An integer $p\ge2$ is prime if its only positive divisors are $1$ and $p$. An integer $n\ge2$ that is not prime is composite: $n = ab$ with $1 < a, b < n$. ($1$ is neither.) Equivalently, for $p\ge2$: $p$ is prime iff $\gcd(p, a)\in\{1, p\}$ for every $a$, i.e. either $p\mid a$ or $p$ and $a$ are coprime.

Every integer $n\ge2$ is a product of one or more primes. In particular every $n\ge2$ has a prime divisor, and there are infinitely many primes.

If $p$ is prime and $p\mid ab$, then $p\mid a$ or $p\mid b$. More generally, if $p\mid a_1a_2\cdots a_n$ then $p\mid a_i$ for some $i$. Fails for composite $n$: $6\mid2\cdot3$.

Every integer $n\ge2$ can be written as a product of primes $n = p_1p_2\cdots p_r$, and this factorisation is unique up to the order of the factors. Grouping equal primes, $n = p_1^{e_1}\cdots p_k^{e_k}$ with $p_1 < \cdots < p_k$ and $e_i\ge1$ uniquely.

For non-zero integers $a, b$, the least common multiple $\operatorname{lcm}(a, b)$ is the smallest positive integer divisible by both $a$ and $b$. (It exists: $|ab|$ is a positive common multiple.)

If $a = \prod p_i^{e_i}$ and $b = \prod p_i^{f_i}$ (allowing zero exponents), then

Every common multiple is a multiple of the lcm.

Let $a, b$ be non-zero with $d = \gcd(a, b)$. The equation $ax + by = c$ has an integer solution iff $d\mid c$. If $(x_0, y_0)$ is one solution, all solutions are

For $n\in\mathbb{N}$, $\sqrt n$ is rational if and only if $n$ is a perfect square. More generally, $\sqrt[k]n$ is rational iff $n$ is a perfect $k$th power.

Table method. Keep rows $(r, x, y)$ with $r = ax + by$, starting $(a, 1, 0)$ and $(b, 0, 1)$. Each new row is (row two above) $- q\cdot$(row above), where $q$ is the quotient of the two $r$'s. Stop when $r = 0$; the previous row gives $\gcd = ax + by$. Checks: verify $ax + by$ equals the gcd at the end; the gcd must divide both inputs; the remainders strictly decrease.