2.5 Division with Remainder

Two facts about the integers of school, taken as known, were proved in the previous volume: every integer is even or odd, and not both (Sets and Functions, Section 1.1, Sets and Functions, Theorem 1.1.2), and division with remainder (Sets and Functions, Section 3.2, Sets and Functions, Theorem 3.2.3). The integers are now the set of classes built in Section 2.1. Is $[(0, 7)]$ , the class that school calls $-7$ , still odd, and could some integer be even and odd at once? Nothing proved so far says. This section answers by proving division with remainder again, on the constructed $\mathbb{Z}$ : the proof is that of Sets and Functions, Section 3.2, with each school fact replaced by a result of this chapter. Divisibility comes first, since uniqueness of the remainder rests on it.

Throughout, $\mathbb{Z}$ is the ordered ring of Theorem 2.4.2, with $\mathbb{N} \subseteq \mathbb{Z}$ and $\mathbb{Z}_{>0} = \{ n \in \mathbb{Z} : n > 0 \}$ (Theorem 2.4.2 (b)), and $a - b \mathrel{:=} a + (-b)$ . Numerals $2 \mathrel{:=} 1 + 1$ , $3 \mathrel{:=} 2 + 1$ , and so on, are the natural numbers of those names, as in Section 2.2; a sum or product of numerals may be computed in $\mathbb{N}$ , because the embedding of Proposition 2.2.3 preserves $+$ and $\cdot$ , and a sign is moved by Proposition 2.3.2 (c), as in $(-4) \cdot 5 = -(4 \cdot 5) = -20$ .

2.5.1. Divisibility on the constructed integers

The definition of divisibility needs nothing that the ring $\mathbb{Z}$ lacks. We restate it, and the definition of a prime, from Sets and Functions, Section 1.1, with $\mathbb{Z}$ now the ring of Chapter 2.

Divisibility (Sets and Functions, Definition 1.1.2). Let $a, b \in \mathbb{Z}$ . Then $a$ divides $b$ , written $a \mid b$ , if there exists $k \in \mathbb{Z}$ with $b = ka$ . Then $a$ is a divisor of $b$ , and $b$ is a multiple of $a$ . We write $a \nmid b$ when $a$ does not divide $b$ .

Prime (Sets and Functions, Definition 1.1.3). An integer $p$ is prime if $p \ge 2$ and the only positive divisors of $p$ are $1$ and $p$ . A prime factor of an integer $n$ is a prime $p$ with $p \mid n$ .

Divisibility is a question about existence: is $b$ some integer times $a$ ?

Some instances. $3 \mid -12$ , since $-12 = (-4) \cdot 3$ . $-4 \mid 0$ , since $0 = 0 \cdot (-4)$ . Even $0 \mid 0$ holds, since $0 = 1 \cdot 0$ : the definition asks for some $k$ , and here every $k$ works. On the other hand $5 \nmid 12$ . That is a statement that no $k \in \mathbb{Z}$ has $12 = 5k$ , and to prove it we need the theorem on division with remainder below.

The rules below are short consequences of the ring laws and the order.

Proposition 2.5.1 (Rules for Divisibility in

\mathbb{Z}

)

Let $a, b, c, x, y \in \mathbb{Z}$ .

(a) $a \mid 0$ , $1 \mid a$ and $a \mid a$ . If $0 \mid a$ , then $a = 0$ .
(b) If $a \mid b$ and $b \mid c$ , then $a \mid c$ .
(c) If $a \mid b$ and $a \mid c$ , then $a \mid bx + cy$ .
(d) If $a \mid b$ , then $(-a) \mid b$ and $a \mid (-b)$ .
(e) If $a \mid b$ , $a > 0$ and $b > 0$ , then $a \le b$ .
(f) If $a, b \in \mathbb{N}$ , $a \mid b$ and $b \mid a$ , then $a = b$ .
(g) If $a \mid 1$ , then $a = 1$ or $a = -1$ .
(h) If $a \ne 0$ , then exactly one of $a$ , $-a$ lies in $\mathbb{Z}_{>0}$ .

Idea. Parts (a)–(d) are identities in the commutative ring $\mathbb{Z}$ : write each hypothesis as an equation $b = ka$ and rearrange. Part (e) is the one that needs the order. If $b = ka$ with $a, b > 0$ , the factor $k$ cannot be zero or negative, so by discreteness it is at least $1$ , and multiplying $a$ by something at least $1$ cannot make it smaller (the method of Example (Method: turn the comparison into one positive element)). Parts (f) and (g) then follow from (e), and (h) is (P2) for the positives of $\mathbb{Z}$ .

Proof. We use the ring laws (F1)–(F7) and (F9) of $\mathbb{Z}$ (Theorem 2.3.1) without further mention. Parts (a)–(d) are one-line identities and (h) restates (P2); their proofs are written out in the fold. After it come (e), which needs the order and discreteness, and the two parts built on it, (f) and (g).

Second readingParts (a)–(d) and (h)

(a) $0 = a \cdot 0 = 0 \cdot a$ by Proposition 2.3.2 (b) and (F6), so $a \mid 0$ with $k = 0$ . Also $a = a \cdot 1$ by (F7), so $1 \mid a$ with $k = a$ ; and $a = 1 \cdot a$ , so $a \mid a$ with $k = 1$ . If $0 \mid a$ , then $a = k \cdot 0 = 0$ for some $k \in \mathbb{Z}$ , by Proposition 2.3.2 (b).
(b) Let $b = ka$ and $c = lb$ with $k, l \in \mathbb{Z}$ . Then $c = l(ka) = (lk)a$ by (F5), so $a \mid c$ .
(c) Let $b = ka$ and $c = la$ . Then $bx + cy = (ka)x + (la)y = (kx)a + (ly)a = (kx + ly)a$ by (F5), (F6) and (F9), and $kx + ly \in \mathbb{Z}$ . So $a \mid bx + cy$ .
(d) Let $b = ka$ . By Proposition 2.3.2 (c), $(-k)(-a) = ka = b$ , so $(-a) \mid b$ ; and $(-k)a = -(ka) = -b$ , so $a \mid (-b)$ .
(e) Let $a \ne 0$ . By the converse part of Proposition 2.4.1, applied to the ordered ring $\mathbb{Z}$ , the set $\{ x \in \mathbb{Z} : x > 0 \}$ satisfies (P2), so exactly one of $a > 0$ , $-a > 0$ holds. That set is $\mathbb{Z}_{>0}$ by Theorem 2.4.2 (b).

(e) Let $b = ka$ with $k \in \mathbb{Z}$ , $a > 0$ and $b > 0$ . We show first that $k > 0$ . If $k = 0$ , then $b = 0 \cdot a = 0$ by Proposition 2.3.2 (b), against $b > 0$ . If $k < 0$ , then $ka < 0 \cdot a = 0$ by Proposition 2.4.3 (c) (multiplying $k < 0$ by $a > 0$ ), again against $b > 0$ . So $k > 0$ , and by discreteness (Theorem 2.4.2 (c), with $0 < k$ ) $1 \le k$ . If $k = 1$ , then $b = a$ . If $1 < k$ , then $k - 1 > 0$ by Proposition 2.4.3 (a), so $(k - 1)a > 0 \cdot a = 0$ by Proposition 2.4.3 (c), that is, $b - a = ka + (-1)a = (k - 1)a > 0$ (Proposition 2.3.2 (c), (F7) and (F9)), and $a < b$ by Proposition 2.4.3 (a). In both cases $a \le b$ .
(f) Let $a, b \in \mathbb{N}$ with $a \mid b$ and $b \mid a$ . If $a = 0$ , then $0 \mid b$ , so $b = 0 = a$ by (a). If $b = 0$ , then $a = 0$ in the same way. Otherwise $a, b \in \mathbb{N}$ are non-zero, hence positive (Theorem 2.4.2 (b)), and (e) gives $a \le b$ and $b \le a$ . Since $\le$ is a total order (Proposition 2.4.3 (i)), it is antisymmetric, and $a = b$ .
(g) Let $a \mid 1$ , say $1 = ka$ . Then $a \ne 0$ : otherwise $1 = k \cdot 0 = 0$ , against $1 \ne 0$ in $\mathbb{Z}$ (Theorem 2.3.1). By (h), one of $a$ , $-a$ is positive; call it $e$ . Then $e \mid 1$ , by (d) if $e = -a$ . Since $1 > 0$ (Proposition 2.4.3 (e)), part (e) gives $e \le 1$ ; and $e > 0$ gives $1 \le e$ by discreteness. So $e = 1$ . If $e = a$ , then $a = 1$ ; if $e = -a$ , then $a = -(-a) = -1$ by Proposition 2.3.2 (a). This proves the proposition.

Part (f) is the antisymmetry of divisibility on $\mathbb{N}$ , Sets and Functions, Proposition 5.1.1 of Sets and Functions, Section 5.1, now proved on $\mathbb{N} \subseteq \mathbb{Z}$ for the constructed integers. On all of $\mathbb{Z}$ it fails: $2 \mid -2$ and $-2 \mid 2$ , by (d), yet $2 \ne -2$ .

Quick check. Which hypothesis of (e) fails for $a = 3$ , $b = 0$ , and is the conclusion $a \le b$ true there?

Solution. $3 \mid 0$ by (a), and $a = 3 > 0$ , but $b = 0$ is not positive. The conclusion $3 \le 0$ is false. Every integer divides $0$ , so no bound of the form $a \le b$ can hold for $b = 0$ ; that is the reason for the hypothesis $b > 0$ .

2.5.2. Division with remainder

Now the substitute for division. Given $a \in \mathbb{Z}$ and $n \in \mathbb{Z}_{>0}$ , we want to write $a$ as a multiple of $n$ plus something small, and we want “small” to make the answer unique. The obvious attempt subtracts $n$ from $a$ until what is left lies in $\{0, \dots, n - 1\}$ , adding $n$ instead when $a$ is negative. That is a process; the theorem replaces it by a least element.

Theorem 2.5.2 (Division with Remainder in

\mathbb{Z}

)

Let $a \in \mathbb{Z}$ and $n \in \mathbb{Z}_{>0}$ .

(a) There are unique $q, r \in \mathbb{Z}$ with $a = qn + r \quad \text{and} \quad 0 \le r < n .$

The integers $q$ and $r$ are the quotient and the remainder of $a$ on division by $n$ .

Idea. This is Sets and Functions, Theorem 3.2.3, and the proof is that volume’s: the method of Sets and Functions, Example (Method: the least element), with $S$ the non-negative integers of the form $a - kn$ , and Proposition 2.4.4 in place of the school least-element principle. The least one, $r$ , lies below $n$ , or else $r - n$ would be a smaller one. Uniqueness is Sets and Functions, Example (Method: existence and uniqueness): two remainders differ by a multiple of $n$ and by less than $n$ , and Proposition 2.5.1 (e) forbids a positive multiple of $n$ below $n$ . What is new is only that every step is now a theorem about the constructed $\mathbb{Z}$ .

Proof. Read the proof of Sets and Functions, Theorem 3.2.3 with these replacements:

the closure of $\mathbb{Z}$ under $+$ , $-$ , $\cdot$ (Sets and Functions, Proposition 3.1.2 (a)) → Theorem 2.3.1, with the identities $a - an = a(1 - n)$ and $r - n = a - (q + 1)n$ from the ring laws and Proposition 2.3.2;
“a positive integer is at least $1$ ” (Sets and Functions, Proposition 3.1.2 (b)) → discreteness, Theorem 2.4.2 (c);
Sets and Functions, Corollary 3.1.5 → Proposition 2.4.4;
the step “a positive multiple of $n$ is at least $n$ ” → Proposition 2.5.1 (e);
the school rules for inequalities, and cancelling $n \ne 0$ from $qn = q'n$ → Proposition 2.4.3.

With these, the proof of Sets and Functions, Section 3.2 goes through step for step on the constructed $\mathbb{Z}$ ; the fold below writes it out.

Second readingThe proof, line by line on the constructed ℤ

(a) Existence. Let $R \mathrel{:=} \{ a - kn : k \in \mathbb{Z} \} \cap \{ x \in \mathbb{Z} : x \ge 0 \} .$ We show $R \ne \emptyset$ . If $a \ge 0$ , take $k = 0$ : $a - 0 \cdot n = a - 0 = a \ge 0$ , by (F6), Proposition 2.3.2 (b) and $-0 = 0$ ( $0 + 0 = 0$ and Proposition 2.3.2 (a)). If $a < 0$ , take $k = a$ : then $a - an = a + a(-n) = a(1 - n)$ by Proposition 2.3.2 (c), (F7) and (F9). Since $n > 0$ , discreteness (Theorem 2.4.2 (c)) gives $1 \le n$ . If $n = 1$ , then $a(1 - n) = a \cdot 0 = 0$ by Proposition 2.3.2 (b). If $1 < n$ , then $-n < -1$ by Proposition 2.4.3 (a), so $1 - n < 0$ by (O3); multiplying $a < 0$ by $1 - n < 0$ reverses the inequality (Proposition 2.4.3 (d)), so $a(1 - n) > 0 \cdot (1 - n) = 0$ . In every case $R$ has an element.

The set $R \subseteq \mathbb{Z}$ is non-empty and has the lower bound $0$ , so by Proposition 2.4.4 it has a least element $r$ . Write $r = a - qn$ with $q \in \mathbb{Z}$ . Then $a = qn + r$ and $r \ge 0$ .

Suppose $r \ge n$ . Then $r - n \ge 0$ : if $r = n$ , then $r - n = 0$ by (F4); if $r > n$ , then $r - n > 0$ by Proposition 2.4.3 (a). Also $r - n = a - qn - n = a + (-1)(qn) + (-1)n = a + (-1)\bigl((q + 1)n\bigr) = a - (q + 1)n$ , since $-x = (-1)x$ for every $x$ (Proposition 2.3.2 (c) and (F7)) and by (F9), so $r - n \in R$ . But $-n < -0 = 0$ (Proposition 2.4.3 (a), since $n > 0$ ), so $r - n < r$ by (O3). This contradicts the choice of $r$ as least. Hence $r < n$ .

Uniqueness. Let $a = qn + r = q'n + r'$ with $q, q', r, r' \in \mathbb{Z}$ , $0 \le r < n$ and $0 \le r' < n$ . Suppose $r \ne r'$ . Exchanging $(q, r)$ and $(q', r')$ changes neither the hypotheses nor the goal, so we may suppose $r' < r$ . Adding $-r' - qn$ to both sides of $qn + r = q'n + r'$ gives $r - r' = q'n - qn = (q' - q)n ,$ by (F1)–(F4), and by Proposition 2.3.2 (c) with (F9) for the last step, so $n \mid r - r'$ . Here $r - r' > 0$ by Proposition 2.4.3 (a), and $n > 0$ , so Proposition 2.5.1 (e) gives $n \le r - r'$ . But adding $r - r'$ to $0 \le r'$ gives $r - r' \le (r - r') + r' = r$ (Proposition 2.4.3 (b)), and $r < n$ ; so $r - r' < n$ , a contradiction. Hence $r = r'$ . Then $qn = q'n$ (add $-r$ to both sides of $qn + r = q'n + r$ ), so $(q - q')n = qn - q'n = 0$ by Proposition 2.3.2 (c) and (F9), and since $n \ne 0$ , Proposition 2.4.3 (f) gives $q - q' = 0$ . Hence $q = (q - q') + q' = q'$ , by (F1)–(F4).

For $n = 0$ the statement fails: no $r$ satisfies $0 \le r < 0$ . Exercise B1 handles $n < 0$ .

Uniqueness is what turns the theorem into a test for divisibility: $n \mid a$ if and only if the remainder of $a$ on division by $n$ is $0$ . Indeed, if $a = kn$ , then $a = kn + 0$ is a division with remainder, and by uniqueness it is the only one; conversely $a = qn + 0$ says $n \mid a$ . For instance $12 = 2 \cdot 5 + 2$ with $0 \le 2 < 5$ , so the remainder is $2 \ne 0$ , and $5 \nmid 12$ .

Quick check. Find the quotient and the remainder of $a = -23$ on division by $n = 4$ .

Solution. $q = -6$ and $r = 1$ : $(-6) \cdot 4 + 1 = -24 + 1 = -23$ , and $0 \le 1 < 4$ . By uniqueness this is the only such pair. The equation $-23 = (-5) \cdot 4 - 3$ is also true, but $-3$ is not a remainder, since it fails $0 \le r < 4$ ; the warning below says why that matters.

Warning. “The remainder” means the $r$ with $0 \le r < n$ . The equation $-17 = (-3) \cdot 5 - 2$ is true, but $-2$ is not the remainder of $-17$ on division by $5$ ; the remainder is $3$ . If negative “remainders” were allowed, uniqueness would fail at once: $-17 = (-3) \cdot 5 + (-2) = (-4) \cdot 5 + 3$ .

2.5.3. Even and odd

Recall that an integer $a$ is even if $a = 2k$ for some $k \in \mathbb{Z}$ , and odd if $a = 2k + 1$ for some $k \in \mathbb{Z}$ (Sets and Functions, Definition 1.1.1, as in Sets and Functions, Theorem 1.1.2), now read on the constructed $\mathbb{Z}$ . With $n = 2$ , the theorem answers the opening question.

Corollary 2.5.3 (Even and Odd Integers)

(a) Every $a \in \mathbb{Z}$ is even or odd, and not both. More precisely, either $a = 2q$ for exactly one $q \in \mathbb{Z}$ and $a$ is not of the form $2k + 1$ , or $a = 2q + 1$ for exactly one $q \in \mathbb{Z}$ and $a$ is not of the form $2k$ .
(b) If $a \in \mathbb{Z}$ and $a^2$ is even, then $a$ is even.

Idea. Divide by $2$ . The remainder lies in $\{0, 1\}$ , by discreteness, and it is unique, so each integer has exactly one of the two forms. For (b), square the odd form and read off the remainder.

Proof.

(a) Since $2 = 1 + 1 > 0$ , the theorem with $n = 2$ gives unique $q, r \in \mathbb{Z}$ with $a = 2q + r$ and $0 \le r < 2$ . Then $r \in \{0, 1\}$ : if $r \ne 0$ , then $0 < r$ , so $1 \le r$ by discreteness (Theorem 2.4.2 (c)); and if moreover $1 < r$ , then $2 = 1 + 1 \le r$ by discreteness again, against $r < 2$ . If $a = 2k$ and $a = 2k' + 1$ for some $k, k' \in \mathbb{Z}$ , then $(k, 0)$ and $(k', 1)$ would be two pairs as in the theorem, and $0 \ne 1$ contradicts its uniqueness. The same uniqueness shows that $q$ is the only integer with $a = 2q + r$ .
(b) Suppose $a$ is not even. By (a), $a = 2q + 1$ with $q \in \mathbb{Z}$ . Then $a^2 = (2q + 1)^2 = 4q^2 + 4q + 1 = 2(2q^2 + 2q) + 1 ,$ by Proposition 2.3.2 (d) and (F5), (F6), (F9), so $a^2$ is odd, and by (a) it is not even. This proves (b) by contraposition.

So $-7 = (-4) \cdot 2 + 1$ is odd and not even, as school says, and now by proof. Part (a) is Sets and Functions, Theorem 1.1.2 on the constructed $\mathbb{Z}$ , and part (b) is Logic and Proof, Theorem 2.1.3, whose proof used (a) and the computation above as school facts. For $a \in \mathbb{N}$ , (a) is also Proposition 1.3.4 (d) of Chapter 1.

Remark (Looking ahead). Preliminaries for Analysis and Algebra, Chapter 2 builds on this section: greatest common divisors and Bézout’s identity, primes and unique factorization, and arithmetic modulo $n$ , all on the constructed $\mathbb{Z}$ . Chapter 3 of this volume builds the rationals as classes of fractions, and its integer part of $a/n$ is the quotient found here.

2.5.4. Exercises

A. Check your understanding

Exercise (A1)

(a) Find the quotient and the remainder on division by $n = 6$ of $a = 47$ , of $a = -47$ and of $a = 0$ .
(b) Where is $n > 0$ used in the existence half of Theorem 2.5.2 (a)?
(c) True or false, with a reason: $0 \mid 0$ .
(d) True or false, with a reason: for all $a, b \in \mathbb{Z}$ , if $a \mid b$ and $b \mid a$ , then $a = b$ .

Solution.

(a) $47 = 7 \cdot 6 + 5$ , so $(q, r) = (7, 5)$ . $-47 = (-8) \cdot 6 + 1$ , since $-48 + 1 = -47$ , so $(q, r) = (-8, 1)$ . $0 = 0 \cdot 6 + 0$ , so $(q, r) = (0, 0)$ . In each case $0 \le r < 6$ , so by uniqueness these are the quotient and remainder. Note $(-8, 1)$ , not $(-7, -5)$ .
(b) Twice. For $a < 0$ , the element $a - an = a(1 - n)$ of $R$ is non-negative because $1 - n \le 0$ , which comes from $n \ge 1$ , that is, from $n > 0$ and discreteness. And the contradiction “ $r - n < r$ ” needs $-n < 0$ , that is, $n > 0$ .
(c) True: $0 = 1 \cdot 0$ , so $k = 1$ witnesses $0 \mid 0$ (Proposition 2.5.1 (a)).
(d) False: $2 \mid -2$ and $-2 \mid 2$ (Proposition 2.5.1 (d)), but $2 \ne -2$ . The statement is true for $a, b \in \mathbb{N}$ (Proposition 2.5.1 (f)).

B. Practice

Exercise (B1: Negative divisors)

Let $a, n \in \mathbb{Z}$ with $n < 0$ . Prove that there are unique $q, r \in \mathbb{Z}$ with $a = qn + r$ and $0 \le r < -n$ .

Solution. Since $n < 0$ , $-n > 0$ by Proposition 2.4.3 (a), so $-n \in \mathbb{Z}_{>0}$ .

Existence. By Theorem 2.5.2 (a) applied to $a$ and $-n$ , there are $q_0, r \in \mathbb{Z}$ with $a = q_0(-n) + r$ and $0 \le r < -n$ . Let $q \mathrel{:=} -q_0$ . Then $q_0(-n) = (-q_0)n = qn$ by Proposition 2.3.2 (c), so $a = qn + r$ .

Uniqueness. Let $a = qn + r = q'n + r'$ with $0 \le r, r' < -n$ . By Proposition 2.3.2 (c), $qn = (-q)(-n)$ and $q'n = (-q')(-n)$ , so $a = (-q)(-n) + r = (-q')(-n) + r'$ are two divisions of $a$ by $-n$ . The uniqueness in Theorem 2.5.2 (a) gives $r = r'$ and $-q = -q'$ , hence $q = -(-q) = -(-q') = q'$ by Proposition 2.3.2 (a).

Exercise (B2: Three in a row)

Let $a \in \mathbb{Z}$ . Prove that exactly one of $a$ , $a + 1$ , $a + 2$ is divisible by $3$ .

Solution. At least one. By Theorem 2.5.2 (a), $a = 3q + r$ with $0 \le r < 3$ , and $r \in \{0, 1, 2\}$ by discreteness, as in the proof of Corollary 2.5.3. If $r = 0$ , then $3 \mid a$ . If $r = 1$ , then $a + 2 = 3q + 3 = 3(q + 1)$ . If $r = 2$ , then $a + 1 = 3q + 3 = 3(q + 1)$ .

At most one. Suppose $3 \mid a + i$ and $3 \mid a + j$ with $0 \le i < j \le 2$ . By Proposition 2.5.1 (c) (with $x = 1$ , $y = -1$ ), $3 \mid (a + j) - (a + i) = j - i$ , and $j - i \in \{1, 2\}$ is positive. By Proposition 2.5.1 (e), $3 \le j - i \le 2$ , which is false. So no two of the three are divisible by $3$ .

(Equivalently: the remainders of $a$ , $a + 1$ , $a + 2$ on division by $3$ are $r$ , and then the other two of $0, 1, 2$ , and uniqueness of remainders allows only one of them to be $0$ .)

C. Going deeper

Exercise (C1: Exit check: remainders of squares)

(a) Prove that for every $a \in \mathbb{Z}$ , the remainder of $a^2$ on division by $4$ is $0$ or $1$ .
(b) Deduce that no integer whose remainder on division by $4$ is $3$ is a sum $x^2 + y^2$ of two squares of integers.

Name the result behind each step.

Solution.

(a) By Corollary 2.5.3 (a), $a = 2q$ or $a = 2q + 1$ for some $q \in \mathbb{Z}$ . In the first case $a^2 = (2q)(2q) = 4q^2 = q^2 \cdot 4 + 0$ , by the ring laws (F5), (F6) and $4 = 2 \cdot 2$ , computed in $\mathbb{N}$ . In the second, $a^2 = (2q + 1)^2 = 4q^2 + 4q + 1 = (q^2 + q) \cdot 4 + 1 ,$ by Proposition 2.3.2 (d) and the ring laws (F5), (F6), (F9). Since $4$ is a non-zero natural number, $4 > 0$ (Theorem 2.4.2 (b)), and both remainders, $0$ and $1$ , satisfy $0 \le r < 4$ , so by the uniqueness in Theorem 2.5.2 (a) they are the remainders of $a^2$ on division by $4$ .
(b) Let $x, y \in \mathbb{Z}$ . By (a), $x^2 = 4k + s$ and $y^2 = 4l + t$ with $k, l \in \mathbb{Z}$ and $s, t \in \{0, 1\}$ . Then $x^2 + y^2 = 4(k + l) + (s + t) , \qquad s + t \in \{0, 1, 2\} ,$ by (F1), (F2) and (F9). So $0 \le s + t \le 2 < 4$ , and by uniqueness $s + t$ is the remainder of $x^2 + y^2$ on division by $4$ . It is not $3$ , so no sum of two squares has remainder $3$ .

Marking scheme. (10 points)

2: splits into the two cases $a = 2q$ , $a = 2q + 1$ , citing Corollary 2.5.3 (a).
3: expands both squares and writes each in the form $q' \cdot 4 + r$ , with the identities justified by the ring laws.
2: checks $0 \le r < 4$ and invokes uniqueness to conclude that $r$ is the remainder.
3: for (b), adds the two forms, checks $0 \le s + t \le 2 < 4$ , and concludes by uniqueness (or by Proposition 2.5.1 (e) applied to the difference) that the remainder is $s + t \ne 3$ .

Fatal errors (0 for the step): calling a value outside $0 \le r < 4$ a remainder; concluding in (b) that the remainder is $s + t$ without checking $0 \le s + t < 4$ or an equivalent divisibility argument.

A proof that divides $a$ by $4$ instead, with four cases $a = 4m + j$ , $j \in \{0, 1, 2, 3\}$ , earns the first 2 points for the case split (citing Theorem 2.5.2 (a) and discreteness) and the rest as above.

R. Review

Exercise (R1)

Let $f \colon \mathbb{N} \to \mathbb{N}$ satisfy $f(0) = 0$ and $f(n + 1) = f(n) + 2n + 1$ for every $n \in \mathbb{N}$ . Prove that $f(n) = n \cdot n$ for every $n$ .

Solution. By Theorem 1.2.1, with $g(n, x) = x + 2n + 1$ , exactly one such $f$ exists, so the question is about a definite function. We prove $f(n) = n \cdot n$ by induction on $n$ (Theorem 1.1.2).

Base. $f(0) = 0 = 0 \cdot 0$ , by Definition 1.2.1 (b).

Step. Suppose $f(n) = n \cdot n$ . Then $f(n + 1) = (n \cdot n + 2n) + 1$ . On the other side, with $\mathrm{S}(n) = n + 1$ (Definition 1.2.1 (c)), $\begin{aligned} (n + 1)(n + 1) &= (n + 1) \cdot n + (n + 1) \\ &= (n \cdot n + n) + (n + 1) = (n \cdot n + (n + n)) + 1 , \end{aligned}$ by Definition 1.2.1 (b) applied to $(n + 1) \cdot \mathrm{S}(n)$ , then Theorem 1.2.3 (e) for $(n + 1) \cdot n = n \cdot n + n$ , and Theorem 1.2.3 (c) to regroup. Finally $2n = (1 + 1)n = 1 \cdot n + 1 \cdot n = n + n$ , by $1 + 1 = 2$ (Definition 1.2.1 (c)) and Theorem 1.2.3 (d), (e). So $f(n + 1) = (n + 1)(n + 1)$ , and the claim holds for every $n$ .

This is Chapter 1’s move of fixing everything else and inducting on the recursion variable, as in the proof of Theorem 1.2.3.

Exercise (R2)

Decide which of the following maps $\mathbb{Z} \to \mathbb{Z}$ are injective and which are surjective:

(a) $x \mapsto -x$ ;
(b) $x \mapsto 2x$ ;
(c) $x \mapsto x^2$ .

Solution.

(a) Bijective. Since $-(-x) = x$ (Proposition 2.3.2 (a)), equal values $-x = -y$ give $x = -(-x) = -(-y) = y$ , and every $y$ is the value at $-y$ .
(b) Injective, not surjective. If $2x = 2y$ , then $2(x - y) = 2x - 2y = 0$ by (F9) and Proposition 2.3.2 (c); and $2 \ne 0$ , since $2 = 1 + 1 > 0$ . So $x - y = 0$ by Proposition 2.4.3 (f), and $x = y$ . Not surjective: $1 = 2x$ would make $1$ even, but $1 = 2 \cdot 0 + 1$ is odd, and no integer is both (Corollary 2.5.3 (a)).
(c) Neither. Not injective: $(-1)^2 = 1 = 1^2$ (Proposition 2.3.2 (c)), and $-1 \ne 1$ , since $-1 < 0 < 1$ (shown below) gives $-1 < 1$ by (O2), and (O1) forbids equality. Not surjective: $x^2 \ge 0$ for every $x$ ( $x^2 = 0$ for $x = 0$ by Proposition 2.3.2 (b), and $x^2 > 0$ otherwise by Proposition 2.4.3 (e)), while $-1 < 0$ ( $1 > 0$ by Proposition 2.4.3 (e), so $-1 < -0 = 0$ by Proposition 2.4.3 (a)). So $-1$ is not a value.

The methods are those of Sets and Functions, Example (Method: proving injectivity) and Sets and Functions, Example (Method: proving surjectivity): for injectivity, start from equal values and reach equal inputs; for surjectivity, solve for the input, or show that a target is never reached.

Exercise (R3)

Prove that for every $a \in \mathbb{Z}$ : if $3 \mid a^2$ , then $3 \mid a$ .

Solution. By contraposition, as in Logic and Proof, Theorem 2.1.3. Suppose $3 \nmid a$ . Since $3$ is a non-zero natural number, $3 > 0$ (Theorem 2.4.2 (b)), so division by $3$ (Theorem 2.5.2 (a)) gives $a = 3q + r$ with $0 \le r < 3$ , so $r \in \{0, 1, 2\}$ by discreteness (Theorem 2.4.2 (c)), as in the proof of Corollary 2.5.3; and $r \ne 0$ , since otherwise $a = 3q$ and $3 \mid a$ . By Proposition 2.3.2 (d) and the ring laws, $\begin{aligned} r = 1 &: \quad a^2 = 9q^2 + 6q + 1 = 3(3q^2 + 2q) + 1 , \\ r = 2 &: \quad a^2 = 9q^2 + 12q + 4 = 3(3q^2 + 4q + 1) + 1 . \end{aligned}$ In both cases $0 \le 1 < 3$ , so the remainder of $a^2$ on division by $3$ is $1 \ne 0$ , and $3 \nmid a^2$ by the divisibility test after Theorem 2.5.2. This proves the contrapositive.