← MA0 1 · Introduction to University Mathematics (Proofs)

Lesson 10

Integers

Taught 22 Aug 2026

Formal Differences

At the end of the last chapter $(\mathbb{N}_0, +)$ was a monoid in which cancellation holds and in which nothing but $0$ has an inverse. It is regular and it is not a group, and this chapter closes the gap between those two facts. We do not add an axiom and we do not assume the integers exist. We build them, out of the natural numbers we already have, by writing down what a difference ought to be and then declaring two of them equal when they ought to be equal.

Pairs and the Sum Criterion

Every integer we want is a difference of two natural numbers. We want $3$ to be $5 - 2$ and $-3$ to be $5 - 8$ , and we want $3$ to be $6 - 3$ and $7 - 4$ as well: the pair recording the difference is not unique, and any construction must say when two pairs record the same thing.

The condition we want is $m - n = m' - n'$ , and as it stands that is not a statement about $\mathbb{N}_0$ , since subtraction is available only when the answer stays in $\mathbb{N}_0$ . But adding $n + n'$ to both sides of it turns it into

m + n' = n + m',

which mentions nothing but addition and is a perfectly good statement about four natural numbers. That equation is the relation we put on pairs, and the rest of the chapter is built on it.

Definition 10.1 (Net-difference equivalence).

On the set $\mathbb{N}_0 \times \mathbb{N}_0$ declare

(m, n) \sim (m', n') \qquad \text{if and only if} \qquad m + n' = n + m'.

The relation $\sim$ is called net-difference equivalence, and the displayed equation is the sum criterion.

Read the pair $(m, n)$ as a formal stand-in for the difference $m - n$ , one that makes sense whether or not that difference exists in $\mathbb{N}_0$ . Two pairs are related exactly when the differences they stand for ought to agree. The symbol $\sim$ is used for equivalence relations throughout mathematics and throughout this book; in this chapter it means only the relation just defined.

Proposition 10.2 (Net-difference equivalence is an equivalence relation).

The relation $\sim$ is an equivalence relation on $\mathbb{N}_0 \times \mathbb{N}_0$ .

Discussion.

Three properties to check, and each unfolds the sum criterion into a statement about addition in $\mathbb{N}_0$ . Reflexivity asks for $m + n = n + m$ , which is commutativity. Symmetry asks that $m + n' = n + m'$ give $m' + n = n' + m$ , which is the same equation read backwards with the two sides commuted. Transitivity is the only part that needs work: two sum criteria are given and a third must be produced, and the obstacle is that the middle pair $(m', n')$ appears in both hypotheses and in neither conclusion. The way to remove it is to add $n''$ to the first equation so that the second becomes substitutable, and then to strip the surviving $n'$ off both sides by cancellation, the property that made $(\mathbb{N}_0, +)$ regular.

Proof.

For reflexivity, $m + n = n + m$ by the laws of addition, so $(m, n) \sim (m, n)$ .

For symmetry, suppose $(m, n) \sim (m', n')$ , so $m + n' = n + m'$ . Commuting each side gives $m' + n = n' + m$ , which is the sum criterion for $(m', n') \sim (m, n)$ .

For transitivity, suppose $(m, n) \sim (m', n')$ and $(m', n') \sim (m'', n'')$ , so

m + n' = n + m' \qquad \text{and} \qquad m' + n'' = n' + m''.

Adding $n''$ to the first equation and rearranging by associativity and commutativity gives $m + n' + n'' = n + m' + n''$ . The second equation replaces $m' + n''$ on the right by $n' + m''$ , so

m + n' + n'' = n + n' + m''.

Cancelling $n'$ leaves $m + n'' = n + m''$ , which is $(m, n) \sim (m'', n'')$ .

The Net Difference

The sum criterion is easy to check but does not describe what a class looks like. A second description of the same relation gives each pair a standard representative: compare the two coordinates using trichotomy and subtract the smaller from the larger.

Definition 10.3 (Net difference).

The net-difference function

\Delta : \mathbb{N}_0 \times \mathbb{N}_0 \to \mathbb{N}_0 \times \mathbb{N}_0

is defined by

\Delta(m, n) \defeq \begin{cases} (m - n, \, 0) & \text{if } n < m, \\ (0, \, n - m) & \text{if } m < n, \\ (0, \, 0) & \text{if } m = n, \end{cases}

where $m - n$ is the difference of the order chapter: the unique element with $n + (m - n) = m$ , which exists because $n \leqslant m$ .

By trichotomy the three clauses cover every pair exactly once, so $\Delta$ is a function. Informally, $(x, 0)$ with $x \in \mathbb{N}$ is a positive difference, $(0, x)$ a negative one, and $(0,0)$ is zero; the next few propositions make that reading precise and tie $\Delta$ back to $\sim$ .

Proposition 10.4 (Coordinates of a net difference).

Let $m, n \in \mathbb{N}_0$ . Then at least one coordinate of $\Delta(m, n)$ is $0$ , and

if $\Delta(m, n) = (x, 0)$ with $x \in \mathbb{N}$ , then $n < m$ ;
if $\Delta(m, n) = (0, x)$ with $x \in \mathbb{N}$ , then $m < n$ ;
if $\Delta(m, n) = (0, 0)$ , then $m = n$ .

Discussion.

The opening claim is read straight off the definition, every clause of which puts a $0$ in one coordinate. The three numbered parts run the definition backwards, which is legitimate because the three cases are mutually exclusive: given the value of $\Delta(m, n)$ , we ask which clause could have produced it and find that only one can. For the first two the argument is that the other two clauses put $0$ in the coordinate that is here positive. The third is the leftover case and is best argued by contradiction: if $m \neq n$ then trichotomy puts one of them strictly below the other, and either way one coordinate of $\Delta(m, n)$ is a positive natural number, so the value is not $(0,0)$ .

Proof.

Trichotomy gives exactly one of $n < m$ , $m < n$ , $m = n$ , and each of the three clauses of the definition places $0$ in at least one coordinate.

Suppose $\Delta(m, n) = (x, 0)$ with $x \in \mathbb{N}$ . The second and third clauses put $0$ in the first coordinate, so neither produced this value, and the first clause applies; hence $n < m$ . The same argument with the coordinates exchanged gives the second part.

For the third, suppose $m \neq n$ . Trichotomy gives $n < m$ or $m < n$ . In the first case $\Delta(m, n) = (m - n, 0)$ and $m - n$ is positive, since $m - n = 0$ would give $m = n$ ; in the second case the second coordinate is positive for the same reason. Either way $\Delta(m, n) \neq (0, 0)$ .

Proposition 10.5 (Shifting both coordinates).

For all $m, n, x \in \mathbb{N}_0$ ,

\Delta(m, n) = \Delta(m + x, \, n + x).

Discussion.

An equality of values of $\Delta$ , so we split on the trichotomy comparison of $m$ with $n$ and check the three cases separately. Shifting does not change the comparison: adding a fixed element preserves the order, so if $n < m$ then $n + x < m + x$ and both sides of the claimed equality are produced by the same clause. Once that is known the two sides are $(m - n, 0)$ and $\bigl((m+x) - (n+x), 0\bigr)$ , and what remains is that shifting both arguments leaves the difference alone, which is uniqueness of differences applied to the defining equation. The case $m < n$ is the same with the coordinates exchanged, and $m = n$ is immediate.

Proof.

Suppose $n < m$ . Then $n + x < m + x$ , so

\Delta(m, n) = (m - n, \, 0), \qquad \Delta(m + x, n + x) = \bigl((m + x) - (n + x), \, 0\bigr).

Write $d \defeq m - n$ , so $n + d = m$ and hence $(n + x) + d = m + x$ by associativity and commutativity. Uniqueness of differences therefore gives $(m + x) - (n + x) = d$ , and the two values agree.

If $m < n$ the same argument applies with the coordinates exchanged. If $m = n$ then $m + x = n + x$ , and both sides are $(0, 0)$ .

Proposition 10.6 (Equal net differences satisfy the sum criterion).

If $\Delta(m, n) = \Delta(m', n')$ , then $m + n' = n + m'$ .

Discussion.

The hypothesis is an equality of pairs and the conclusion an equality of natural numbers, and we must convert one into the other, and the conversion depends on which of the three shapes the common value has. We therefore split on the comparison of $m$ with $n$ , and in each case the previous proposition on coordinates transfers the same comparison to $m'$ and $n'$ . Once both pairs are known to be of the same shape with the same entry $x$ , the defining property of the difference rewrites the hypothesis as $m = n + x$ and $m' = n' + x$ , two equations with no subtraction in them, and substituting both into $m + n'$ produces $n + m'$ after rearrangement.

Proof.

Suppose first that $n < m$ . Then $\Delta(m, n) = (x, 0)$ with $x \defeq m - n \in \mathbb{N}$ , so $\Delta(m', n') = (x, 0)$ as well; by the proposition on coordinates $n' < m'$ , and $m' - n' = x$ . Hence $m = n + x$ and $m' = n' + x$ , and

m + n' = (n + x) + n' = n + (x + n') = n + (n' + x) = n + m',

by associativity and commutativity.

The case $m < n$ is the same argument with the coordinates exchanged. If $m = n$ then $\Delta(m, n) = (0,0)$ , so $\Delta(m', n') = (0,0)$ and $m' = n'$ ; then $m + n' = n + m'$ reads $m + m' = m + m'$ .

Proposition 10.7 (The sum criterion yields a common shift).

Let $(m, n)$ and $(m', n')$ satisfy $m + n' = n + m'$ with $n \leqslant n'$ . Then there is $x \in \mathbb{N}_0$ with

n' = n + x \qquad \text{and} \qquad m' = m + x.

Discussion.

An existence claim, and the hypothesis $n \leqslant n'$ gives the witness directly: the description of the associated order says that $n \leqslant n'$ is exactly the existence of an $x$ with $n' = n + x$ . It remains to check that the same $x$ works in the other coordinate. Substituting $n + x$ for $n'$ in the sum criterion and rearranging leaves $n$ in front on both sides, and cancelling it gives $m' = m + x$ .

Proof.

Since $n \leqslant n'$ , there is $x \in \mathbb{N}_0$ with $n' = n + x$ . Then

n + m' = m + n' = m + (n + x) = n + (m + x),

the first equality being the sum criterion and the last associativity and commutativity. Cancelling $n$ gives $m' = m + x$ .

Three readings of “the same formal difference” are now available, and they agree.

Theorem 10.8 (Characterisations of net-difference equivalence).

Let $(m, n)$ and $(m', n')$ lie in $\mathbb{N}_0 \times \mathbb{N}_0$ . The following are equivalent.

$\Delta(m, n) = \Delta(m', n')$ .
$m + n' = n + m'$ .
Either $n' = n + x$ and $m' = m + x$ for some $x \in \mathbb{N}_0$ , or $n = n' + x$ and $m = m' + x$ for some $x \in \mathbb{N}_0$ .

Discussion.

Three conditions asserted to be equivalent, so rather than six implications we run a cycle through them, in the manner already used for equivalence classes. The first arrow, from the net difference to the sum criterion, is the proposition just proved. The second, from the sum criterion to the shift, is the other proposition together with a case split: the shift condition offers two alternatives because the previous proposition needed $n \leqslant n'$ , and trichotomy guarantees that one of $n \leqslant n'$ and $n' \leqslant n$ holds, each giving one alternative once the roles of the two pairs are exchanged. The third arrow, from the shift back to the net difference, is the proposition on shifting both coordinates, read in one direction for the first alternative and in the other for the second.

Proof.

That the first implies the second is the proposition on equal net differences.

Suppose the second holds. If $n \leqslant n'$ , the proposition on common shifts gives $x$ with $n' = n + x$ and $m' = m + x$ , which is the first alternative of the third condition. Otherwise $n' \leqslant n$ by trichotomy, and the same proposition applied to the pairs in the other order — the sum criterion $m' + n = n' + m$ being the given equation read backwards — gives $x$ with $n = n' + x$ and $m = m' + x$ , which is the second alternative.

Suppose the third holds. Under the first alternative, the proposition on shifting both coordinates gives

\Delta(m, n) = \Delta(m + x, \, n + x) = \Delta(m', n').

Under the second it gives $\Delta(m', n') = \Delta(m' + x, \, n' + x) = \Delta(m, n)$ . Either way the first condition holds, and the cycle is closed.

Remark (Which characterisation to use).

Each of the three is the convenient one somewhere below. The sum criterion is easiest to use in algebra, since it is an equation in $\mathbb{N}_0$ and nothing else, and every well-definedness check in this chapter uses it. The shift criterion says that two pairs agree when one is the other with the same amount added to both coordinates. The net difference gives each class a single named representative, and that is what lets us say what the integers are rather than only when two of them are equal.

Problem 10.1.

Compute $\Delta(19, 15)$ and $\Delta(14, 16)$ .

Problem 10.2.

Show that $m - 0 = m$ for every $m \in \mathbb{N}_0$ , from the defining property of the difference. Deduce that $\Delta(m, 0) = (m, 0)$ and $\Delta(0, n) = (0, n)$ for all $m, n \in \mathbb{N}_0$ , and hence that $\Delta \circ \Delta = \Delta$ .

Problem 10.3.

Prove the proposition that $\sim$ is an equivalence relation a second time, taking the first condition of the theorem as the definition of $\sim$ and checking the three properties directly from properties of $\Delta$ .

The Integers

Integers as Classes

Definition 10.9 (The integers).

The set of integers is the quotient

\mathbb{Z} \defeq \bigl(\mathbb{N}_0 \times \mathbb{N}_0\bigr)\big/{\sim}

of $\mathbb{N}_0 \times \mathbb{N}_0$ by net-difference equivalence. We write $[(m, n)]$ for the class of the pair $(m, n)$ .

No axiom has been added. The set is carved out of a product of two copies of $\mathbb{N}_0$ by a relation already checked to be an equivalence, and both of those operations have been available since the chapters on sets and on relations. What remains is to define the arithmetic.

By the theorem and the proposition on coordinates, every class has exactly one representative among the pairs

(x, 0) \text{ with } x \in \mathbb{N}_0, \qquad (0, x) \text{ with } x \in \mathbb{N},

these being the values $\Delta$ takes, and $(0,0)$ appearing once in the first list. We call it the normal form of the class. In particular $[(m,n)] = [(m - n, 0)]$ when $n \leqslant m$ , and $[(m, n)] = [(0, n - m)]$ when $m \leqslant n$ .

Proposition 10.10 (Embedding the natural numbers).

The map

\iota : \mathbb{N}_0 \to \mathbb{Z}, \qquad \iota(n) \defeq [(n, 0)]

is injective.

Discussion.

Injectivity is the statement that equal values force equal arguments, so we assume $\iota(n) = \iota(n')$ and must reach $n = n'$ . Equal classes mean related representatives, by the characterisation of equivalence classes, and the sum criterion for those two particular pairs is $n + 0 = 0 + n'$ , which is the conclusion up to two zeros.

Proof.

Suppose $[(n, 0)] = [(n', 0)]$ . Then $(n, 0) \sim (n', 0)$ , so $n + 0 = 0 + n'$ by the sum criterion, and $n = n'$ by the identity law for addition.

So $\iota$ embeds $\mathbb{N}_0$ in $\mathbb{Z}$ , and the normal form says every class is either $\iota(x)$ for a unique $x \in \mathbb{N}_0$ , or $[(0, x)]$ for a unique $x \in \mathbb{N}$ . Once addition is in place the second family will turn out to be the additive inverses of the first.

Problem 10.4.

List five distinct pairs in the class $[(3, 5)]$ , and give the normal form of that class.

Problem 10.5.

Show that $[(m, n)] = [(0, 0)]$ if and only if $m = n$ .

Addition and Negation

The arithmetic must be defined on classes, but the only formulae available are written with pairs. We follow the same pattern three times: define the operation on pairs, prove that equivalent inputs give equivalent outputs, and only then pass to classes. The middle step ensures that the result does not depend on which representatives were picked.

Pretend for a moment that differences already exist. Then $-(m - n) = n - m$ and

(m - n) + (m' - n') = (m + m') - (n + n'),

and those two identities suggest the definitions on pairs. Nothing below uses this; it only motivates the definitions.

Definition 10.11 (Pre-negation).

The pre-negation of a pair $(m, n) \in \mathbb{N}_0 \times \mathbb{N}_0$ is the pair $(n, m)$ .

Proposition 10.12 (Pre-negation respects equivalence).

If $(m, n) \sim (m', n')$ , then $(n, m) \sim (n', m')$ .

Discussion.

Hypothesis and conclusion are both sum criteria, so both unfold into equations in $\mathbb{N}_0$ . The hypothesis is $m + n' = n + m'$ . The conclusion, written out for the pairs $(n, m)$ and $(n', m')$ , is $n + m' = m + n'$ . Those are the same equation with the two sides exchanged, so symmetry of equality is the whole proof.

Proof.

The hypothesis is $m + n' = n + m'$ . Reading it backwards gives $n + m' = m + n'$ , which is the sum criterion for $(n, m) \sim (n', m')$ .

Definition 10.13 (Negation).

Define negation on $\mathbb{Z}$ by

-[(m, n)] \defeq [(n, m)].

By the proposition just proved, the right-hand side depends only on the class of $(m, n)$ and not on the representative chosen for it.

Definition 10.14 (Pre-addition).

Define pre-addition on pairs by

(m, n) + (m', n') \defeq (m + m', \; n + n').

Proposition 10.15 (Pre-addition respects equivalence).

If $(m, n) \sim (a, b)$ and $(m', n') \sim (a', b')$ , then

(m + m', \; n + n') \sim (a + a', \; b + b').

Discussion.

Two sum criteria are given and one is wanted, and since all three are equations between sums in $\mathbb{N}_0$ we add the two hypotheses together. What comes out is an equation whose two sides are the four summands in some order, and the general associativity and rearrangement available in any abelian semigroup lets us collect them into the grouping the conclusion asks for. No case split and no cancellation are needed.

Proof.

The hypotheses are $m + b = n + a$ and $m' + b' = n' + a'$ . Adding the two equations and rearranging the summands on each side gives

(m + m') + (b + b') = (n + n') + (a + a'),

which is exactly the sum criterion for $(m + m', n + n') \sim (a + a', b + b')$ .

Definition 10.16 (Addition and subtraction).

Define addition on $\mathbb{Z}$ by

[(m, n)] + [(m', n')] \defeq [(m + m', \; n + n')],

which the previous proposition makes independent of the representatives; and for $x, y \in \mathbb{Z}$ define $x - y \defeq x + (-y)$ .

Theorem 10.17 (The integers form an abelian group).

With the addition just defined, $(\mathbb{Z}, +)$ is an abelian group. Its identity is $[(0, 0)]$ and the inverse of $[(m, n)]$ is $[(n, m)]$ . Moreover

\iota(m + n) = \iota(m) + \iota(n) \qquad \text{for all } m, n \in \mathbb{N}_0,

and $\iota(0) = [(0, 0)]$ .

Discussion.

The definition of a group asks for four things and the last claim adds a fifth, but every one of them is a law in $\mathbb{N}_0$ applied in each coordinate, so the proof is a sequence of short computations. Associativity and commutativity of the new addition are associativity and commutativity of the old one, used once in each coordinate. The class $[(0,0)]$ is an identity because $0$ is one in $\mathbb{N}_0$ . The only step that needs thought is the inverse: adding $[(m,n)]$ to $[(n,m)]$ gives the class of $(m + n, \, n + m)$ , and this is $[(0,0)]$ not because the two coordinates are zero (they are not) but by the sum criterion, which asks only that $(m+n) + 0 = (n+m) + 0$ . That is commutativity. The claim about $\iota$ is the definition of addition read on pairs whose second coordinate is $0$ .

Proof.

Let $x = [(m, n)]$ , $y = [(m', n')]$ and $z = [(m'', n'')]$ . Then

(x + y) + z = \bigl[\bigl((m + m') + m'', \; (n + n') + n''\bigr)\bigr] = x + (y + z)

by associativity of addition in $\mathbb{N}_0$ in each coordinate, so the operation is associative; and $x + y = y + x$ by commutativity in each coordinate. So $(\mathbb{Z}, +)$ is an abelian semigroup.

Next,

x + [(0, 0)] = [(m + 0, \; n + 0)] = [(m, n)] = x,

so $[(0,0)]$ is an identity, and it is the only one by uniqueness of the identity. Finally

x + [(n, m)] = [(m + n, \; n + m)] = [(0, 0)],

the last equality by the sum criterion, which asks for $(m + n) + 0 = (n + m) + 0$ and gets it from commutativity. So every element is invertible and $(\mathbb{Z}, +)$ is an abelian group.

For the last claim, $\iota(m) + \iota(n) = [(m, 0)] + [(n, 0)] = [(m + n, \, 0)] = \iota(m + n)$ , and $\iota(0) = [(0,0)]$ by definition.

In particular $-\iota(n) = -[(n, 0)] = [(0, n)]$ , so the classes with normal form $(0, n)$ are precisely the additive inverses of the embedded positive naturals. Every integer is therefore $\iota(x)$ for a unique $x \in \mathbb{N}_0$ or $-\iota(x)$ for a unique $x \in \mathbb{N}$ , which is the normal form restated using addition. Writing $n$ for $\iota(n)$ and $-n$ for $-\iota(n)$ , the familiar list $\ldots, -2, -1, 0, 1, 2, \ldots$ names every integer exactly once.

Remark (What was gained).

The chapter on groups observed that $(\mathbb{N}_0, +)$ is regular but not a group, and said that regularity is the condition needed to enlarge a monoid into a group. This theorem does that for $(\mathbb{N}_0, +)$ . The regularity was used once, in the proof that $\sim$ is transitive, and without it the relation would not be an equivalence and there would be no quotient.

Problem 10.6.

Compute $[(5, 2)] + [(1, 4)]$ and $-[(5, 2)]$ , and give each answer in normal form.

Problem 10.7.

Prove directly from the definitions that $-(x + y) = (-x) + (-y)$ and $-(-x) = x$ for all $x, y \in \mathbb{Z}$ . Which of the two also follows from a proposition of the chapter on groups, and why does the other not?

Problem 10.8.

Show that $\iota(m) - \iota(n) = [(m, n)]$ for all $m, n \in \mathbb{N}_0$ , so that every class really is a difference of two embedded natural numbers.

Multiplication

Pretend again that differences exist. Then

(m - n)(m' - n') = (mm' + nn') - (mn' + nm'),

and the rule on pairs is forced.

Definition 10.18 (Pre-multiplication).

Define pre-multiplication on pairs by

(m, n) \cdot (m', n') \defeq (mm' + nn', \; mn' + nm').

Proposition 10.19 (Pre-multiplication respects equivalence).

Let $(m, n) \sim (a, b)$ . Then for every pair $(m', n')$ ,

(m, n) \cdot (m', n') \sim (a, b) \cdot (m', n').

Likewise, if $(m', n') \sim (a', b')$ then $(m, n) \cdot (m', n') \sim (m, n) \cdot (a', b')$ for every $(m, n)$ .

Discussion.

Two statements, one for each factor, and together they are what a definition on classes needs: changing the representatives one at a time changes them both. Each is again an implication between sum criteria, but unlike the additive case the hypothesis cannot simply be added to something, because the conclusion involves products. So we write down the sum criterion the conclusion asks for, expand both of its sides using distributivity in $\mathbb{N}_0$ , and regroup the terms until the hypothesis becomes visible. The left side collects into $(m + b)m' + (n + a)n'$ and the right into $(m + b)n' + (n + a)m'$ ; the hypothesis says the two bracketed factors are equal, so the two sides are the same sum written twice. The second statement is the first with the roles of the factors exchanged, which is legitimate because pre-multiplication is symmetric in its two arguments.

Proof.

Assume $m + b = n + a$ . The two pre-products are

(mm' + nn', \; mn' + nm') \qquad \text{and} \qquad (am' + bn', \; an' + bm'),

and the sum criterion for their equivalence asks that

(mm' + nn') + (an' + bm') = (mn' + nm') + (am' + bn').

Regrouping the left side by distributivity, associativity and commutativity gives $(m + b)m' + (n + a)n'$ , and the right side gives $(m + b)n' + (n + a)m'$ . Writing $k$ for the common value of $m + b$ and $n + a$ , both sides are $km' + kn'$ , so they agree.

For the second statement, pre-multiplication is unchanged when its two arguments are exchanged, since $mm' + nn'$ and $mn' + nm'$ are symmetric under exchanging $(m,n)$ with $(m',n')$ ; so the first statement applied to the exchanged pairs gives it.

Definition 10.20 (Multiplication).

Define multiplication on $\mathbb{Z}$ by

[(m, n)] \cdot [(m', n')] \defeq [(mm' + nn', \; mn' + nm')],

which the previous proposition makes independent of both choices of representative.

Theorem 10.21 (Distributivity in the integers).

For all $x, y, z \in \mathbb{Z}$ ,

x(y + z) = xy + xz.

Discussion.

An identity between two integers, so we name representatives for the three of them and compute both sides down to a single class each. The left side expands by the definition of addition and then of multiplication, the right side by multiplication twice and then addition, and each expansion is an application of distributivity in $\mathbb{N}_0$ inside a coordinate. The two resulting pairs then have the same four terms in each coordinate, in a different order, so commutativity of addition finishes. We write the computation with the pairs visible, since the identity holds coordinatewise.

Proof.

Let $x = [(a, b)]$ , $y = [(c, d)]$ and $z = [(e, f)]$ . Then $y + z = [(c + e, \; d + f)]$ , so

\begin{aligned} x(y + z) &= \bigl[\bigl(a(c + e) + b(d + f), \; a(d + f) + b(c + e)\bigr)\bigr] \\ &= \bigl[\bigl(ac + ae + bd + bf, \; ad + af + bc + be\bigr)\bigr], \end{aligned}

while

\begin{aligned} xy + xz &= [(ac + bd, \; ad + bc)] + [(ae + bf, \; af + be)] \\ &= \bigl[\bigl(ac + bd + ae + bf, \; ad + bc + af + be\bigr)\bigr]. \end{aligned}

The two pairs have the same terms in each coordinate, so they are equal by commutativity of addition in $\mathbb{N}_0$ , and the two classes agree.

Proposition 10.22 (The embedding preserves multiplication).

For all $m, n \in \mathbb{N}_0$ we have $\iota(mn) = \iota(m) \cdot \iota(n)$ . Moreover $[(1, 0)]$ is an identity for multiplication on all of $\mathbb{Z}$ .

Discussion.

Two computations, each one line. For the first, expand $\iota(m) \cdot \iota(n)$ by the definition: both second coordinates are $0$ , so three of the four products in the formula vanish and what is left is $(mn, 0)$ , which is $\iota(mn)$ . The second claim is not the case $m = 1$ of the first, since that only says $\iota(1)$ acts as an identity on the image of $\iota$ , and the image is not all of $\mathbb{Z}$ ; so it needs its own computation, which is the same expansion carried out against a general class. Only one side need be checked, because pre-multiplication is symmetric in its arguments.

Proof.

For the first claim,

\begin{aligned} \iota(m) \cdot \iota(n) &= [(m, 0)] \cdot [(n, 0)] \\ &= [(mn + 0 \cdot 0, \; m \cdot 0 + 0 \cdot n)] = [(mn, 0)] = \iota(mn). \end{aligned}

For the second, let $[(a, b)]$ be any class. Then

[(1, 0)] \cdot [(a, b)] = [(1 \cdot a + 0 \cdot b, \; 1 \cdot b + 0 \cdot a)] = [(a, b)],

and the other side is the same computation, pre-multiplication being symmetric in its two arguments.

Remark (What is left to check).

The remaining algebra (associativity and commutativity of multiplication, the sign rules $(-x)y = x(-y) = -(xy)$ and $(-x)(-y) = xy$ , and the absence of zero divisors) follows the pattern of this section without exception: name representatives, expand, and quote the corresponding law in $\mathbb{N}_0$ . None of it needs a new idea, so it is set as problems. What is still missing is the order on $\mathbb{Z}$ .

Problem 10.9.

Prove that multiplication on $\mathbb{Z}$ is commutative and associative.

Problem 10.10.

Prove that $(-x)y = x(-y) = -(xy)$ and $(-x)(-y) = xy$ for all $x, y \in \mathbb{Z}$ .

Problem 10.11.

Prove that if $x, y \in \mathbb{Z}$ and $xy = [(0, 0)]$ , then $x = [(0,0)]$ or $y = [(0,0)]$ . Reduce to normal form first, and then use that a product of positive natural numbers is positive.

Problem 10.12.

Using the problem that $\iota(m) - \iota(n) = [(m, n)]$ , show that $[(m, n)] = [(m', n')]$ if and only if $\iota(m) - \iota(n) = \iota(m') - \iota(n')$ in $\mathbb{Z}$ .

The Order on the Integers

So far nothing distinguishes $[(5,2)]$ from $[(2,5)]$ except the labels; the arithmetic treats them alike. The order does distinguish them, and we define it from the normal form, which sorts every class into one of three shapes.

Definition 10.23 (Positive integers).

An integer $x$ is positive if $x = \iota(n)$ for some $n \in \mathbb{N}$ .

Proposition 10.24 (Every integer has exactly one sign).

Let $x \in \mathbb{Z}$ . Then exactly one of the following holds: $x$ is positive; $x = \iota(0)$ ; $x = -y$ for a positive $y$ .

Discussion.

The claim is that three cases cover $\mathbb{Z}$ and no two of them overlap, so there are two halves to it. Coverage is the normal form: every class is $[(a, 0)]$ with $a \in \mathbb{N}_0$ or $[(0, a)]$ with $a \in \mathbb{N}$ , and the first of those is $\iota(a)$ , positive when $a \in \mathbb{N}$ and $\iota(0)$ when $a = 0$ , while the second is $-\iota(a)$ by the remark following the group theorem. Exclusivity is the uniqueness half of the normal form, together with the injectivity of $\iota$ : two of the cases could only collide if two distinct normal forms named the same class, or if $\iota$ identified $0$ with something in $\mathbb{N}$ .

Proof.

Every class has exactly one normal form. If it is $(a, 0)$ with $a \in \mathbb{N}$ , then $x = \iota(a)$ is positive. If it is $(0, 0)$ , then $x = \iota(0)$ . If it is $(0, a)$ with $a \in \mathbb{N}$ , then $x = -\iota(a)$ with $\iota(a)$ positive. So the three cases cover $\mathbb{Z}$ .

For exclusivity, suppose $x$ is positive and also $x = \iota(0)$ . Then $\iota(n) = \iota(0)$ for some $n \in \mathbb{N}$ , so $n = 0$ by injectivity of $\iota$ , contradicting $0 \notin \mathbb{N}$ . Suppose $x$ is positive and also $x = -\iota(n')$ with $n' \in \mathbb{N}$ . Then $x$ has normal forms $(n, 0)$ and $(0, n')$ with $n, n' \in \mathbb{N}$ , and those are different pairs, contradicting uniqueness. The same argument rules out $\iota(0) = -\iota(n')$ .

Proposition 10.25 (Positive integers are closed under the operations).

If $x$ and $y$ are positive, then so are $x + y$ and $xy$ .

Discussion.

Both claims say that a value built from two positive integers is again of the form $\iota(n)$ with $n \in \mathbb{N}$ , and the two facts that produce such a form are already proved: $\iota$ carries sums to sums and carries products to products. So each claim reduces immediately to the corresponding closure in $\mathbb{N}$ , which is the proposition that the positive natural numbers are closed under addition and multiplication. Nothing about $\mathbb{Z}$ is used beyond the two formulas for $\iota$ .

Proof.

Write $x = \iota(m)$ and $y = \iota(n)$ with $m, n \in \mathbb{N}$ . Then $x + y = \iota(m + n)$ and $xy = \iota(mn)$ , and both $m + n$ and $mn$ lie in $\mathbb{N}$ . So both values are positive.

Definition 10.26 (The order on the integers).

For $x, y \in \mathbb{Z}$ write

x < y \qquad \text{if and only if} \qquad y - x \text{ is positive},

and write $x \leqslant y$ for ” $x < y$ or $x = y$ ”, as in the associated order of the chapter on relations.

Theorem 10.27 (The integers are strictly ordered).

The relation $<$ is a strict linear order on $\mathbb{Z}$ .

Discussion.

Two conditions are asked for. Transitivity is a computation: from $y - x$ and $z - y$ positive we must produce $z - x$ positive, and the way to reach $z - x$ from those two is to add them, since the middle terms cancel in the group $(\mathbb{Z}, +)$ ; the previous proposition then keeps the sum positive. Trichotomy is the proposition on signs, applied not to $x$ or $y$ but to the single integer $y - x$ : its three cases say that $y - x$ is positive, or zero, or the negative of a positive, and those are exactly $x < y$ , $x = y$ and $y < x$ since $-(y - x) = x - y$ . That last identity is the rule for the inverse of a product read additively, together with $-(-x) = x$ .

Proof.

For transitivity, suppose $x < y$ and $y < z$ , so $y - x$ and $z - y$ are positive. Their sum is positive by the previous proposition, and

(z - y) + (y - x) = z + \bigl((-y) + y\bigr) + (-x) = z - x

by associativity and the inverse law in $(\mathbb{Z}, +)$ . So $x < z$ .

For trichotomy, let $x, y \in \mathbb{Z}$ and apply the proposition on signs to $y - x$ . If $y - x$ is positive then $x < y$ . If $y - x = \iota(0)$ then, adding $x$ to both sides, $y = x$ . If $y - x = -w$ with $w$ positive, then $x - y = -(y - x) = w$ is positive, so $y < x$ . Exactly one of the three cases holds, and they are the three alternatives trichotomy demands.

Proposition 10.28 (The order and the operations).

Let $x, y, z \in \mathbb{Z}$ .

If $x < y$ then $x + z < y + z$ .
If $x < y$ and $z$ is positive, then $xz < yz$ .
$\iota(m) < \iota(n)$ if and only if $m < n$ , for all $m, n \in \mathbb{N}_0$ .

Discussion.

Each part unfolds the definition of $<$ into a statement about a difference being positive, so each is settled by computing that difference. In the first the difference is $(y + z) - (x + z)$ , and the two copies of $z$ cancel in the group, leaving $y - x$ unchanged: so the hypothesis is the conclusion. In the second the difference is $yz - xz$ , which factors as $(y - x)z$ by distributivity together with the sign rule $(-x)z = -(xz)$ , and the previous proposition then multiplies two positives. Both of those facts about multiplication were set as problems above, and we quote them. The third is the definition of $<$ on each side: $\iota(n) - \iota(m)$ is $\iota(n - m)$ when $m \leqslant n$ , so positivity of the difference in $\mathbb{Z}$ says exactly what $m < n$ says in $\mathbb{N}_0$ .

Proof.

For the first, $(y + z) - (x + z) = y - x$ by associativity, commutativity and the inverse law, so one difference is positive exactly when the other is.

For the second, the problems on multiplication give $(-x)z = -(xz)$ , and distributivity gives

(y - x)z = yz + (-x)z = yz - xz.

If $x < y$ then $y - x$ is positive, and $z$ is positive, so the product is positive by the previous proposition; hence $xz < yz$ .

For the third, suppose $m < n$ in $\mathbb{N}_0$ . Then $n = m + b$ with $b \in \mathbb{N}$ , so $\iota(n) - \iota(m) = \iota(m + b) - \iota(m) = \iota(b)$ , which is positive; hence $\iota(m) < \iota(n)$ . Conversely, if $\iota(m) < \iota(n)$ then $\iota(n) - \iota(m) = \iota(b)$ for some $b \in \mathbb{N}$ , so $\iota(n) = \iota(m + b)$ and $n = m + b$ by injectivity, giving $m < n$ .

Corollary 10.29 (One is the least positive integer).

If $x \in \mathbb{Z}$ is positive, then $\iota(1) \leqslant x$ .

Proof.

Write $x = \iota(n)$ with $n \in \mathbb{N}$ . Then $1 \leqslant n$ , since $n$ is positive and $\mathbb{N}$ has least element $1$ among its own members, so $\iota(1) \leqslant \iota(n)$ by the third part of the proposition.

Remark (Dropping the embedding from the notation).

From here on we write $n$ for $\iota(n)$ and $-n$ for $-\iota(n)$ , and treat $\mathbb{N}_0$ as a subset of $\mathbb{Z}$ . This is harmless, by the proposition on the order: $\iota$ carries sums to sums, products to products, and the order to the order, and it is injective, so every statement about $\mathbb{N}_0$ transfers unchanged to its image and back. The positive integers are then exactly $\mathbb{N}$ , the list

\ldots, \; -2, \; -1, \; 0, \; 1, \; 2, \; \ldots

names every integer exactly once, and $0 < 1$ by the corollary.

Problem 10.13.

Show that $x < y$ if and only if $-y < -x$ , and that $x$ is positive if and only if $-x < 0$ .

Problem 10.14.

Show that if $x < y$ and $z < 0$ then $yz < xz$ , and that $x^2 \geqslant 0$ for every $x \in \mathbb{Z}$ , with equality only at $x = 0$ .

Problem 10.15.

Show that no integer lies strictly between $n$ and $n + 1$ , and deduce that $\mathbb{Z}$ has no maximum and no minimum.

Sequences, Sums and Products

Many of our notions are already functions. Addition is a map $\mathbb{Z} \times \mathbb{Z} \to \mathbb{Z}$ , iteration is repeated composition, and counting a finite set is a bijection $\langle n \rangle \to S$ . A sequence is the same idea read in the other direction: a list of values is a function whose domain is a set of indices. That notion is not new: finite and infinite sequences were defined in the chapter on relations, and the summation symbol in the chapter on the natural numbers. What is new is that the indices may now run over an interval of integers rather than an opening stretch of $\mathbb{N}_0$ , which makes it easier to write a sum starting at $0$ or at $-3$ , or to shift one along.

Indexing by an Integer Interval

Definition 10.30 (Integer intervals).

For $m, n \in \mathbb{Z}$ with $m \leqslant n$ , write

\{m, \ldots, n\} \defeq \{x \in \mathbb{Z} \mid m \leqslant x \leqslant n\},

and for $n \in \mathbb{Z}$ write

\{n, n+1, \ldots\} \defeq \{x \in \mathbb{Z} \mid n \leqslant x\}.

The first is finite and the second is not, as the next paragraph records. When $m = 1$ and $n \in \mathbb{N}$ the interval $\{1, \ldots, n\}$ is exactly the block $\langle n \rangle$ .

Proposition 10.31 (Intervals are finite and are counted by their length).

Let $m \leqslant n$ in $\mathbb{Z}$ . Then $j \mapsto m + j$ is a bijection from the cut $L_{n - m + 1}$ onto $\{m, \ldots, n\}$ , so $\{m, \ldots, n\}$ is finite with $\#\{m, \ldots, n\} = n - m + 1$ . The ray $\{n, n+1, \ldots\}$ is infinite.

Discussion.

The first claim is an existence statement about a bijection, and the map comes from the shape of the interval: an element of $\{m, \ldots, n\}$ is $m$ plus something, and the something is bounded by the length. So we only check the two halves of bijectivity, and both come from the order: injectivity is cancellation for addition in $\mathbb{Z}$ , and surjectivity is the observation that $m \leqslant x \leqslant n$ makes $x - m$ a natural number below $n - m + 1$ . The cardinality is then read off, a cut $L_k$ having $k$ elements. The last claim is a contradiction: a finite subset of a totally ordered set has a maximum, and the ray has none, since $x + 1$ is always a larger member.

Proof.

Write $k \defeq n - m + 1$ , a positive integer since $m \leqslant n$ . If $j \in L_k$ then $0 \leqslant j \leqslant n - m$ , so $m \leqslant m + j \leqslant n$ and the map lands in the interval. It is injective because $m + j = m + j'$ gives $j = j'$ by cancellation, and surjective because $m \leqslant x \leqslant n$ makes $x - m$ a natural number with $x - m \leqslant n - m$ , so $x - m \in L_k$ and $x = m + (x - m)$ .

Hence $\{m, \ldots, n\} \approx L_k$ and $\#\{m, \ldots, n\} = k$ .

Were the ray finite it would be a non-empty finite subset of the totally ordered set $\mathbb{Z}$ , hence would have a maximum $M$ ; but $M + 1$ lies in the ray and $M < M + 1$ , which no upper bound permits.

Definition 10.32 (Sequences on an interval).

Let $S$ be a set. A finite sequence in $S$ indexed by $\{m, \ldots, n\}$ is a function $c : \{m, \ldots, n\} \to S$ , and an infinite sequence indexed by $\{n, n+1, \ldots\}$ is a function on that ray. One writes $c_i$ for $c(i)$ , calls $c_i$ the $i$ -th term and $i$ the index, and calls the domain the index set.

Composing with the bijection of the proposition turns such a sequence into one indexed by a cut, and back again, so this is the notion of the chapter on relations with the indices relabelled and not a second notion. The gain is convenience: one may now write a rule on a generic index, as in ” $c_i = 2i + 1$ for $i \in \{0, \ldots, 5\}$ ”, and start wherever the problem starts. The index is a bound variable and may be renamed, so the same sequence is equally $c_j = 2j + 1$ for $j \in \{0, \ldots, 5\}$ .

Remark (Shifts are different functions).

A finite sequence is commonly written $(c_i)_{i = m, \ldots, n}$ , or $(c_i)$ when the index set is understood, and sequences may be built from sequences: $(3a_i + 4)_{i = m, \ldots, n}$ is a sequence once $(a_i)$ is one. But

(b_{i+k})_{i = m-k, \ldots, n-k} \qquad \text{and} \qquad (b_i)_{i = m, \ldots, n}

are not equal, even though they list the same values in the same order. Their domains differ, and functions with different domains are different functions. One is a shift of the other, and the theorem on index shifts below is what relates their sums.

Problem 10.16.

Take the values $5, 10, 17, 26, 37$ . Give a finite sequence with exactly those terms, and name its index set. Write a shifted sequence with the same values in the same order, and extend the original to an infinite sequence.

Problem 10.17.

Let $(b_i)_{i = m, \ldots, n}$ be a finite sequence and let $k \in \mathbb{Z}$ . Show that $(b_{i+k})_{i = m-k, \ldots, n-k}$ and $(b_i)_{i = m, \ldots, n}$ have the same image, but are equal as functions if and only if $k = 0$ .

Sums over an Interval

Definition 10.33 (Summation over an interval).

Let $(b_i)$ be a sequence with values in a set $U$ carrying an operation written $+$ , and let $m$ lie in its index set. For every $n \geqslant m$ in that index set define

\sum_{i=m}^{m} b_i \defeq b_m, \qquad \sum_{i=m}^{k+1} b_i \defeq \left(\sum_{i=m}^{k} b_i\right) + b_{k+1} \quad (k \geqslant m).

That the clauses determine one value at each $n$ is the recursion theorem, applied after the running length $n - m$ has been shifted into $\mathbb{N}_0$ ; it is the same argument that produced the summation symbol in the chapter on the natural numbers, and taking $m = 1$ with values in a Peano system recovers that symbol exactly. What the present definition adds is an arbitrary lower limit and an arbitrary value set: $U$ needs an operation and nothing else. If every term lies in a subset of $U$ closed under $+$ , the sum lies there too, since the recursion never leaves that subset.

Proposition 10.34 (An interval sum is a left-associated sum).

Let $(U, +)$ be a set with an operation and let $m \leqslant n$ . Then

\sum_{i=m}^{n} b_i = p(b_m, b_{m+1}, \ldots, b_n),

where $p$ is the left-associated product of the chapter on groups, written additively.

Discussion.

Both sides are defined by a recursion, and the claim is that the two recursions are the same one in different notation. So the proof is an induction on the number of terms in which each step compares the two recursive clauses: the base cases are the single-term clauses, which both give $b_m$ , and the step appends $b_{k+1}$ on the right in both definitions. Nothing about $+$ is used. We record it because it lets us quote the results of the chapter on groups here instead of proving them again.

Proof.

Induct on $t \in \mathbb{N}_0$ with $n = m + t$ . At $t = 0$ both sides are $b_m$ . If the two agree at $t$ , then

\sum_{i=m}^{m+t+1} b_i = \left(\sum_{i=m}^{m+t} b_i\right) + b_{m+t+1} = p(b_m, \ldots, b_{m+t}) + b_{m+t+1} = p(b_m, \ldots, b_{m+t+1}),

the outer equalities being the recursive clauses of the two definitions and the middle one the inductive hypothesis.

Theorem 10.35 (Splitting a sum).

Let $(U, +)$ be a semigroup and let $\ell \leqslant m - 1$ and $m \leqslant n$ in $\mathbb{Z}$ , with $(b_i)$ defined on $\{\ell, \ldots, n\}$ . Then

\sum_{i=\ell}^{n} b_i = \sum_{i=\ell}^{m-1} b_i \; + \sum_{i=m}^{n} b_i .

Discussion.

This is the splitting identity of general associativity, which says a left-associated product may be cut anywhere, and the previous proposition has just identified an interval sum with such a product. So we only need to match the two statements: the cut after the $(m-1)$ -st term of the interval corresponds to the cut after the $(m - \ell)$ -th factor of the list, and the two blocks are the two sub-intervals.

Proof.

Write the list $b_\ell, b_{\ell+1}, \ldots, b_n$ , of length $n - \ell + 1$ , and cut it after position $k \defeq m - \ell$ , which satisfies $1 \leqslant k < n - \ell + 1$ . The first part of the theorem on general associativity gives

p(b_\ell, \ldots, b_n) = p(b_\ell, \ldots, b_{m-1}) + p(b_m, \ldots, b_n),

and the previous proposition rewrites each of the three left-associated sums as the corresponding interval sum.

Remark (Moving parentheses).

Once $+$ is associative the outer bracketing of a finite sum is irrelevant, and the theorem is the interval form of that fact. The reading fixed by the definition is the left-associated one, so $a_1 + a_2 + a_3 + a_4$ means $\bigl((a_1 + a_2) + a_3\bigr) + a_4$ , and the theorem equates it with $(a_1 + a_2) + (a_3 + a_4)$ and with $a_1 + (a_2 + a_3 + a_4)$ . It does not reorder the terms. Reordering needs commutativity, which the rearrangement corollary supplies for a list and the last section of this chapter supplies for an unordered index set.

Theorem 10.36 (General distributivity).

Let $U$ carry operations $+$ and $\cdot$ with $c \cdot (x + y) = (c \cdot x) + (c \cdot y)$ for all $c, x, y \in U$ . Then for $c \in U$ and $m \leqslant n$ ,

c \cdot \sum_{i=m}^{n} b_i = \sum_{i=m}^{n} (c \cdot b_i).

Discussion.

An identity over an interval whose length is not fixed, so it is an induction on that length, with the upper limit climbing from $m$ to $n$ . The base is the single-term clause, where both sides are $c \cdot b_m$ . The step uses the hypothesis on $U$ once: expand the left side by the recursive clause, apply the binary distributive law to split $c$ across the two summands, replace the shorter sum by the inductive hypothesis, and reassemble by the recursive clause on the right. Associativity is not needed anywhere, so the theorem is stated for any pair of operations.

Proof.

Induct on $t \in \{0, \ldots, n - m\}$ , writing $k = m + t$ . At $t = 0$ both sides are $c \cdot b_m$ . Suppose the identity holds at $t$ and $t < n - m$ . Then

\begin{aligned} c \cdot \sum_{i=m}^{k+1} b_i &= c \cdot \left(\left(\sum_{i=m}^{k} b_i\right) + b_{k+1}\right) \\ &= \left(c \cdot \sum_{i=m}^{k} b_i\right) + (c \cdot b_{k+1}) \\ &= \left(\sum_{i=m}^{k} (c \cdot b_i)\right) + (c \cdot b_{k+1}) = \sum_{i=m}^{k+1} (c \cdot b_i), \end{aligned}

by the recursive clause, distributivity, the inductive hypothesis, and the recursive clause again. Taking $t = n - m$ gives the theorem.

If the multiplication is not commutative the matching right-hand law, $\bigl(\sum b_i\bigr) \cdot c = \sum (b_i \cdot c)$ , is proved by the same induction from the right distributive law.

Theorem 10.37 (Termwise sums, zeros and negatives).

Let $m \leqslant n$ and let $(b_i)$ and $(c_i)$ be defined on $\{m, \ldots, n\}$ .

If $(U, +)$ is an abelian semigroup, then $\displaystyle\sum_{i=m}^{n} (b_i + c_i) = \sum_{i=m}^{n} b_i + \sum_{i=m}^{n} c_i$ .
If $U$ has an identity $0$ for $+$ , then $\displaystyle\sum_{i=m}^{n} 0 = 0$ .
If $(U, +)$ is an abelian group, then $\displaystyle -\sum_{i=m}^{n} b_i = \sum_{i=m}^{n} (-b_i)$ .

Discussion.

The first two are inductions on the length, of the same shape as the one just done. In the first the step produces a four-term expression on the left and must match a four-term expression on the right, and the matching is a rearrangement, so this uses commutativity as well as associativity. In the second the step adds one more $0$ to a running total already equal to $0$ , and $0 + 0 = 0$ . The third needs no induction: by the first two parts the two sums add to $0$ , so each is the inverse of the other by uniqueness of inverses.

Proof.

For the first, induct on $t$ with $k = m + t$ . At $t = 0$ both sides are $b_m + c_m$ . At the step,

\sum_{i=m}^{k+1} (b_i + c_i) = \left(\sum_{i=m}^{k} b_i + \sum_{i=m}^{k} c_i\right) + (b_{k+1} + c_{k+1}),

and rearranging the four summands by associativity and commutativity gives $\bigl(\sum_{i=m}^{k+1} b_i\bigr) + \bigl(\sum_{i=m}^{k+1} c_i\bigr)$ .

For the second, induct likewise: the single-term sum is $0$ , and $0 + 0 = 0$ .

For the third, the first two parts give

\sum_{i=m}^{n} b_i + \sum_{i=m}^{n} (-b_i) = \sum_{i=m}^{n} \bigl(b_i + (-b_i)\bigr) = \sum_{i=m}^{n} 0 = 0,

and the same computation in the other order, so $\sum (-b_i)$ is an inverse of $\sum b_i$ and hence is $-\sum b_i$ .

Theorem 10.38 (Index shift).

Let $(U, +)$ be a set with an operation, let $m \leqslant n$ , and let $k \in \mathbb{Z}$ . Then

\sum_{i=m}^{n} b_i = \sum_{i=m+k}^{n+k} b_{i-k}.

Discussion.

First, the right-hand sum makes sense, because $m + k \leqslant i \leqslant n + k$ gives $m \leqslant i - k \leqslant n$ , so every term named is a term of $(b_i)$ . The identity itself is an induction on the length: at the base both sides are $b_m$ , and at each step the term appended on the left is $b_{k'+1}$ while the term appended on the right is $b_{(k'+1+k)-k}$ , and those are the same element. This is the relation between shifted sequences mentioned earlier: two different functions with the same sum.

Proof.

Induct on $t \in \{0, \ldots, n - m\}$ , writing $l = m + t$ . At $t = 0$ both sides are $b_m$ . If the identity holds at $t$ , then

\sum_{i=m}^{l+1} b_i = \left(\sum_{i=m}^{l} b_i\right) + b_{l+1} = \left(\sum_{i=m+k}^{l+k} b_{i-k}\right) + b_{(l+1+k)-k} = \sum_{i=m+k}^{(l+1)+k} b_{i-k},

by the recursive clause, the inductive hypothesis, and the recursive clause again.

Proposition 10.39 (Agreement on an interval).

Let $(a_i)$ and $(b_i)$ be sequences in $U$ whose index sets both contain $\{m, \ldots, n\}$ , and suppose $a_i = b_i$ for every $i$ in that interval. Then their sums over it agree.

Discussion.

We need this because a sequence may be defined on a larger index set than the one being summed over, so the two sequences need not be equal as functions. The sum depends only on the terms named: equal single terms give the base, and the recursive clause appends equal terms at each step, so equality is preserved all the way up.

Proof.

Induct on $t \in \{0, \ldots, n - m\}$ . At $t = 0$ both sums are $a_m = b_m$ . If the sums to $m + t$ agree and $t < n - m$ , the recursive clause appends $a_{m+t+1} = b_{m+t+1}$ to each.

Problem 10.18.

Using only the definition, show that $\sum_{i=1}^{1} a_i = a_1$ , that $\sum_{i=1}^{2} a_i = a_1 + a_2$ , that $\sum_{i=1}^{3} a_i = (a_1 + a_2) + a_3$ , and that $\sum_{i=1}^{4} a_i = \bigl((a_1 + a_2) + a_3\bigr) + a_4$ .

Problem 10.19.

Show that the binary distributive law in $U$ is the case $m = 1$ , $n = 2$ of general distributivity, and that the case $\ell = 1$ , $m = 2$ , $n = 3$ of the splitting theorem is the ordinary associative law.

Problem 10.20.

Show that $\sum_{i=m}^{n} b_i$ agrees with the summation symbol of the chapter on the natural numbers when $m = 1$ and the values lie in a Peano system with addition.

Products over an Interval

Definition 10.40 (Products over an interval).

Let $(b_i)$ have values in a set $U$ carrying an operation written multiplicatively, and let $m$ lie in its index set. For $n \geqslant m$ define

\prod_{i=m}^{m} b_i \defeq b_m, \qquad \prod_{i=m}^{k+1} b_i \defeq \left(\prod_{i=m}^{k} b_i\right) \cdot b_{k+1} \quad (k \geqslant m).

Everything proved for sums holds for products, because nothing proved for sums used anything about $+$ beyond the recursion and the laws named in each hypothesis. Replacing $+$ by $\cdot$ and $0$ by $1$ throughout turns each statement above into its multiplicative twin, and each proof into a proof of it: the splitting theorem, general distributivity read the other way, termwise products, the product of ones, the index shift, and agreement on an interval. We use them under those names without restating them, and taking $m = 1$ recovers the product symbol of the chapter on the natural numbers.

One consequence is used often when taking products apart.

Proposition 10.41 (Splitting off the first factor).

Let $U$ have a multiplication with identity $1$ , and let $m \leqslant n$ . Then there is $b \in U$ with

\prod_{j=m}^{n} a_j = a_m \cdot b.

Discussion.

An existence claim, and there are two cases according to whether the interval has one term or more. If $n = m$ the product is $a_m$ itself, and $b = 1$ serves, which is the only place the identity element is needed. If $m < n$ the splitting theorem cuts the product after the first factor, and the second block is the required $b$ ; no computation is involved beyond naming it.

Proof.

If $n = m$ then $\prod_{j=m}^{m} a_j = a_m = a_m \cdot 1$ , so $b = 1$ serves. If $m < n$ then the splitting theorem with the cut after the first factor gives

\prod_{j=m}^{n} a_j = \left(\prod_{j=m}^{m} a_j\right) \cdot \left(\prod_{j=m+1}^{n} a_j\right) = a_m \cdot \left(\prod_{j=m+1}^{n} a_j\right),

so the second block serves as $b$ .

Remark (Left association as the default).

An unbracketed $a + b + c$ means the sum of the three-term sequence, hence $(a + b) + c$ , and longer unbracketed sums and products are read the same way. That matches the convention already fixed for the left-associated product and for composition of functions. The factorial may now be written $n! = \prod_{k=1}^{n} k$ for $n \in \mathbb{N}$ , with the empty product $0! = 1$ already recorded there.

Problem 10.21.

Using only the definition, expand $\prod_{i=1}^{k} a_i$ for $k = 1, 2, 3, 4$ and check that the reading is left-associated. State the identity obtained from the splitting theorem for products with $\ell = 1$ , $m = 3$ , $n = 5$ .

Sums over an Unordered Index Set

An interval carries an order, so its terms arrive in a fixed sequence. When $+$ is commutative as well as associative the order should not matter, and then the index set need not be ordered at all: one wants $\sum_{i \in I} b_i$ for an arbitrary finite $I$ . Throughout this section $(U, +)$ is a commutative monoid (associative, commutative, with an identity $0$ ), and $(b_i)_{i \in I}$ means a function $b : I \to U$ .

The plan is to sum along an ordering and then prove the answer independent of it.

Definition 10.42 (Sum along an ordering).

Let $I$ be finite with $\#I = n$ , let $(b_i)_{i \in I}$ have values in $U$ , and let $f : \langle n \rangle \to I$ be a bijection, with $\langle 0 \rangle = \emptyset$ . Define

\sum_{i \in I}^{(f)} b_i \defeq \begin{cases} 0 & \text{if } n = 0, \\ \displaystyle\sum_{j=1}^{n} b_{f(j)} & \text{if } n \geqslant 1. \end{cases}

Proposition 10.43 (Peeling the last index).

Let $\#I = n \geqslant 1$ , let $f : \langle n \rangle \to I$ be a bijection, put $x \defeq f(n)$ , and let $f_1$ be the restriction of $f$ to a bijection $\langle n-1 \rangle \to I \setminus \{x\}$ . Then

\sum_{i \in I}^{(f)} b_i = \left(\sum_{i \in I \setminus \{x\}}^{(f_1)} b_i\right) + b_x.

Discussion.

First, the restriction is a bijection onto $I \setminus \{x\}$ because $f$ is injective and $f(n) = x$ , so nothing below $n$ is sent to $x$ . The identity itself splits into two cases. When $n = 1$ the left side is $b_x$ and the right side is $0 + b_x$ , so the identity law applies; this is where the convention for the empty sum is used. When $n > 1$ the recursive clause peels the last term off the interval sum, and what is left is the interval sum of $j \mapsto b_{f(j)}$ over $\langle n - 1 \rangle$ ; that agrees with the sum along $f_1$ because the two sequences take equal values there, which is the proposition on agreement.

Proof.

If $n = 1$ then $I = \{x\}$ , the left side is $b_{f(1)} = b_x$ , and the right side is $0 + b_x = b_x$ .

If $n > 1$ the recursive clause gives

\sum_{j=1}^{n} b_{f(j)} = \left(\sum_{j=1}^{n-1} b_{f(j)}\right) + b_{f(n)},

and $b_{f(n)} = b_x$ . The sequences $j \mapsto b_{f(j)}$ and $j \mapsto b_{f_1(j)}$ agree on $\langle n-1 \rangle$ , so their sums there agree by the proposition on agreement, and that sum is the sum along $f_1$ .

Proposition 10.44 (The ordering does not matter).

Let $I$ be finite with $\#I = n$ and let $f, g : \langle n \rangle \to I$ be bijections. Then

\sum_{i \in I}^{(f)} b_i = \sum_{i \in I}^{(g)} b_i.

Discussion.

The claim is universal in $n$ and we use strong induction, since the step will need the hypothesis at $n - 2$ as well as at $n - 1$ . At $n = 0$ and $n = 1$ there is only one bijection available, so there is nothing to compare. For $n \geqslant 2$ we look at where the two orderings put their last element, $x = f(n)$ and $y = g(n)$ . If they agree, peeling both by the previous proposition leaves two sums over the same smaller set, which the hypothesis identifies. If they differ, we cannot peel to a common set in one step, so we take two: choose an ordering of $I \setminus \{x\}$ ending at $y$ and an ordering of $I \setminus \{y\}$ ending at $x$ (these exist because a transposition rearranges any ordering to end where we like), and peel each side twice. Both sides then reduce to the same sum over $I \setminus \{x, y\}$ with $b_x$ and $b_y$ attached, in opposite orders, and commutativity finishes.

Proof.

We first record that for any $z \in I$ there is a bijection $\langle n \rangle \to I$ sending $n$ to $z$ : take any bijection $h$ and compose it with the transposition of $h^{-1}(z)$ and $n$ in $\langle n \rangle$ , which is a bijection.

Now induct strongly on $n$ . If $n \leqslant 1$ the two bijections coincide, since $\langle 0 \rangle = \emptyset$ has one map to $\emptyset$ and $\langle 1 \rangle$ has one map to a singleton.

Let $n \geqslant 2$ and assume the claim for all index sets of smaller cardinality. Put $x = f(n)$ and $y = g(n)$ , with restrictions $f_1, g_1$ as in the previous proposition.

If $x = y$ , peeling both sides gives sums over $I \setminus \{x\}$ along $f_1$ and along $g_1$ , which agree by the inductive hypothesis, so the two sides agree.

If $x \neq y$ , choose a bijection $f_2 : \langle n-1 \rangle \to I \setminus \{x\}$ with $f_2(n-1) = y$ and a bijection $g_2 : \langle n-1 \rangle \to I \setminus \{y\}$ with $g_2(n-1) = x$ , and let $f_3, g_3$ be their restrictions to bijections onto $I \setminus \{x, y\}$ . Write $T$ for the common value of the sums over $I \setminus \{x,y\}$ along $f_3$ and along $g_3$ , equal by the inductive hypothesis. Peeling twice on each side,

\sum_{i \in I}^{(f)} b_i = (T + b_y) + b_x, \qquad \sum_{i \in I}^{(g)} b_i = (T + b_x) + b_y,

where the inductive hypothesis at $n-1$ was used to replace $f_1$ by $f_2$ and $g_1$ by $g_2$ . Associativity and commutativity make the two right-hand sides equal.

Definition 10.45 (Sum over a finite index set).

Let $I$ be finite and let $(b_i)_{i \in I}$ have values in $U$ . Define

\sum_{i \in I} b_i \defeq \sum_{i \in I}^{(f)} b_i

for any bijection $f : \langle \#I \rangle \to I$ , which the previous proposition makes independent of the choice.

Proposition 10.46 (Agreement with interval sums).

If $m \leqslant n$ in $\mathbb{Z}$ , then $\displaystyle\sum_{i \in \{m, \ldots, n\}} b_i = \sum_{i=m}^{n} b_i$ .

Discussion.

The two sides are sums of the same terms under two definitions, and to compare them we need a bijection $\langle N \rangle \to \{m, \ldots, n\}$ , which the proposition on intervals gives: $j \mapsto j + (m-1)$ is one, with $N = n - m + 1$ . Summing along it produces an interval sum from $1$ to $N$ of the shifted sequence, and the index-shift theorem carries that back to the sum from $m$ to $n$ . So the work is in the index shift.

Proof.

Put $N \defeq n - m + 1 = \#\{m, \ldots, n\}$ . The map $f : \langle N \rangle \to \{m, \ldots, n\}$ with $f(j) \defeq j + (m-1)$ is a bijection, with inverse $i \mapsto i - m + 1$ . Hence

\sum_{i \in \{m, \ldots, n\}} b_i = \sum_{j=1}^{N} b_{f(j)} = \sum_{j=1}^{N} b_{j + (m-1)} = \sum_{i=m}^{n} b_i,

the last step being the index shift with $k = m - 1$ .

Theorem 10.47 (Peeling and splitting).

Let $I$ be finite and let $(b_i)_{i \in I}$ have values in $U$ .

If $I = \emptyset$ then $\sum_{i \in I} b_i = 0$ , and if $I = \{x\}$ then $\sum_{i \in I} b_i = b_x$ .
If $x \in I$ then $\displaystyle\sum_{i \in I} b_i = \left(\sum_{i \in I \setminus \{x\}} b_i\right) + b_x$ .
If $I = I_1 \cup I_2$ with $I_1 \cap I_2 = \emptyset$ , then $\displaystyle\sum_{i \in I} b_i = \sum_{i \in I_1} b_i + \sum_{i \in I_2} b_i$ .

Discussion.

The first part is the definition, read at the two smallest index sets. The second is the proposition on peeling for a chosen element: that proposition peeled whichever element the ordering put last, and since the sum no longer depends on the ordering we may choose one that puts the element we want there, which the transposition trick supplies. The third is the main one and is proved by building an ordering of $I$ out of orderings of the two pieces, laid end to end; it is a bijection because the pieces are disjoint, and the cardinality of a disjoint union says its domain has the right size. Summing along it and cutting after the first block is the splitting theorem, and the second block needs an index shift to be recognised as a sum over $I_2$ . The empty cases are handled first, since an ordering of an empty piece is not available to concatenate.

Proof.

The first part is the definition together with the case $n = 1$ of peeling.

For the second, choose a bijection $f : \langle n \rangle \to I$ with $f(n) = x$ , as in the proof of the previous proposition, and apply peeling; the two sums are independent of the orderings by that proposition.

For the third, put $n_1 \defeq \#I_1$ and $n_2 \defeq \#I_2$ , so $\#I = n_1 + n_2$ . If $n_1 = 0$ then $I_1 = \emptyset$ and $I_2 = I$ , and the claim reads $s = 0 + s$ ; the case $n_2 = 0$ is the same. Suppose both are positive, choose bijections $f_1 : \langle n_1 \rangle \to I_1$ and $f_2 : \langle n_2 \rangle \to I_2$ , and define $f : \langle n_1 + n_2 \rangle \to I$ by

f(j) \defeq \begin{cases} f_1(j) & \text{if } j \leqslant n_1, \\ f_2(j - n_1) & \text{if } n_1 < j. \end{cases}

Disjointness of $I_1$ and $I_2$ makes $f$ injective, and it is surjective because $I$ is their union. Then

\sum_{i \in I} b_i = \sum_{j=1}^{n_1 + n_2} b_{f(j)} = \sum_{j=1}^{n_1} b_{f(j)} + \sum_{j = n_1 + 1}^{n_1 + n_2} b_{f(j)}

by the splitting theorem. The first block is $\sum_{i \in I_1} b_i$ . In the second, the index shift by $k = -n_1$ turns it into $\sum_{j=1}^{n_2} b_{f(j + n_1)} = \sum_{j=1}^{n_2} b_{f_2(j)}$ , which is $\sum_{i \in I_2} b_i$ .

Theorem 10.48 (Reindexing).

Let $I$ and $I'$ be finite, let $(b_i)_{i \in I}$ have values in $U$ , and let $\sigma : I' \to I$ be a bijection. Then

\sum_{i \in I'} b_{\sigma(i)} = \sum_{i \in I} b_i.

Discussion.

Both sides are defined by choosing an ordering, and the sum does not depend on which, so we are free to choose orderings that make the two sides identical term by term. An ordering $f$ of $I'$ produces one of $I$ by composing with $\sigma$ , since a composite of bijections is a bijection; and the $j$ -th term of the left sum along $f$ is $b_{\sigma(f(j))}$ , which is the $j$ -th term of the right sum along $\sigma \circ f$ . So the two interval sums are the same sum.

Proof.

If $I = \emptyset$ then $I' = \emptyset$ and both sides are $0$ . Otherwise put $n \defeq \#I = \#I'$ and choose a bijection $f : \langle n \rangle \to I'$ . Then $\sigma \circ f : \langle n \rangle \to I$ is a bijection, and

\sum_{i \in I'} b_{\sigma(i)} = \sum_{j=1}^{n} b_{\sigma(f(j))} = \sum_{j=1}^{n} b_{(\sigma \circ f)(j)} = \sum_{i \in I} b_i,

each outer equality being the definition of the sum over an index set.

Corollary 10.49 (Rearranging a sum).

Let $I$ be finite and let $\sigma$ be a permutation of $I$ . Then $\sum_{i \in I} b_i = \sum_{i \in I} b_{\sigma(i)}$ .

Proof.

Reindexing with $I' = I$ .

That is the general commutative law for sums, and the rearrangement corollary of the chapter on groups is the case where $I$ is an interval and $\sigma$ is written as a permutation of positions. Termwise addition carries over to unordered index sets the same way: choose an ordering and quote the interval statement.

Proposition 10.50 (Termwise sums, unordered).

Let $I$ be finite and let $(b_i)_{i \in I}$ and $(c_i)_{i \in I}$ have values in $U$ . Then

\sum_{i \in I} (b_i + c_i) = \sum_{i \in I} b_i + \sum_{i \in I} c_i.

Discussion.

The empty case is the identity law, $0 = 0 + 0$ . Otherwise choose any ordering; each of the three sums becomes an interval sum along it, and the interval version of termwise addition applies to the two ordered sequences. The choice of ordering does not matter, by the proposition on independence.

Proof.

If $I = \emptyset$ both sides are $0$ . Otherwise let $n = \#I$ and let $f : \langle n \rangle \to I$ be a bijection. Then

\begin{aligned} \sum_{i \in I} (b_i + c_i) &= \sum_{j=1}^{n} \bigl(b_{f(j)} + c_{f(j)}\bigr) \\ &= \sum_{j=1}^{n} b_{f(j)} + \sum_{j=1}^{n} c_{f(j)} = \sum_{i \in I} b_i + \sum_{i \in I} c_i, \end{aligned}

by the interval theorem on termwise sums.

Everything in this section holds for products over a commutative monoid written multiplicatively, with $1$ in place of $0$ ; the definitions, the independence of the ordering, peeling, splitting, reindexing and the commutative law all carry over under that substitution, and their proofs with them.

Problem 10.22.

State the product analogues of the definition of $\prod_{i \in I} b_i$ and of the peeling and splitting theorem, and say which line of each proof changes.

Problem 10.23.

Let $I = \{1, 2, 3\}$ and let $\sigma$ be the permutation $1 \mapsto 2 \mapsto 3 \mapsto 1$ . Expand both sides of the rearrangement corollary for a general $(b_i)_{i \in I}$ in $\mathbb{Z}$ .

Problem 10.24.

Let $I$ and $J$ be finite and let $a_{i,j} \in U$ for $i \in I$ and $j \in J$ . Show that summing along $I$ first and then along $J$ gives the same element as summing along $J$ first and then along $I$ .

Divisibility

$(\mathbb{Z}, +)$ is a group and $(\mathbb{Z}, \cdot)$ is not, since only $1$ and $-1$ have multiplicative inverses. So exact division inside $\mathbb{Z}$ is rare. The study of when one integer divides another is number theory, and this section is its beginning.

Divisors

Proposition 10.51 (The only invertible integers).

Let $a, b \in \mathbb{Z}$ with $ab = 1$ . Then either $a = b = 1$ or $a = b = -1$ .

Discussion.

The hypothesis pins a product to a particular value, and we use the order to get information about the factors. So we work through the signs. Neither factor can be $0$ , since a product with a zero factor is $0$ and $0 \neq 1$ . They cannot have opposite signs, since a positive times a negative is negative while $1$ is positive. That leaves both positive or both negative. If both are positive, each is at least $1$ by the corollary on the least positive integer, and if $a$ were strictly larger than $1$ then multiplying that inequality by the positive $b$ would push $ab$ above $b$ and so above $1$ ; so $a = 1$ , and then $b = 1$ . The negative case is the positive one applied to $-a$ and $-b$ , whose product is again $1$ .

Proof.

Neither factor is $0$ , since $0 \cdot b = 0 \neq 1$ . If one is positive and the other negative, their product is negative, while $1$ is positive; so both are positive or both are negative.

Suppose both are positive. Then $1 \leqslant a$ and $1 \leqslant b$ . If $1 < a$ , multiplying by the positive $b$ gives $b < ab = 1$ , contradicting $1 \leqslant b$ . So $a = 1$ , and $b = 1 \cdot b = ab = 1$ .

If both are negative then $-a$ and $-b$ are positive and $(-a)(-b) = ab = 1$ , so $-a = -b = 1$ and $a = b = -1$ .

Definition 10.52 (Divisibility).

Let $a, b \in \mathbb{Z}$ with $a \neq 0$ . Then $a$ divides $b$ , written $a \mid b$ , if $b = ac$ for some $c \in \mathbb{Z}$ ; in that case $a$ is a divisor of $b$ and $b$ a multiple of $a$ . When $a$ does not divide $b$ we write $a \nmid b$ .

The condition $a \neq 0$ is part of the notation: wherever $a \mid b$ appears as a hypothesis, $a \neq 0$ is part of it. Usage keeps divisor for the general statement and factor for a number appearing in a particular product, so $1, 2, 3, 4, 6$ and $12$ are the positive divisors of $12$ , while $3$ and $4$ are the factors of $12$ in the expression $12 = 3 \cdot 4$ . This is the notion the problem on divisibility introduced for natural numbers, now stated where negative multipliers are available.

Definition 10.53 (Prime).

An integer $p > 1$ whose only positive divisors are $1$ and $p$ is prime.

This makes precise a word we have used informally since the first chapter, and it restates two old results: that $n$ is even says exactly that $2 \mid n$ , and the proposition that odd squares are odd now reads $2 \mid n$ if and only if $2 \mid n^2$ . The four rules below are the basic arithmetic of divisibility.

Proposition 10.54 (The arithmetic of divisibility).

Let $a, b, c, d \in \mathbb{Z}$ with the divisors below non-zero.

If $a \mid b$ and $b \mid c$ , then $a \mid c$ .
If $a \mid c$ and $b \mid d$ , then $ab \mid cd$ .
If $a \mid b$ and $a \mid c$ , then $a \mid bx + cy$ for all $x, y \in \mathbb{Z}$ .
If $a \mid b$ or $a \mid c$ , then $a \mid bc$ .

Discussion.

All four are proved the same way. Each hypothesis $a \mid b$ unpacks by the definition into an equation $b = ak$ with $k$ an integer, and each conclusion asks for one integer of the same shape; so in every case the work is to substitute the hypotheses into the expression named in the conclusion, regroup by associativity, commutativity and distributivity until a single factor of the intended divisor stands in front, and observe that what remains in the bracket is an integer because $\mathbb{Z}$ is closed under the operations. The first substitutes one equation into the other and takes the product of the two multipliers. The second multiplies the two equations and regroups. The third is the one where the shared divisor matters: both unpackings carry the same $a$ , so distributivity pulls it out of the combination. The fourth is a disjunction, hence two cases, each of which is the first line of the others. Nothing needs the order, and nothing needs a case split on sign.

Proof.

For the first, write $b = ak_1$ and $c = bk_2$ . Then $c = (ak_1)k_2 = a(k_1k_2)$ , and $k_1k_2 \in \mathbb{Z}$ , so $a \mid c$ .

For the second, write $c = ak_1$ and $d = bk_2$ . Then $cd = (ak_1)(bk_2) = (ab)(k_1k_2)$ by associativity and commutativity, so $ab \mid cd$ .

For the third, write $b = ak_1$ and $c = ak_2$ . For any $x, y \in \mathbb{Z}$ ,

bx + cy = (ak_1)x + (ak_2)y = a(k_1x + k_2y)

by distributivity, and $k_1x + k_2y \in \mathbb{Z}$ , so $a \mid bx + cy$ .

For the fourth, suppose $a \mid b$ , so $b = ak$ . Then $bc = (ak)c = a(kc)$ and $kc \in \mathbb{Z}$ , so $a \mid bc$ . If instead $a \mid c$ , the same argument applies with $b$ and $c$ exchanged.

Corollary 10.55 (Sums and differences).

If $a \mid b$ and $a \mid c$ , then $a \mid b + c$ and $a \mid b - c$ .

Proof.

Take $x = y = 1$ , and then $x = 1$ , $y = -1$ , in the third part of the proposition.

Theorem 10.56 (Each factor divides the product).

Let $(a_j)$ be a sequence in $\mathbb{Z}$ defined on $\{m, \ldots, n\}$ with $m \leqslant n$ , and let $i \in \{m, \ldots, n\}$ with $a_i \neq 0$ . Then

a_i \; \Bigg| \; \prod_{j=m}^{n} a_j .

Discussion.

The conclusion asks for the product to be written with $a_i$ standing in front, so we move $a_i$ there. If $i$ is the first index, the proposition on splitting off the first factor has already done it. Otherwise cut the product just before $i$ by the splitting theorem for products; the second block now begins at $i$ , so splitting off its first factor exposes $a_i$ , and what is left is the first block times whatever followed. Commutativity and associativity of multiplication in $\mathbb{Z}$ then move $a_i$ to the front of the whole, and the remaining bracket is an integer because a product of integers is one. The hypothesis $a_i \neq 0$ is needed only because the divisibility symbol demands it.

Proof.

If $i = m$ , the proposition on splitting off the first factor gives $\prod_{j=m}^{n} a_j = a_m \cdot b$ for some $b \in \mathbb{Z}$ , so $a_m$ divides the product.

Suppose $m < i$ . The splitting theorem for products, cutting before $i$ , gives

\prod_{j=m}^{n} a_j = \left(\prod_{j=m}^{i-1} a_j\right) \cdot \left(\prod_{j=i}^{n} a_j\right),

and splitting off the first factor of the second block writes it as $a_i \cdot b$ for some $b \in \mathbb{Z}$ . Writing $A$ for the first block,

\prod_{j=m}^{n} a_j = A \cdot (a_i \cdot b) = a_i \cdot (b \cdot A)

by commutativity and associativity, and $b \cdot A \in \mathbb{Z}$ . So $a_i$ divides the product.

Division with Remainder

Non-divisibility is harder to use than divisibility, because it gives no equation. Instead we use the remainder, and every integer has exactly one. That was proved for $\mathbb{N}_0$ in the chapter on order; it extends to $\mathbb{Z}$ with one extra step.

Theorem 10.57 (Division with remainder in the integers).

Let $a \in \mathbb{Z}$ and $m \in \mathbb{N}$ . Then there is exactly one pair $q, r \in \mathbb{Z}$ with

a = qm + r, \qquad 0 \leqslant r < m.

Discussion.

An existence-and-uniqueness claim, and the two halves need different arguments, as they did over $\mathbb{N}_0$ . For existence we look for the remainder rather than the quotient: the numbers $a - qm$ that land in $\mathbb{N}_0$ form a set to which well-ordering applies, provided it is non-empty. That is the one new step, since a negative $a$ leaves nothing when $q = 0$ ; taking $q = a$ works, because multiplying a negative $a$ by $m \geqslant 1$ only makes it more negative. Minimality of the least member then forces it below $m$ , since otherwise one more $m$ could be subtracted. Uniqueness is the argument from the earlier theorem word for word: two decompositions give a multiple of $m$ equal to a difference of remainders, which is trapped strictly between $-m$ and $m$ and so is $0$ .

Proof.

For existence, let $R \defeq \{a - qm \mid q \in \mathbb{Z}\} \cap \mathbb{N}_0$ . It is non-empty: if $0 \leqslant a$ then $q = 0$ gives $a \in R$ ; and if $a < 0$ then $q = a$ gives $a - am = a(1 - m) \geqslant 0$ , since $a < 0$ and $1 - m \leqslant 0$ .

Well-ordering supplies $r \defeq \min R$ , with $a = qm + r$ for some $q \in \mathbb{Z}$ and $0 \leqslant r$ . If $m \leqslant r$ then $r - m \in \mathbb{N}_0$ and $a - (q+1)m = r - m$ , so $r - m \in R$ ; but $r - m < r$ because $m$ is positive, contradicting minimality. Hence $r < m$ .

For uniqueness, suppose $q_1m + r_1 = q_2m + r_2$ with $0 \leqslant r_1, r_2 < m$ . Then $(q_1 - q_2)m = r_2 - r_1$ , and $-m < r_2 - r_1 < m$ . If $q_1 - q_2$ were non-zero its absolute size would be at least $1$ , so $(q_1 - q_2)m$ would be at least $m$ or at most $-m$ , which the bounds forbid. Hence $q_1 = q_2$ , and then $r_1 = r_2$ .

Corollary 10.58 (Remainder forms).

Let $m \in \mathbb{N}$ . Every $a \in \mathbb{Z}$ has exactly one of the $m$ forms $qm$ , $qm + 1$ , …, $qm + (m-1)$ with $q \in \mathbb{Z}$ . In particular $m \mid a$ if and only if the remainder is $0$ .

Proof.

The theorem gives exactly one pair $q, r$ with $a = qm + r$ and $r < m$ , and the available values of $r$ are $0, 1, \ldots, m-1$ . If $r = 0$ then $a = qm$ and $m \mid a$ ; conversely $a = qm$ is a decomposition with remainder $0$ , which uniqueness makes the only one.

So $m \nmid a$ says that $a$ takes one of the $m - 1$ forms $qm + 1, \ldots, qm + (m-1)$ , and a proof from a non-divisibility hypothesis is a proof by cases with that many cases. Taking $m = 2$ recovers the familiar reading: $2 \nmid a$ says $a = 2q + 1$ . The next proposition is the pattern at $m = 3$ .

Proposition 10.59 (Divisibility by three).

Let $a \in \mathbb{Z}$ . If $3 \nmid a^2 - 1$ , then $3 \mid a$ .

Discussion.

The statement is a conditional $p \to q$ in which $p$ is " $3 \nmid a^2 - 1$ " and $q$ is " $3 \mid a$ ". A direct proof would have to start from a non-divisibility fact about $a^2 - 1$ , which offers no equation to work with, so we take the contrapositive: if $3 \nmid a$ then $3 \mid a^2 - 1$ . That still opens with a non-divisibility, but now it is a hypothesis rather than a conclusion, and the corollary converts it into two cases, $a = 3k + 1$ and $a = 3k + 2$ . Each case is then ordinary algebra: expand $a^2 - 1$ , take a factor of $3$ out, and check that what remains in the bracket is an integer.

Proof.

We prove the contrapositive: if $3 \nmid a$ , then $3 \mid a^2 - 1$ . By the corollary, $a = 3k + 1$ or $a = 3k + 2$ for some $k \in \mathbb{Z}$ .

If $a = 3k + 1$ , then

a^2 - 1 = (3k+1)^2 - 1 = 9k^2 + 6k = 3(3k^2 + 2k),

and $3k^2 + 2k \in \mathbb{Z}$ , so $3 \mid a^2 - 1$ .

If $a = 3k + 2$ , then

a^2 - 1 = (3k+2)^2 - 1 = 9k^2 + 12k + 3 = 3(3k^2 + 4k + 1),

and $3k^2 + 4k + 1 \in \mathbb{Z}$ , so $3 \mid a^2 - 1$ .

Remark (Exhibiting a remainder is enough).

The corollary works in both directions. If $a = 3k + 1$ or $a = 3k + 2$ for some $k$ , then $3 \nmid a$ , because divisibility would give $a$ the form $3k'$ and each integer has exactly one of the three forms. So when the conclusion wanted is itself a non-divisibility, exhibiting a remainder settles it, and the same holds with any $m$ in place of $3$ .

Problem 10.25.

Show that $3 \nmid a^2 + 1$ for every $a \in \mathbb{Z}$ .

Problem 10.26.

Show that $a \mid b$ and $b \mid a$ together force $b = a$ or $b = -a$ , and that $a \mid b$ with $b \neq 0$ forces $a \leqslant b$ or $b \leqslant a$ according to sign — state the inequality carefully before proving it.

Problem 10.27.

Let $p_1, \ldots, p_k \in \mathbb{Z}$ be non-zero and let $\sigma \in S_k$ . Using the theorem on factors and the rearrangement corollary, show that each $p_i$ divides $p_{\sigma(1)} \cdots p_{\sigma(k)}$ as well as $p_1 \cdots p_k$ .

Problem 10.28.

Show that the square of an integer leaves remainder $0$ or $1$ on division by $4$ , and deduce that no integer of the form $4k + 3$ is a sum of two squares.

Rings and Fields

This last section names the structure formed by $+$ and $\cdot$ on $\mathbb{Z}$ , and shows that the construction of $\mathbb{Z}$ works for any monoid with the right properties.

The Construction Was Not Special

Look back at what the first half of the chapter used. It took $(\mathbb{N}_0, +)$ , a commutative monoid in which cancellation holds, and produced a group containing a copy of it. Cancellation entered once, in the proof of transitivity. Commutativity and the identity entered in the routine checks. Nothing else about $\mathbb{N}_0$ was used: not the order, not induction, not the successor.

Theorem 10.60 (Every regular commutative monoid sits inside a group).

Let $(H, *)$ be a commutative regular monoid with identity $f$ . Then there are a group $(G, *)$ with identity $e$ and an injective map $\alpha : H \to G$ such that

\alpha(f) = e, \qquad \alpha(a * b) = \alpha(a) * \alpha(b),

and such that every $c \in G$ has the form $c = \alpha(a) * \alpha(b)^{-1}$ for some $a, b \in H$ . Moreover the pair $(G, \alpha)$ is unique up to a unique isomorphism: if $(G', \alpha')$ is another such pair, there is exactly one isomorphism $\beta : G \to G'$ with $\alpha' = \beta \circ \alpha$ .

Discussion.

Two claims, one much harder than the other. The first is an existence claim, and it needs no new work: the construction of $\mathbb{Z}$ from $\mathbb{N}_0$ used only the hypotheses now assumed, so repeating it with $*$ in place of $+$ builds $G$ , and the proofs of this chapter become its proofs. We say which pieces correspond.

The second is the one to prove. Uniqueness of $\beta$ comes first and is immediate: the condition $\alpha' = \beta \circ \alpha$ fixes $\beta$ on the image of $\alpha$ , and since every element of $G$ is a quotient $\alpha(a) * \alpha(b)^{-1}$ , and a homomorphism must send an inverse to an inverse, $\beta$ is forced everywhere. That forced formula is then taken as a definition, and since an element of $G$ may be written as such a quotient in many ways, we check that two writings give the same value, which uses injectivity of $\alpha$ . That $\beta$ is a homomorphism is a short computation, and we get bijectivity by building the map the other way and observing that both composites satisfy the defining condition of the identity, which the uniqueness half then identifies them with.

Proof.

For existence, run the construction of the first half of this chapter with $H$ in place of $\mathbb{N}_0$ and $*$ in place of $+$ . Declare $(a, b) \sim (a', b')$ when $a * b' = a' * b$ ; this is an equivalence relation, the proof of transitivity using cancellation exactly where it used it for $\mathbb{N}_0$ . Let $G$ be the quotient, with $[(a,b)] * [(a',b')] \defeq [(a * a', b * b')]$ , well defined by the same computation as before. Then $(G, *)$ is an abelian group with identity $e \defeq [(f,f)]$ and $[(a,b)]^{-1} = [(b,a)]$ , and $\alpha(a) \defeq [(a, f)]$ is injective with $\alpha(f) = e$ and $\alpha(a * b) = \alpha(a) * \alpha(b)$ . Finally

\alpha(a) * \alpha(b)^{-1} = [(a,f)] * [(f,b)] = [(a * f, f * b)] = [(a, b)],

so every element of $G$ has the required form.

For uniqueness, let $(G', \alpha')$ be another such pair and suppose $\beta : G \to G'$ is a homomorphism with $\alpha' = \beta \circ \alpha$ . For $c = \alpha(a) * \alpha(b)^{-1}$ we get

\beta(c) = \beta(\alpha(a)) * \beta\bigl(\alpha(b)^{-1}\bigr) = \alpha'(a) * \alpha'(b)^{-1},

using that homomorphisms respect inverses. So $\beta$ is determined, and at most one such map exists.

That formula does define a map. Suppose $\alpha(a) * \alpha(b)^{-1} = \alpha(a') * \alpha(b')^{-1}$ . Multiplying by $\alpha(b) * \alpha(b')$ gives $\alpha(a) * \alpha(b') = \alpha(a') * \alpha(b)$ , that is $\alpha(a * b') = \alpha(a' * b)$ , so $a * b' = a' * b$ by injectivity of $\alpha$ . Applying $\alpha'$ to that equation and reversing the steps gives $\alpha'(a) * \alpha'(b)^{-1} = \alpha'(a') * \alpha'(b')^{-1}$ , so the value does not depend on the writing.

The map $\beta$ so defined is a homomorphism, since

\bigl(\alpha(a) * \alpha(b)^{-1}\bigr) * \bigl(\alpha(a') * \alpha(b')^{-1}\bigr) = \alpha(a * a') * \alpha(b * b')^{-1}

in $G$ and the same identity holds in $G'$ , both by commutativity and the inverse of a product. It satisfies $\alpha' = \beta \circ \alpha$ , by taking $b = f$ .

Exchanging the roles of $G$ and $G'$ produces a homomorphism $\beta' : G' \to G$ with $\alpha = \beta' \circ \alpha'$ . Then $\beta' \circ \beta$ is a homomorphism $G \to G$ with $(\beta' \circ \beta) \circ \alpha = \alpha$ , and so is $\mathrm{id}_G$ ; the uniqueness just proved, applied with $G' = G$ and $\alpha' = \alpha$ , forces $\beta' \circ \beta = \mathrm{id}_G$ . Likewise $\beta \circ \beta' = \mathrm{id}_{G'}$ . So $\beta$ is a bijection, hence an isomorphism.

Remark.

The theorem says the integers are the only possible answer: any group containing a copy of $(\mathbb{N}_0,+)$ in which every element is a difference of two copied elements is isomorphic to $\mathbb{Z}$ , by a unique isomorphism respecting the copy. It also saves work later. The same theorem, applied to a multiplicative monoid instead of an additive one, is what will build the rationals out of the integers, and we shall not have to write the pairs down again.

Rings, Integral Domains and Fields

Definition 10.61 (Ring).

A ring is a set $R$ with two operations $+$ and $\cdot$ such that $(R, +)$ is an abelian group, written with identity $0$ ; $(R, \cdot)$ is a semigroup; and both distributive laws hold,

a(b + c) = ab + ac, \qquad (b + c)a = ba + ca .

The ring is commutative if $\cdot$ is commutative. It is a ring with identity if there is $1 \in R$ with $1 \neq 0$ and $1 \cdot a = a \cdot 1 = a$ for every $a$ . It is free of zero divisors if $ab = 0$ forces $a = 0$ or $b = 0$ . A commutative ring with identity and free of zero divisors is an integral domain, and an integral domain in which every $a \neq 0$ is invertible under $\cdot$ is a field.

The identity of $+$ and the identity of $\cdot$ are each unique, by uniqueness of the identity applied to the two operations separately, so the notation $0$ and $1$ names something definite. Nothing yet says how the two operations interact beyond distributivity; the next proposition gives some consequences of distributivity.

Proposition 10.62 (Arithmetic in a ring).

Let $R$ be a ring and let $a, b \in R$ . Then

$0 \cdot a = a \cdot 0 = 0$ ;
$(-a)b = a(-b) = -(ab)$ ;
$(-a)(-b) = ab$ .

Discussion.

None of these is an axiom, and each has to be derived from distributivity, which is the only link between the two operations. For the first, write $0$ as $0 + 0$ and distribute: the result is an equation saying that $0 \cdot a$ added to itself is itself, and in a group only the identity does that, so cancellation finishes. The second uses the first as its target: $ab + (-a)b$ becomes, by distributivity, $\bigl(a + (-a)\bigr)b = 0 \cdot b = 0$ , which says $(-a)b$ is an additive inverse of $ab$ , and inverses are unique. The third is the second applied twice, or once with $b$ replaced by $-b$ , together with $-(-x) = x$ .

Proof.

For the first, $0 \cdot a = (0 + 0) \cdot a = 0 \cdot a + 0 \cdot a$ by the right distributive law. Cancelling $0 \cdot a$ in the group $(R, +)$ gives $0 = 0 \cdot a$ . The computation for $a \cdot 0$ is the same with the left law.

For the second, $ab + (-a)b = \bigl(a + (-a)\bigr)b = 0 \cdot b = 0$ , and likewise $(-a)b + ab = 0$ , so $(-a)b$ is an additive inverse of $ab$ and hence equals $-(ab)$ . The same argument on the other side gives $a(-b) = -(ab)$ .

For the third, replacing $b$ by $-b$ in the second part gives $(-a)(-b) = -\bigl(a(-b)\bigr) = -\bigl(-(ab)\bigr) = ab$ .

Theorem 10.63 (The integers are an integral domain).

$(\mathbb{Z}, +, \cdot)$ is an integral domain, and it is not a field.

Discussion.

Each clause of the definition has already been proved or set as a problem, so the proof mostly collects them: the additive group is the theorem of the second section, the multiplicative semigroup and its commutativity and identity are the problems of the third, and distributivity is its theorem. Two points need a comment. Freedom from zero divisors is the problem on products that vanish. That $\mathbb{Z}$ is not a field is the proposition on invertible integers, which leaves only $1$ and $-1$ invertible, so $2$ has no inverse and $2x = 1$ has no solution.

Proof.

$(\mathbb{Z}, +)$ is an abelian group by the theorem of the second section. Multiplication is associative and commutative by the problems there, with identity $1$ by the proposition on the embedding, and it distributes over addition by the theorem on distributivity; commutativity turns the one distributive law into both. The problem on vanishing products says $xy = 0$ forces $x = 0$ or $y = 0$ . So $\mathbb{Z}$ is an integral domain.

It is not a field: by the proposition on invertible integers, the only invertible elements are $1$ and $-1$ , so $2$ has no multiplicative inverse.

Example 10.64 (The smallest field).

Let $\mathbb{F}_2 \defeq \{0, 1\}$ with $0 \neq 1$ . The field axioms fix both tables. Multiplication is forced by the previous proposition and the identity law: $0 \cdot 0 = 0 \cdot 1 = 1 \cdot 0 = 0$ and $1 \cdot 1 = 1$ . For addition, only $1 + 1$ is not yet determined, and $1 + 1 = 1$ would give

1 = 1 + 0 = 1 + \bigl(1 + (-1)\bigr) = (1 + 1) + (-1) = 1 + (-1) = 0,

which is forbidden; so $1 + 1 = 0$ . The tables are

\begin{array}{c|cc} + & 0 & 1 \\ \hline 0 & 0 & 1 \\ 1 & 1 & 0 \end{array} \qquad\qquad \begin{array}{c|cc} \cdot & 0 & 1 \\ \hline 0 & 0 & 0 \\ 1 & 0 & 1 \end{array}

and one checks directly that they satisfy the axioms. A field needs $0 \neq 1$ , so no smaller field exists.

Corollary 10.65 (The binomial theorem in a commutative ring).

Let $R$ be a commutative ring with identity, let $a, b \in R$ and let $n \in \mathbb{N}_0$ . Then

(a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^k b^{n-k},

where $\binom{n}{k} x$ means the sum of $\binom{n}{k}$ copies of $x$ .

Proof.

The proof of the binomial theorem used only the commutative, associative and distributive laws and the recursion defining powers, as the remark following it recorded. Every one of those holds in a commutative ring with identity, so the argument applies word for word, with the coefficient $\binom{n}{k}$ read as an instruction to add $\binom{n}{k}$ copies.

Remark.

The coefficient cannot in general be read as an element of $R$ , since $R$ need not contain a copy of $\mathbb{N}_0$ ; what it names is a repeated sum, and repeated sums can be $0$ . In $\mathbb{F}_2$ , for instance, $2x = x + x = 0$ for every $x$ , so the middle term of $(a+b)^2$ disappears and $(a+b)^2 = a^2 + b^2$ .

Greatest Common Divisors

The next theorem, proved with division with remainder, is what we need to build fields from the integers.

Theorem 10.66 (Bézout's identity).

Let $a, b \in \mathbb{Z}$ be not both $0$ , and let

S \defeq \{ax + by \mid x, y \in \mathbb{Z}\}.

Then $S$ contains a positive element, its least positive element $d$ divides both $a$ and $b$ , and every common divisor of $a$ and $b$ divides $d$ . In particular $d = ax_0 + by_0$ for some $x_0, y_0 \in \mathbb{Z}$ .

Discussion.

Three assertions, and the first is needed for well-ordering to produce $d$ : taking $x = a$ and $y = b$ gives $a^2 + b^2$ , which is positive because a square is never negative and the two are not both $0$ . The second is the main one, and it uses division with remainder. Divide $a$ by $d$ ; the remainder is again of the form $ax + by$ , being $a$ minus a multiple of $ax_0 + by_0$ , and it is strictly below $d$ ; since $d$ was the least positive member, the remainder cannot be positive, so it is $0$ and $d$ divides $a$ . The same for $b$ . The third assertion is the easiest: a common divisor of $a$ and $b$ divides every combination $ax + by$ , by the arithmetic of divisibility, and $d$ is one of those.

Proof.

Taking $x = a$ and $y = b$ gives $a^2 + b^2 \in S$ , which is positive since squares are non-negative and $a$ and $b$ are not both $0$ . So the positive members of $S$ form a non-empty subset of $\mathbb{N}$ , and well-ordering supplies a least one, $d = ax_0 + by_0$ .

Divide: $a = qd + r$ with $0 \leqslant r < d$ . Then

r = a - qd = a - q(ax_0 + by_0) = a(1 - qx_0) + b(-qy_0),

so $r \in S$ . Were $r$ positive it would be a positive member of $S$ below $d$ , contrary to the choice of $d$ ; so $r = 0$ and $d \mid a$ . The same argument with $b$ in place of $a$ gives $d \mid b$ .

If $c$ divides both $a$ and $b$ , then $c$ divides $ax_0 + by_0 = d$ by the third part of the arithmetic of divisibility.

Definition 10.67 (Greatest common divisor and coprimality).

For $a, b \in \mathbb{Z}$ not both $0$ , the greatest common divisor $\gcd(a, b)$ is the $d$ of the theorem: the least positive integer of the form $ax + by$ . The integers $a$ and $b$ are coprime if $\gcd(a, b) = 1$ .

The name is justified by the theorem: $d$ is a common divisor, and every common divisor divides it, hence is at most $d$ . Coprimality says exactly that $1 = ax + by$ for some integers $x$ and $y$ , and the next section uses that equation.

The Integers Modulo $m$

Definition 10.68 (Congruence).

Let $m \in \mathbb{N}$ and $a, b \in \mathbb{Z}$ . Then $a$ is congruent to $b$ modulo $m$ , written $a \equiv b \pmod{m}$ , if $m \mid a - b$ .

Proposition 10.69 (Congruence is an equivalence relation).

For each $m \in \mathbb{N}$ , congruence modulo $m$ is an equivalence relation on $\mathbb{Z}$ , and its classes are in bijection with $\{0, 1, \ldots, m-1\}$ .

Discussion.

Each of the three properties follows from the definition. Reflexivity is $m \mid 0$ , which holds because $0 = m \cdot 0$ . Symmetry is the observation that $b - a$ is $-(a - b)$ , and a divisor of an integer divides its negative. Transitivity is the corollary on sums: $m$ divides $a - b$ and $b - c$ , hence their sum $a - c$ . For the count, division with remainder attaches to each integer exactly one remainder below $m$ , and two integers are congruent exactly when their remainders agree, because their difference is then a multiple of $m$ , and conversely a difference of two numbers both below $m$ cannot be a non-zero multiple of $m$ .

Proof.

Reflexivity: $a - a = 0 = m \cdot 0$ , so $m \mid a - a$ . Symmetry: if $a - b = mk$ then $b - a = m(-k)$ . Transitivity: if $m \mid a - b$ and $m \mid b - c$ then $m$ divides $(a-b) + (b-c) = a - c$ by the corollary on sums.

For the count, let $r(a)$ be the remainder of $a$ on division by $m$ . If $r(a) = r(b)$ then $a - b = (q_a - q_b)m$ , so $a \equiv b$ . Conversely if $a \equiv b$ then $r(a) - r(b) = (a - q_am) - (b - q_bm)$ is a multiple of $m$ lying strictly between $-m$ and $m$ , hence $0$ . So $a \mapsto r(a)$ induces a bijection from the classes onto $\{0, \ldots, m-1\}$ .

Definition 10.70 (The integers modulo $m$ ).

Write $[a]$ for the class of $a$ and

\mathbb{Z}/m\mathbb{Z} \defeq \mathbb{Z}\big/{\equiv} \pmod m

for the quotient, the integers modulo $m$ , with operations

[a] + [b] \defeq [a + b], \qquad [a] \cdot [b] \defeq [ab].

Theorem 10.71 (The integers modulo $m$ form a ring).

The two operations above are well defined, and $\mathbb{Z}/m\mathbb{Z}$ is a commutative ring with identity $[1]$ and zero $[0]$ , with $\#(\mathbb{Z}/m\mathbb{Z}) = m$ when $m \geqslant 2$ .

Discussion.

Well-definedness is the only thing that needs care, as in the first half of the chapter: the formulas name representatives, and a class has many. So we suppose $a \equiv a'$ and $b \equiv b'$ and must show $a + b \equiv a' + b'$ and $ab \equiv a'b'$ . The first is the corollary on sums applied to the two differences. The second needs one step more: $ab - a'b'$ does not obviously factor, so we insert and remove $a'b$ , splitting it into $b(a - a')$ and $a'(b - b')$ , each divisible by $m$ by the fourth part of the arithmetic of divisibility, and then add. Every ring axiom afterwards is the corresponding axiom of $\mathbb{Z}$ read inside the brackets, and the count is the bijection of the previous proposition.

Proof.

Suppose $m \mid a - a'$ and $m \mid b - b'$ . Then $m$ divides $(a - a') + (b - b') = (a + b) - (a' + b')$ , so the sum is well defined. And

ab - a'b' = b(a - a') + a'(b - b'),

in which $m$ divides each summand by the fourth part of the arithmetic of divisibility, hence divides the whole by the corollary on sums; so the product is well defined.

Associativity, commutativity and distributivity for the classes follow from the same laws in $\mathbb{Z}$ applied to representatives; $[0]$ is an additive identity with $-[a] = [-a]$ , and $[1]$ is a multiplicative identity. When $m \geqslant 2$ the classes $[0], \ldots, [m-1]$ are distinct and exhaust the quotient by the previous proposition, so there are $m$ of them and $[0] \neq [1]$ .

Theorem 10.72 (A prime modulus gives a field).

Let $m \geqslant 2$ . Then $\mathbb{Z}/m\mathbb{Z}$ is a field if and only if $m$ is prime. When $m = p$ is prime one writes $\mathbb{F}_p$ for it, a field with exactly $p$ elements.

Discussion.

A biconditional, and the two directions use opposite features of $m$ . Suppose $m$ is composite, say $m = m_1m_2$ with both factors strictly between $1$ and $m$ . Then $[m_1]$ and $[m_2]$ are non-zero while their product is $[m] = [0]$ , so the ring has zero divisors; and a zero divisor can never be invertible, since multiplying $[m_1][m_2] = [0]$ by a hypothetical inverse of $[m_1]$ would give $[m_2] = [0]$ . So no composite modulus works.

Suppose instead $m = p$ is prime and $[a] \neq [0]$ , that is $p \nmid a$ . The positive divisors of $p$ are $1$ and $p$ , and $p$ is not among the common divisors of $a$ and $p$ , so $\gcd(a, p) = 1$ . Bézout then writes $1 = ax + py$ , and reading that equation modulo $p$ leaves $[a][x] = [1]$ . Every non-zero class is therefore invertible, which with the previous theorem is the definition of a field.

Proof.

Suppose $m$ is not prime, so $m = m_1m_2$ with $1 < m_1, m_2 < m$ . Then $[m_1] \neq [0]$ and $[m_2] \neq [0]$ , since $m$ divides neither factor, while $[m_1][m_2] = [m] = [0]$ . If $[m_1]$ had an inverse $[c]$ then $[m_2] = [c][m_1][m_2] = [c][0] = [0]$ , a contradiction. So $\mathbb{Z}/m\mathbb{Z}$ is not a field.

Suppose $m = p$ is prime and let $[a] \neq [0]$ , so $p \nmid a$ . Any positive common divisor of $a$ and $p$ divides $p$ , hence is $1$ or $p$ ; it is not $p$ , since $p \nmid a$ . So $\gcd(a, p) = 1$ , and Bézout gives $x, y \in \mathbb{Z}$ with $ax + py = 1$ . Then $ax - 1 = p(-y)$ , so $[a][x] = [ax] = [1]$ and $[a]$ is invertible. With the previous theorem, $\mathbb{Z}/p\mathbb{Z}$ is a field, and it has $p$ elements.

Remark.

Taking $p = 2$ recovers $\mathbb{F}_2$ , whose tables were forced by the axioms a few pages ago; now it comes from the construction, which gives one field for every prime. These are not all the finite fields (there is one with $p^n$ elements for each prime $p$ and each $n \in \mathbb{N}$ ), but the others are not quotients of $\mathbb{Z}$ , and we do not build them here.

Problem 10.29.

Show that $[a] \in \mathbb{Z}/m\mathbb{Z}$ is invertible if and only if $\gcd(a, m) = 1$ , and that the invertible classes form an abelian group under multiplication.

Problem 10.30.

Write out the addition and multiplication tables of $\mathbb{Z}/m\mathbb{Z}$ for $m = 4$ and $m = 5$ , and say which classes are invertible in each.

Problem 10.31.

Show that a subset $R_0$ of a ring $R$ is itself a ring under the restricted operations if and only if it is non-empty and $a - b$ and $ab$ lie in $R_0$ whenever $a$ and $b$ do. Show that $2\mathbb{Z}$ is such a subset of $\mathbb{Z}$ but does not contain the identity of $\mathbb{Z}$ .

Problem 10.32.

Show that freedom from zero divisors is equivalent, in a commutative ring with identity, to cancellation: $ab = ac$ with $a \neq 0$ forces $b = c$ . Which of the two conditions was easier to check for $\mathbb{Z}$ ?

Subrings, Homomorphisms and Ideals

The chapter on groups asked, of every structure it defined, which subsets inherit it and which maps respect it. We ask the same two questions of rings. The answers are parallel, except that the kernel of a ring homomorphism has a strictly stronger property than a subring.

Definition 10.73 (Subring).

Let $R$ be a ring. A non-empty subset $R_0 \subset R$ is a subring if $a - b \in R_0$ and $ab \in R_0$ whenever $a, b \in R_0$ .

The two conditions say exactly that $R_0$ is a subgroup of $(R, +)$ , by the one-step criterion, and is closed under multiplication; associativity and distributivity are laws and so are inherited. Freedom from zero divisors is inherited too, being another law. What is not inherited is the identity: $2\mathbb{Z}$ is a subring of $\mathbb{Z}$ containing no multiplicative identity of $\mathbb{Z}$ , and a subring of a ring with identity may lack one.

Definition 10.74 (Ring homomorphism).

Let $R_1$ and $R_2$ be rings. A function $\alpha : R_1 \to R_2$ is a ring homomorphism if

\alpha(a + b) = \alpha(a) + \alpha(b) \qquad \text{and} \qquad \alpha(ab) = \alpha(a)\alpha(b)

for all $a, b \in R_1$ . A bijective ring homomorphism is a ring isomorphism. The kernel is $\ker\alpha \defeq \alpha^{-1}(\{0\})$ and the image is $\alpha(R_1)$ .

Proposition 10.75 (Kernel and image of a ring homomorphism).

Let $\alpha : R_1 \to R_2$ be a ring homomorphism. Then $\ker\alpha$ is a subring of $R_1$ and $\alpha(R_1)$ is a subring of $R_2$ ; and $\alpha$ is injective if and only if $\ker\alpha = \{0\}$ .

Discussion.

A ring homomorphism is in particular a homomorphism of the additive groups, so everything proved about kernels and images in the chapter on groups is available and settles the additive half of each claim, injectivity included. What remains is closure under multiplication, one line on each side: a product of two elements of the kernel maps to a product of zeros, and a product of two values is the value at a product. Nothing here needs the identity, and neither the kernel nor the image need contain one.

Proof.

Since $\alpha$ is a homomorphism of $(R_1, +)$ into $(R_2, +)$ , the proposition on kernels and images makes $\ker\alpha$ a subgroup of $(R_1, +)$ and $\alpha(R_1)$ a subgroup of $(R_2, +)$ , and makes $\alpha$ injective exactly when $\ker\alpha = \{0\}$ .

If $a, b \in \ker\alpha$ then $\alpha(ab) = \alpha(a)\alpha(b) = 0 \cdot 0 = 0$ , so $ab \in \ker\alpha$ . And $\alpha(a)\alpha(b) = \alpha(ab) \in \alpha(R_1)$ . So both are closed under multiplication and hence are subrings.

Remark (Neither identities nor freedom from zero divisors survive).

The image of a ring with identity need not contain the identity of the target, and the image of an integral domain need not be free of zero divisors: the map $\mathbb{Z} \to \mathbb{Z}/m\mathbb{Z}$ sending $a$ to $[a]$ is a ring homomorphism, and for composite $m$ its image is the whole of a ring with zero divisors. The kernel contains the identity only in one case: if $1 \in \ker\alpha$ then $\alpha(a) = \alpha(a \cdot 1) = \alpha(a) \cdot 0 = 0$ for every $a$ , so $\alpha$ is the zero map.

The kernel has a further property, the analogue of normality.

Proposition 10.76 (Kernels absorb multiplication).

Let $\alpha : R_1 \to R_2$ be a ring homomorphism, let $a \in \ker\alpha$ and let $b \in R_1$ . Then $ab \in \ker\alpha$ and $ba \in \ker\alpha$ .

Discussion.

A subring need only be closed under products of its own elements, but the kernel contains the product of any of its elements with anything at all, and the reason is the one-line computation that $\alpha$ sends $ab$ to $\alpha(a)\alpha(b) = 0 \cdot \alpha(b)$ , which is $0$ by the arithmetic of a ring. This property is strictly stronger, and like normality for subgroups it gets its own name.

Proof.

$\alpha(ab) = \alpha(a)\alpha(b) = 0 \cdot \alpha(b) = 0$ , so $ab \in \ker\alpha$ ; and $\alpha(ba) = \alpha(b) \cdot 0 = 0$ , so $ba \in \ker\alpha$ .

Definition 10.77 (Ideal).

Let $R$ be a commutative ring. A non-empty subset $\mathfrak{a} \subset R$ is an ideal if

$a_1 - a_2 \in \mathfrak{a}$ whenever $a_1, a_2 \in \mathfrak{a}$ ;
$ba \in \mathfrak{a}$ whenever $a \in \mathfrak{a}$ and $b \in R$ .

An ideal other than $\{0\}$ and $R$ is proper. For $a \in R$ the set $Ra \defeq \{ba \mid b \in R\}$ is the principal ideal generated by $a$ , written $(a)$ ; more generally $(a_1, \ldots, a_n) \defeq \{b_1a_1 + \cdots + b_na_n \mid b_i \in R\}$ .

The second clause makes the first look weak, and in a ring with identity it is: from $a \in \mathfrak{a}$ one gets $-a = (-1)a \in \mathfrak{a}$ , so closure under subtraction follows from closure under addition. Every ideal is a subring, and the kernel of every ring homomorphism is an ideal by the proposition above. The converse, that every ideal is a kernel, is proved below.

Example 10.78 (Ideals of the integers).

For $m \in \mathbb{N}$ the set $m\mathbb{Z}$ of multiples of $m$ is an ideal of $\mathbb{Z}$ , and it is the principal ideal $(m)$ . It is the kernel of $a \mapsto [a]$ , and congruence modulo $m$ is exactly the relation $a - b \in m\mathbb{Z}$ , so the general quotient construction below, applied to this ideal, reproduces the ring $\mathbb{Z}/m\mathbb{Z}$ built by hand earlier, which explains the notation. Bézout’s identity says more: $(a, b) = (\gcd(a,b))$ , so every ideal generated by finitely many integers is principal.

Theorem 10.79 (The quotient ring).

Let $R$ be a commutative ring and $\mathfrak{a}$ an ideal. Then $a \equiv b$ meaning $a - b \in \mathfrak{a}$ is an equivalence relation, and the operations

[a] + [b] \defeq [a + b], \qquad [a] \cdot [b] \defeq [ab]

are well defined on the quotient $R/\mathfrak{a}$ , making it a commutative ring. The map $q : R \to R/\mathfrak{a}$ sending $a$ to $[a]$ is a surjective ring homomorphism with $\ker q = \mathfrak{a}$ .

Discussion.

That the relation is an equivalence is the first clause of the definition, which makes $\mathfrak{a}$ a subgroup of $(R,+)$ : reflexivity is $0 \in \mathfrak{a}$ , symmetry is closure under negation, transitivity is closure under addition.

Well-definedness of the sum is the additive statement already proved for quotient groups, an abelian group having every subgroup normal. Well-definedness of the product uses the second clause of the definition: $ab - a'b'$ does not obviously lie in $\mathfrak{a}$ , so we insert and remove $a'b$ , splitting the difference into $b(a - a')$ and $a'(b - b')$ , each of which is a ring element times a member of $\mathfrak{a}$ , which lies in an ideal but need not lie in a subring. The ring axioms then follow from those of $R$ applied to representatives, and the statement about $q$ is the definition read backwards.

Proof.

The first clause makes $\mathfrak{a}$ a subgroup of the abelian group $(R,+)$ , so $a - b \in \mathfrak{a}$ is an equivalence relation whose classes are the cosets, and the theorem on quotient groups makes $[a] + [b] \defeq [a+b]$ well defined with $(R/\mathfrak{a}, +)$ an abelian group.

For the product, suppose $a - a' \in \mathfrak{a}$ and $b - b' \in \mathfrak{a}$ . Then

ab - a'b' = b(a - a') + a'(b - b'),

and the second clause puts both summands in $\mathfrak{a}$ , so their sum lies there and $[ab] = [a'b']$ .

Associativity, commutativity and distributivity for classes are the corresponding laws in $R$ applied to representatives. Finally $q(a + b) = [a+b] = q(a) + q(b)$ and $q(ab) = [ab] = q(a)q(b)$ , so $q$ is a ring homomorphism; it is surjective by construction; and $q(a) = [0]$ holds exactly when $a \in \mathfrak{a}$ .

Theorem 10.80 (First isomorphism theorem for rings).

Let $\alpha : R_1 \to R_2$ be a homomorphism of commutative rings. Then

R_1/\ker\alpha \;\cong\; \alpha(R_1),

by the ring isomorphism sending $[a]$ to $\alpha(a)$ .

Discussion.

Both sides exist already: the quotient because kernels are ideals, the image because it is a subring. So the work is in the named map, and it is the group version with one clause added. Well-definedness, additivity, surjectivity onto the image and injectivity are exactly as they were there, since $\alpha$ is in particular a homomorphism of additive groups. The one new thing to check is that the map respects multiplication, and that is the definition of the quotient product followed by the multiplicativity of $\alpha$ .

Proof.

Write $\mathfrak{k} \defeq \ker\alpha$ , an ideal by the proposition on kernels, and define $\beta([a]) \defeq \alpha(a)$ .

Everything about the additive structure — that $\beta$ is well defined, additive, surjective onto $\alpha(R_1)$ and injective — is the first isomorphism theorem for groups applied to $\alpha$ as a homomorphism of $(R_1,+)$ into $(R_2,+)$ .

For multiplication, $\beta([a][b]) = \beta([ab]) = \alpha(ab) = \alpha(a)\alpha(b) = \beta([a])\beta([b])$ . So $\beta$ is a bijective ring homomorphism onto $\alpha(R_1)$ .

Remark (Fields have no proper ideals).

If $\mathbb{K}$ is a field and $\mathfrak{a}$ an ideal containing some $a \neq 0$ , then $1 = a^{-1}a \in \mathfrak{a}$ , and then $b = b \cdot 1 \in \mathfrak{a}$ for every $b$ , so $\mathfrak{a} = \mathbb{K}$ . A field therefore has only the two trivial ideals, and consequently a ring homomorphism between fields is either the zero map or injective: its kernel, being an ideal not containing $1$ unless it is everything, must be $\{0\}$ .

Problem 10.33.

Show that an intersection of ideals of $R$ is an ideal, and that $(a_1, \ldots, a_n)$ is the smallest ideal containing $a_1, \ldots, a_n$ .

Problem 10.34.

Show that $a \mid b$ in a commutative ring with identity if and only if $(b) \subset (a)$ , that $u$ is a unit if and only if $(u) = R$ , and that $d$ is a greatest common divisor of $a$ and $b$ exactly when $(a, b) = (d)$ .

Problem 10.35.

Show that every ideal of $\mathbb{Z}$ is principal. Use well-ordering on the positive members, as in the proof of Bézout’s identity.

Polynomials

A polynomial is usually written as an expression, and an expression is not an object. We do what we did for ordered pairs and for the integers: say what the object is, in terms of things already built, and then recover the familiar notation as a theorem.

Definition 10.81 (Polynomials and formal power series).

Let $R$ be a commutative ring with identity. A formal power series over $R$ is a sequence $\alpha : \mathbb{N}_0 \to R$ , written $\alpha = (a_0, a_1, a_2, \ldots)$ with $a_n \defeq \alpha(n)$ . It is a polynomial if $a_n = 0$ for all but finitely many $n$ . Define

(\alpha + \beta)_n \defeq a_n + b_n, \qquad (\alpha\beta)_n \defeq \sum_{j = 0}^{n} a_j b_{n-j} .

Write $R[x]$ for the set of polynomials and $R[[x]]$ for the set of all formal power series, with these operations. The degree $\deg\alpha$ of a non-zero polynomial $\alpha$ is the largest index carrying a non-zero coefficient.

The product is the rule one would get by multiplying out two expressions and collecting the terms of each degree; here it is a definition, and the sum defining it is a finite sum over an interval, so it names an element of $R$ without any question of convergence. “Formal” means that the series is a sequence of coefficients and nothing more.

Theorem 10.82 (Polynomials form a ring).

Let $R$ be a commutative ring with identity. Then $R[[x]]$ is a commutative ring with identity under the operations above, and $R[x]$ is a subring containing that identity. The map sending $r \in R$ to $(r, 0, 0, \ldots)$ is an injective ring homomorphism, and writing $x \defeq (0, 1, 0, 0, \ldots)$ gives

x^n = (\underbrace{0, \ldots, 0}_{n}, 1, 0, \ldots), \qquad \alpha = \sum_{j=0}^{n} a_j x^j \quad \text{for every polynomial } \alpha \text{ with } a_j = 0 \text{ beyond } n .

Discussion.

Addition is coordinatewise, so the additive group is immediate. Commutativity of the product is the observation that reversing the order of summation in $\sum_j a_j b_{n-j}$ turns it into $\sum_j b_j a_{n-j}$ , which is reindexing a finite sum. Associativity is the corresponding statement for a double sum: both $(\alpha\beta)\gamma$ and $\alpha(\beta\gamma)$ have $n$ -th coefficient the sum of $a_ib_jc_k$ over all triples with $i + j + k = n$ , so the two agree once the sums are rearranged, which the results on unordered index sets allow. Distributivity is coordinatewise. That $R[x]$ is a subring is the observation that a sum or product of two sequences with finitely many non-zero terms has finitely many non-zero terms; for the product, because the $n$ -th coefficient vanishes once $n$ exceeds the sum of the two cut-offs. The claims about $x$ are a computation from the product rule, and the last display is then bookkeeping.

Proof.

Addition is coordinatewise, so $(R[[x]], +)$ is an abelian group with zero $(0,0,\ldots)$ and $(-\alpha)_n = -a_n$ .

For commutativity of the product, the substitution $j \mapsto n - j$ is a bijection of $\{0, \ldots, n\}$ with itself, so reindexing gives $\sum_{j=0}^{n} a_jb_{n-j} = \sum_{j=0}^{n} b_j a_{n-j}$ .

For associativity, both $\bigl((\alpha\beta)\gamma\bigr)_n$ and $\bigl(\alpha(\beta\gamma)\bigr)_n$ equal the sum of $a_ib_jc_k$ over the finitely many triples $(i,j,k)$ in $\mathbb{N}_0$ with $i + j + k = n$ , by splitting each double sum and reindexing. Distributivity is coordinatewise, since the $n$ -th coefficient of $\alpha(\beta + \gamma)$ is $\sum_j a_j(b_{n-j} + c_{n-j})$ .

The element $(1, 0, 0, \ldots)$ is an identity, since its only non-zero coefficient is at $0$ and the product sum collapses to $a_n \cdot 1$ .

If $a_n = 0$ for $n > N$ and $b_n = 0$ for $n > M$ , then every term of $\sum_j a_jb_{n-j}$ vanishes once $n > N + M$ , so $R[x]$ is closed under products; it is clearly closed under differences. So $R[x]$ is a subring, and it contains $(1,0,\ldots)$ .

Finally $x^n$ has $1$ in position $n$ and $0$ elsewhere, by induction on $n$ from the product rule, so $a_jx^j$ has $a_j$ in position $j$ and $0$ elsewhere, and adding those for $j \leqslant n$ reproduces $\alpha$ .

Proposition 10.83 (Degree and zero divisors).

Let $R$ be an integral domain and let $\alpha, \beta \in R[x]$ be non-zero, of degrees $\deg\alpha$ and $\deg\beta$ . Then $\alpha\beta \neq 0$ and $\deg(\alpha\beta) = \deg\alpha + \deg\beta$ . Hence $R[x]$ is an integral domain, and it is never a field.

Discussion.

We look at the top coefficient. Writing $N$ and $M$ for the two degrees, the coefficient of $\alpha\beta$ at $N + M$ is a sum in which every term but one has a factor above the cut-off of $\alpha$ or of $\beta$ , hence vanishes; the remaining term is the product of the two leading coefficients, which is non-zero because $R$ has no zero divisors. So the product is non-zero and its degree is exactly $N + M$ . The last claim follows: $x$ has degree $1$ , so any $\gamma$ with $x\gamma = 1$ would have $1 + \deg\gamma = \deg 1 = 0$ , which the order on $\mathbb{N}_0$ forbids.

Proof.

Put $N \defeq \deg\alpha$ and $M \defeq \deg\beta$ . The coefficient of $\alpha\beta$ at $N + M$ is $\sum_{j} a_j b_{N+M-j}$ ; a term with $j > N$ has $a_j = 0$ , and a term with $j < N$ has $N + M - j > M$ and so $b_{N+M-j} = 0$ . Only $j = N$ survives, giving $a_N b_M$ , which is non-zero because $R$ has no zero divisors. Coefficients above $N + M$ vanish by the same count. So $\alpha\beta \neq 0$ with degree $N + M$ , and $R[x]$ is an integral domain.

If $x\gamma = 1$ for some $\gamma \neq 0$ , then $1 + \deg\gamma = 0$ , impossible in $\mathbb{N}_0$ . So $x$ is not invertible and $R[x]$ is not a field.

Problem 10.36.

Show that $\alpha \in R[[x]]$ is a unit if and only if $a_0$ is a unit in $R$ , by solving for the coefficients of the inverse one at a time. Deduce that $1 - x$ is invertible in $R[[x]]$ and identify its inverse.

Problem 10.37.

Show that evaluation at $r \in R$ , sending $\sum_j a_j x^j$ to $\sum_j a_j r^j$ , is a ring homomorphism $R[x] \to R$ . Show that its kernel is an ideal containing $x - r$ .

Problem 10.38.

Show that $\mathbb{F}_2[x]$ is infinite while the set of functions $\mathbb{F}_2 \to \mathbb{F}_2$ is finite, and conclude that distinct polynomials may define the same function. Give two such polynomials.

Modules and Vector Spaces

The last definition of the chapter describes a ring acting on an abelian group, where the group need not be a ring itself.

Definition 10.84 (Module and vector space).

Let $R$ be a commutative ring with identity. An $R$ -module is an abelian group $(M, +)$ together with a map $R \times M \to M$ , written $(c, v) \mapsto cv$ , such that for all $c, c' \in R$ and $v, v' \in M$

(c + c')v = cv + c'v, \qquad c(v + v') = cv + cv', \qquad (cc')v = c(c'v), \qquad 1v = v .

When $R$ is a field $\mathbb{K}$ , an $R$ -module is called a $\mathbb{K}$ -vector space, and its elements vectors.

Example 10.85 (Modules already met).

Every ring $R$ is a module over itself, with $cv$ the ring product; every ideal of $R$ is a submodule. Every abelian group is a $\mathbb{Z}$ -module, with $nv$ the $n$ -fold sum, which is exactly the map $\iota$ construction read with $v$ in place of $1$ . For a field $\mathbb{K}$ and a set $X$ , the functions $X \to \mathbb{K}$ form a $\mathbb{K}$ -vector space under pointwise operations, and taking $X = \langle n \rangle$ gives the space $\mathbb{K}^n$ of $n$ -tuples with coordinatewise addition and scaling. And $R[x]$ is an $R$ -module, the scalars acting on the coefficients.

Remark (Where this goes).

A ring that is also a $\mathbb{K}$ -vector space, with the two structures compatible, is a $\mathbb{K}$ -algebra; the linear maps of a vector space to itself form one under composition, and choosing a basis identifies it with a ring of matrices. That is linear algebra, and we stop at the definition. Every structure in these chapters (semigroup, group, ring, field, module) was built from the same two things, a set and a function.

Problem 10.39.

Show that $0v = 0$ and $(-c)v = -(cv)$ in any $R$ -module, quoting the corresponding argument for rings.

Problem 10.40.

Show that an abelian group admits exactly one structure as a $\mathbb{Z}$ -module. Where does the uniqueness come from?

Exercises

Answers are checked in your browser, as often as you like. Nothing is sent anywhere and nothing is kept but your own work. A formula may be written with the symbols themselves or with ~ & | -> <-> ^, and \and, \or, \to expand as you type.

Exercises in Lean

The proofs below are checked in your browser. Nothing is sent anywhere, and nothing is stored but your own work. Type \to for →, \and for ∧, \< and \> for ⟨ ⟩.

An integer of this chapter is a class of pairs of natural numbers, and the sum criterion that decides when two pairs name the same integer mentions nothing but addition on $\mathbb{N}_0$ . So the whole construction can be checked in the carrier the pairs are drawn from, and the sheet is written there: a pair is two naturals $m$ and $n$ , and $(m, n) \sim (m', n')$ is the equation

m + n' = n + m'

with no new notation needed for it. What the chapter proves about $\sim$ becomes an implication between such equations, which is what the exercises ask for.

Two laws of multiplication join the arithmetic already listed, both from the problems of the chapter on the natural numbers:

Nat.mul_assoc   (m * n) * p = m * (n * p)
Nat.add_mul     (m + n) * p = m * p + n * p

and divisibility arrives as the definition the order chapter gave it, written a ∣ b and typed \mid:

Nat.dvd_iff     a ∣ b ↔ ∃ c : ℕ, b = a * c

It is an equivalence rather than a definition the checker unfolds, so it is used through .mp and .mpr.

Rearranging a sum

Every calculation with pairs ends the same way: four naturals added in one order must be shown equal to the same four added in another order. We prove this once.

Example.

Associativity opens the bracketing, commutativity exchanges the middle pair, and associativity closes it again. It is listed below as Nat.add_shuffle.

Example.

Symmetry of $\sim$ , which is the sum criterion read backwards with each side commuted.

Exercise 10.12.

The exchange that Proposition 10.5 turns on.

Exercise 10.13.

A common shift satisfies the sum criterion, which is the third condition of Theorem 10.8 implying the second.

Exercise 10.14.

Transitivity, and with it Proposition 10.2 . Adding $n''$ to the first equation is what makes the second substitutable, and cancellation clears what is left.

Exercise 10.15.

Proposition 10.15 : pre-addition respects the equivalence. This is what Nat.add_shuffle is for.

Exercise 10.16.

Every number divides itself.

Exercise 10.17.

The first part of Proposition 10.54 , on the carrier.

Exercise 10.18.

And Corollary 10.55 , whose subtraction half has no reading in $\mathbb{N}_0$ .

Exercise 10.19.

A divisibility survives multiplying both sides by the same factor.

Exercise 10.20.

The third part of Proposition 10.54 , in the form $\mathbb{N}_0$ can state. (Harder.)

What the checker understands

Tactics

intro h	assume the hypothesis of an implication, naming it h
exact e	give the proof outright
apply f	reduce the goal to the hypotheses of f
assumption	close the goal with a hypothesis already present
trivial	close the goal True
exfalso	replace the goal with False
by_contra h	assume the negation of the goal
constructor	split ∧ into both halves, or ↔ into both directions
left / right	choose which half of a ∨ to prove
rcases h with a \| b	argue by cases on a disjunction
obtain ⟨a, b⟩ := h	take a conjunction or an existential apart
cases h	as above, keeping the name
refine e	give the proof with holes left in it
have h : p := …	record an intermediate result
show p	restate the goal in an equal form
use w	give a witness for ∃
specialize h a	instantiate a ∀ hypothesis
rw [h]	rewrite with an equation, ← to go backwards
rfl	both sides compute to the same thing
decide / norm_num	settle a closed computation
tauto	close a goal that is true by pure logic
induction n with k ih	the fifth Peano condition: prove the goal at 0, then at succ k from ih

Results you may cite

Classical.em	∀ (a : Prop), a ∨ ¬a — the law of excluded middle
Classical.byContradiction	∀ {a : Prop}, (¬a → False) → a — proof by contradiction; the tactic by_contra does this for you
Classical.byCases	∀ {a b : Prop}, (a → b) → (¬a → b) → b — split on whether a holds
not_not	∀ {a : Prop}, ¬¬a ↔ a — double negation
not_and_or	∀ {a b : Prop}, ¬(a ∧ b) ↔ ¬a ∨ ¬b — De Morgan
not_or	∀ {a b : Prop}, ¬(a ∨ b) ↔ ¬a ∧ ¬b — De Morgan
not_imp	∀ {a b : Prop}, ¬(a → b) ↔ a ∧ ¬b
and_comm	∀ {a b : Prop}, a ∧ b ↔ b ∧ a
or_comm	∀ {a b : Prop}, a ∨ b ↔ b ∨ a
Set.ext	∀ {A B : Obj}, (∀ x : Obj, x ∈ A ↔ x ∈ B) → A = B — extensionality: sets with the same elements are equal
Set.ext_iff	∀ {A B : Obj}, A = B ↔ (∀ x : Obj, x ∈ A ↔ x ∈ B) — extensionality and substitution, in one biconditional
Set.subset_antisymm	∀ {A B : Obj}, A ⊆ B → B ⊆ A → A = B — mutual inclusion is equality
Set.empty_subset	∀ {A : Obj}, ∅ ⊆ A — the empty set is a subset of every set
Set.pair_eq	∀ {a b c d : Obj}, ((a, b) = (c, d)) ↔ (a = c ∧ b = d) — two ordered pairs are equal exactly when their coordinates are
Nat.succ_inj	∀ {m n : ℕ}, succ m = succ n → m = n — the third Peano condition: the successor is injective
Nat.succ_ne_zero	∀ (n : ℕ), succ n ≠ 0 — the fourth: zero is nobody's successor
Nat.pred	∀ {n : ℕ}, n ≠ 0 → ∃ m : ℕ, n = succ m — predecessors: everything but zero is a successor
Nat.add_zero	∀ (m : ℕ), m + 0 = m — the first clause of addition
Nat.add_succ	∀ (m n : ℕ), m + succ n = succ (m + n) — the second clause of addition
Nat.zero_add	∀ (n : ℕ), 0 + n = n — addition from the left
Nat.succ_add	∀ (m n : ℕ), succ m + n = succ (m + n) — addition from the left, at a successor
Nat.add_assoc	∀ (m n p : ℕ), (m + n) + p = m + (n + p) — addition is associative
Nat.add_comm	∀ (m n : ℕ), m + n = n + m — addition is commutative
Nat.add_ne_zero	∀ {a : ℕ} (b : ℕ), a ≠ 0 → a + b ≠ 0 — positivity is absorbing
Nat.mul_zero	∀ (m : ℕ), m * 0 = 0 — the first clause of multiplication
Nat.mul_succ	∀ (m n : ℕ), m * succ n = m * n + m — the second clause of multiplication
Nat.zero_mul	∀ (m : ℕ), 0 * m = 0 — multiplication from the left
Nat.succ_mul	∀ (m n : ℕ), succ m * n = m * n + n — multiplication from the left, at a successor
Nat.add_right_cancel	∀ {m n k : ℕ}, m + k = n + k → m = n — cancellation, from the last sheet
Nat.add_eq_zero	∀ {m n : ℕ}, m + n = 0 → m = 0 ∧ n = 0 — a sum is zero only when both parts are, from the last sheet
Nat.mul_comm	∀ (m n : ℕ), m * n = n * m — multiplication is commutative, from the last sheet
Nat.mul_add	∀ (m n p : ℕ), m * (n + p) = m * n + m * p — multiplication distributes over addition, from the last sheet
Nat.mul_assoc	∀ (m n p : ℕ), (m * n) * p = m * (n * p) — multiplication associates, from the problems of the last chapter
Nat.add_mul	∀ (m n p : ℕ), (m + n) * p = m * p + n * p — distributivity on the other side
Nat.add_left_cancel	∀ {a m n : ℕ}, a + m = a + n → m = n — uniqueness of differences
Nat.lt_trichotomy	∀ (m n : ℕ), m < n ∨ m = n ∨ n < m — trichotomy, from the theorem that ℕ is strictly ordered
Nat.lt_irrefl	∀ (n : ℕ), ¬(n < n) — anti-reflexivity, from the last sheet
Nat.lt_trans	∀ {m n p : ℕ}, m < n → n < p → m < p — transitivity of the strict order, from the last sheet
Nat.lt_succ_self	∀ (n : ℕ), n < succ n — every number is below its successor, from the last sheet
Nat.not_lt_zero	∀ {n : ℕ}, ¬(n < 0) — nothing lies below zero
Nat.lt_succ_iff	∀ {m n : ℕ}, m < succ n ↔ m < n ∨ m = n — nothing lies strictly between n and succ n
Num.inj	∀ {m n : ℕ}, ↑m = ↑n → m = n — distinct numbers name distinct objects of ω
swap_apply_left	∀ (a b : Obj), swap a b a = b — the transposition sends a to b
swap_apply_right	∀ (a b : Obj), swap a b b = a — and b to a
swap_apply_of_ne_of_ne	∀ {a b x : Obj}, x ≠ a → x ≠ b → swap a b x = x — and fixes every other point
swap_swap	∀ (a b x : Obj), swap a b (swap a b x) = x — a transposition is its own inverse
Function.iterate_zero_apply	∀ (f : Obj → Obj) (x : Obj), f^[0] x = x — the first clause of the powers of a map
Function.iterate_succ_apply	∀ (f : Obj → Obj) (n : ℕ) (x : Obj), f^[succ n] x = f^[n] (f x) — the second clause: f^[succ n] is f^[n] ∘ f
Function.iterate_add_apply	∀ (f : Obj → Obj) (m n : ℕ) (x : Obj), f^[m + n] x = f^[m] (f^[n] x) — the first law of exponents
Nat.factorial_zero	0 ! = succ 0 — the first clause of the factorial
Nat.factorial_succ	∀ (n : ℕ), (succ n) ! = succ n * n ! — the second clause of the factorial
Nat.choose_zero_right	∀ (n : ℕ), choose n 0 = succ 0 — the empty set is the one 0-subset
Nat.choose_eq_zero_of_lt	∀ {n k : ℕ}, n < k → choose n k = 0 — no subset is larger than the whole
Nat.choose_succ_succ	∀ (n k : ℕ), choose (succ n) (succ k) = choose n k + choose n (succ k) — Pascal's identity
mul_assoc	∀ (a b c : Obj), (a ∗ b) ∗ c = a ∗ (b ∗ c) — the operation associates
e_mul	∀ (a : Obj), e ∗ a = a — the identity on the left
mul_e	∀ (a : Obj), a ∗ e = a — and on the right
inv_mul_cancel	∀ (a : Obj), a⁻¹ ∗ a = e — the inverse on the left
mul_inv_cancel	∀ (a : Obj), a ∗ a⁻¹ = e — and on the right
inv_inv	∀ (a : Obj), (a⁻¹)⁻¹ = a — worked above: inverting twice gives the element back
mul_left_cancel	∀ {a x y : Obj}, a ∗ x = a ∗ y → x = y — worked above: the left half of prop-9-5
Nat.add_shuffle	∀ (p q r s : ℕ), (p + q) + (r + s) = (p + r) + (q + s) — worked above: the rearrangement every pair calculation needs
Nat.dvd_iff	∀ {a b : ℕ}, a ∣ b ↔ ∃ c : ℕ, b = a * c — a divides b when b is a multiple of it

From the logical core

And.intro	∀ {a b : Prop}, a → b → a ∧ b
And.left	∀ {a b : Prop}, a ∧ b → a
And.right	∀ {a b : Prop}, a ∧ b → b
And.symm	∀ {a b : Prop}, a ∧ b → b ∧ a
Or.inl	∀ {a b : Prop}, a → a ∨ b
Or.inr	∀ {a b : Prop}, b → a ∨ b
Or.elim	∀ {a b c : Prop}, a ∨ b → (a → c) → (b → c) → c
Or.symm	∀ {a b : Prop}, a ∨ b → b ∨ a
Iff.intro	∀ {a b : Prop}, (a → b) → (b → a) → (a ↔ b)
Iff.mp	∀ {a b : Prop}, (a ↔ b) → a → b
Iff.mpr	∀ {a b : Prop}, (a ↔ b) → b → a
Iff.symm	∀ {a b : Prop}, (a ↔ b) → (b ↔ a)
Iff.rfl	∀ {a : Prop}, a ↔ a
Iff.trans	∀ {a b c : Prop}, (a ↔ b) → (b ↔ c) → (a ↔ c)
True.intro	True
False.elim	∀ {a : Prop}, False → a
absurd	∀ {a b : Prop}, a → ¬a → b
id	∀ {a : Prop}, a → a
mt	∀ {a b : Prop}, (a → b) → ¬b → ¬a
Eq.refl	∀ {α : Type} (a : α), a = a
Eq.symm	∀ {α : Type} {a b : α}, a = b → b = a
Eq.trans	∀ {α : Type} {a b c : α}, a = b → b = c → a = c
congrArg	∀ {α : Type} {β : Type} {a b : α} (f : α → β), a = b → f a = f b
Exists.intro	∀ {α : Type} {p : α → Prop} (w : α), p w → ∃ x : α, p x
Exists.elim	∀ {α : Type} {p : α → Prop} {b : Prop}, (∃ x : α, p x) → (∀ y : α, p y → b) → b

Formal Differences

Pairs and the Sum Criterion

The Net Difference

The Integers

Integers as Classes

Addition and Negation

Multiplication

The Order on the Integers

Sequences, Sums and Products

Indexing by an Integer Interval

Sums over an Interval

Products over an Interval

Sums over an Unordered Index Set

Divisibility

Divisors

Division with Remainder

Rings and Fields

The Construction Was Not Special

Rings, Integral Domains and Fields

Greatest Common Divisors

The Integers Modulo mmm

Subrings, Homomorphisms and Ideals

Polynomials

Modules and Vector Spaces

Exercises

Exercises in Lean

Rearranging a sum

The Integers Modulo $m$