The natural numbers: synthesis and challenges

Summary

This lesson closes the unit devoted to the natural numbers. It reconstructs the deductive chain that leads from the language of sets and the Peano axioms to the binomial theorem, indicating at each link which principle is used and which result is obtained; it places what has been achieved within the plan of the course and explains why the limits of subtraction and division among natural numbers lead to the next unit, devoted to number systems. It ends with ten challenges, harder than the problems of the lessons, which require combining the tools of several of them.

Learning objectives

Reconstruct the logical order of the results of the unit, identifying the principle on which each one rests.
Explain how induction, well-ordering, division with remainder, unique factorization and congruences are related.
Justify, from the limitations of subtraction and division among natural numbers, the need to extend the number systems.
Solve problems that combine induction, divisibility, positional notation and counting.

What the unit achieved

The unit set out to deduce the arithmetic of the natural numbers from a few principles, without accepting any of its properties as evident. The aim has been fulfilled with a few reservations, each one declared in its place: the rules of naive set theory and of the negation of quantifiers, which are the language in which everything else is written; the existence of the functions defined by recursion, which Dedekind’s recursion theorem guarantees and which was admitted because it belongs to set theory; the uniqueness of the number of elements of a finite set, and the finiteness of its subsets, on which counting rests; generalized commutativity, which allows the factors of a finite product to be reordered; and the elementary rules of the integers, the rationals and the reals, which the unit anticipated in examples and problems and which the next unit constructs. With these reservations, the path travelled can be read as a single deductive chain in four segments.

The foundations: sets, axioms, operations and order

The lesson on sets, relations and functions fixed the language in which the unit is written, declaring the little it admits from set theory, and proved that equivalence relations and partitions are two faces of a single idea: the classes of an equivalence form a partition, and every partition comes from a unique equivalence. That result reappears in the classification of the integers by their remainder and in congruences, and the next unit uses it to construct the integers and the rationals as classes of pairs. In the lesson on the Peano axioms the natural numbers were defined by means of $1$ , the successor operation and five axioms; the second to fourth axioms guarantee that the sequence neither stops nor turns back on itself, and the fifth, the principle of induction, guarantees that there are no natural numbers other than those reached from $1$ . The lesson on the basic operations and order built on the successor, with the recursion theorem, a ladder of recursive definitions, in which each operation is defined by means of the previous one:

n + S(m) = S(n + m), \qquad n \cdot S(m) = n \cdot m + n, \qquad b^{S(n)} = b^n \cdot b

From these definitions, commutativity, associativity, distributivity and cancellation were deduced by induction, and order was obtained from addition, with trichotomy, transitivity and monotonicity. Subtraction and division were defined as inverse operations, but only in certain cases: $a - b$ exists when $b < a$ , and $\frac{a}{b}$ , when $b$ divides $a$ .

The principles of proof

The lesson on summations, progressions and induction widened the repertoire of proofs. It proved that ordinary induction implies strong induction and the well-ordering principle, and that, with the lemma that every natural number other than $1$ is a successor and the properties of order, well-ordering in turn implies induction, so that each proof may use whichever principle suits it best; it gave sums a recursive definition and properties that allow them to be calculated, and showed with telescoping sums that a formula can be deduced, and not merely verified. The well-ordering principle turned out to be the tool of almost all the existence proofs that followed, because it allows one to choose the least element of a set and to reason by the smallest counterexample.

The arithmetic of divisibility

With well-ordering, the lesson on divisibility proved that every integer, when divided by a natural number, has a unique quotient and a unique remainder. The following four results depend on that theorem, each one resting on the previous ones:

The classification of the integers by their remainder, which allows proof by cases, and the divisibility tests, which reduce to the fact that two numbers that differ by a multiple of $d$ leave the same remainder when divided by $d$ .
In the lesson on prime numbers, Euclid’s lemma, proved with well-ordering and division with remainder, and with it the fundamental theorem of arithmetic: every natural number greater than $1$ is a product of primes in exactly one way. From uniqueness were deduced the number of divisors, the characterization of perfect squares and the irrationality of roots that are not exact.
In the lesson on the greatest common divisor, the Euclidean algorithm, which applies division with remainder until it is exhausted, Bézout’s identity, which is deduced from it, and the complete solution of linear Diophantine equations.
In the lesson on congruences, the conversion of all the above into a calculus: congruence modulo $n$ is an equivalence relation compatible with addition and multiplication, whose classes form $\mathbb{Z}_n$ ; Bézout’s identity decides which remainders are invertible and when a linear congruence has a solution, and yields the Chinese remainder theorem; and Euclid’s lemma, together with inverses, yields Fermat’s little theorem.

Writing and counting

The lesson on positional numeral systems applied division with remainder again and again to prove that every natural number is written in exactly one way in any base, and thereby justified the calculation procedures and the divisibility tests in every base. The lesson on combinatorics and the binomial theorem returned to the starting point, because counting is the operation that gave rise to the natural numbers: the addition and multiplication principles, proved from the definition of the number of elements by means of bijections (the second by induction from the first), led to the binomial coefficients, to Pascal’s rule and to the binomial theorem, whose proof brings together induction, summation notation and counting.

The following figure gathers the four segments into a single chain. Each node of the column is a definition or a theorem, numbered according to the logical order and joined by an arc to the earlier links that its proof uses; around it float the supports, that is, the principles and tools to which the chain resorts again and again, each one joined by a solid line to the links that rest on it and by a dotted one to the link where it is established, except those admitted without proof, which are drawn as rings. Clicking a support highlights all the links that use it, and each link refers to the lesson in which it is proved.

Supports of the chain

APrinciple of induction. If a property holds for $1$ and, assuming it for an arbitrary natural number $k$ , it holds for its successor $S(k)$ , then it holds for all natural numbers. Established in: 2. Peano axioms.
BRecursion theorem. Given the value at $1$ and a rule that gives the value at $S(n)$ from the value at $n$ , there is a unique function on the natural numbers satisfying them; this is how addition, multiplication, exponentiation, summation and the factorial are defined. Existence is admitted; uniqueness is proved by induction. Admitted without proof in this unit.
CStrong induction. It suffices to prove a property for $1$ and that, assuming it for all natural numbers from $1$ to $n$ , it holds for $n + 1$ . Established in: 9. Strong induction.
DWell-ordering. Every nonempty set of natural numbers has a least element, which allows one to reason by the smallest counterexample. Established in: 10. Well-ordering principle.
EDivision with remainder. For every integer $a$ and every natural number $b$ there are a unique quotient $q$ and a unique remainder $r$ such that $a = bq + r$ and $0 \leq r < b$ . Established in: 12. Division with remainder.
FLinear combinations. If an integer $d$ divides the integers $a$ and $b$ , it divides $ax + by$ for all integers $x$ and $y$ ; in particular, their sum and their difference. Established in: 11. Properties of divisibility.
GAnticipated numbers. The elementary rules of calculation and of order of the integers, the rationals and the reals (signs, cancellation, fractions, roots) are anticipated in this unit without proof; their construction is the subject of the next unit. Admitted without proof in this unit.
HNumber of elements. A set that admits a bijection with $\{1, \ldots, n\}$ has $n$ elements; it is admitted that this number is unique and that the subsets of a finite set are finite. Admitted without proof in this unit.

Segment 1 The foundations: sets, axioms, operations and order
- Fix the language of sets, relations and functions, and prove that equivalence relations and partitions correspond to each other.
- Define the natural numbers from $1$ and the successor by means of the five Peano axioms.
- Build on the successor a ladder of recursive definitions: addition, multiplication and exponentiation.
- Deduce by induction commutativity, associativity, distributivity and cancellation.
- Obtain order from addition, with trichotomy, transitivity and monotonicity, and specify when subtraction and division exist.
1. Equivalences and partitions. The classes of an equivalence relation on a set form a partition of it, and every partition is the set of classes of a unique equivalence relation.
  Proved in: Sets, relations and functions.
2. Peano axioms. The natural numbers are generated from $1$ by the successor: $1$ is not the successor of any of them, distinct natural numbers have distinct successors, and every set that contains $1$ and the successor of each of its elements contains all the natural numbers.
  Proved in: The natural numbers and the Peano axioms.
3. Recursive addition. Addition, defined by $n + 1 = S(n)$ and $n + S(m) = S(n + m)$ , is commutative, associative and cancellative.
  Uses: 2. Peano axioms. Rests on: A (Principle of induction), B (Recursion theorem). Proved in: Basic operations on natural numbers and order relations.
4. Multiplication and exponentiation. Multiplication, defined by $n \cdot 1 = n$ and $n \cdot S(m) = n \cdot m + n$ , is commutative, associative, distributive and cancellative, and exponentiation satisfies $b^n b^m = b^{n + m}$ , $(b^n)^m = b^{nm}$ and $(ab)^n = a^n b^n$ .
  Uses: 3. Recursive addition. Rests on: A (Principle of induction), B (Recursion theorem). Proved in: Basic operations on natural numbers and order relations.
5. Order, subtraction and division. If $a < b$ means that $a + k = b$ for some natural number $k$ , then between two natural numbers exactly one of the relations $a < b$ , $a = b$ and $b < a$ holds, and the order is transitive and is preserved by addition and multiplication; the difference $a - b$ exists only when $b < a$ , and the quotient $\frac{a}{b}$ only when $b$ divides $a$ , and both are unique by cancellation.
  Uses: 2. Peano axioms, 3. Recursive addition, 4. Multiplication and exponentiation. Rests on: A (Principle of induction). Proved in: Basic operations on natural numbers and order relations.
Segment 2 The principles of proof
- Prove that ordinary induction, strong induction and the well-ordering principle are equivalent.
- Define summation recursively and deduce its properties.
- Deduce formulas with telescoping sums, instead of merely verifying them.
- Sum arithmetic and geometric progressions.
1. Induction from a natural number. A property that holds for $n_0$ and passes from each natural number $k \geq n_0$ to $k + 1$ holds for every natural number $n \geq n_0$ .
  Uses: 5. Order, subtraction and division. Rests on: A (Principle of induction). Proved in: Summations, progressions and induction.
2. Summation and telescoping sum. Defined recursively, summation is linear, splits into consecutive sums and admits shifting the index and reversing the order; a sum of differences between consecutive values equals the last value minus the first: $\sum_{k=1}^{n} (b_{k + 1} - b_k) = b_{n + 1} - b_1$ .
  Uses: 4. Multiplication and exponentiation, 6. Induction from a natural number. Rests on: A (Principle of induction), B (Recursion theorem). Proved in: Summations, progressions and induction.
3. Progressions. The sum of $n$ terms of an arithmetic progression is $\frac{n(a_1 + a_n)}{2}$ , and that of a geometric one with first term $a$ and common ratio $r \neq 1$ is $a \cdot \frac{r^n - 1}{r - 1}$ .
  Uses: 7. Summation and telescoping sum. Rests on: A (Principle of induction), G (Anticipated numbers). Proved in: Summations, progressions and induction.
4. Strong induction. If a property holds for $1$ and, assuming it for all natural numbers from $1$ to $n$ , it holds for $n + 1$ , then it holds for all natural numbers.
  Uses: 6. Induction from a natural number. Rests on: A (Principle of induction). Proved in: Summations, progressions and induction.
5. Well-ordering principle. Every set of natural numbers with at least one element has a least element; with the lemma that every natural number other than $1$ is a successor and the properties of order, well-ordering in turn implies induction, and the three principles turn out to be equivalent.
  Uses: 5. Order, subtraction and division. Rests on: C (Strong induction). Proved in: Summations, progressions and induction.
Segment 3 The arithmetic of divisibility
- Prove with well-ordering the existence and uniqueness of the quotient and the remainder.
- Classify the integers by their remainder and base the divisibility tests on it.
- Prove the infinitude of the primes, Euclid’s lemma and unique factorization, with their consequences.
- Calculate the greatest common divisor with the Euclidean algorithm, deduce Bézout’s identity from it and solve linear Diophantine equations.
- Calculate with congruences, decide which remainders are invertible, solve linear congruences and systems with coprime moduli, and prove Fermat’s little theorem.
1. Properties of divisibility. Divisibility among integers is reflexive and transitive, a divisor of an integer $a > 0$ lies between $-a$ and $a$ , and if $d$ divides $a$ and $b$ , it divides every combination $ax + by$ .
  Uses: 5. Order, subtraction and division. Rests on: G (Anticipated numbers). Proved in: Divisibility and division with remainder.
2. Division with remainder. For every integer $a$ and every natural number $b$ there exist a unique quotient $q$ and a unique remainder $r$ such that $a = bq + r$ and $0 \leq r < b$ .
  Rests on: D (Well-ordering), G (Anticipated numbers). Proved in: Divisibility and division with remainder.
3. Remainders and tests. Two integers leave the same remainder when divided by $d$ if and only if their difference is a multiple of $d$ ; from this follow the remainder of a sum, of a product and of a power, and the tests for $3$ , for $9$ and for $11$ .
  Rests on: A (Principle of induction), E (Division with remainder), F (Linear combinations). Proved in: Divisibility and division with remainder.
4. Prime divisor and infinitude. Every natural number $n > 1$ has a prime divisor, and if $n$ is composite, its least prime divisor $p$ satisfies $p^2 \leq n$ ; from this it follows that no finite list contains all the prime numbers.
  Uses: 5. Order, subtraction and division, 11. Properties of divisibility. Rests on: D (Well-ordering), F (Linear combinations). Proved in: Prime numbers and the fundamental theorem of arithmetic.
5. Euclid’s lemma. If a prime divides the product $ab$ , it divides $a$ or it divides $b$ ; and if it divides a product of several factors, it divides one of them.
  Rests on: A (Principle of induction), D (Well-ordering), E (Division with remainder), F (Linear combinations). Proved in: Prime numbers and the fundamental theorem of arithmetic.
6. Fundamental theorem. Every natural number $n > 1$ is a product of prime numbers, and that factorization is unique up to the order of the factors.
  Uses: 4. Multiplication and exponentiation, 15. Euclid’s lemma. Rests on: D (Well-ordering). Proved in: Prime numbers and the fundamental theorem of arithmetic.
7. Divisors and irrational roots. If $n = p_1^{e_1} \cdots p_k^{e_k}$ , its divisors are the numbers $p_1^{f_1} \cdots p_k^{f_k}$ with $0 \leq f_i \leq e_i$ , and there are $(e_1 + 1) \cdots (e_k + 1)$ of them; a natural number $n > 1$ is a perfect $k$ -th power if and only if all the exponents of its factorization are multiples of $k$ , and if it is not, there are no natural numbers $a$ and $b$ with $a^k = n b^k$ , that is, its $k$ -th root is irrational.
  Uses: 15. Euclid’s lemma, 16. Fundamental theorem. Rests on: A (Principle of induction), G (Anticipated numbers). Proved in: Prime numbers and the fundamental theorem of arithmetic.
8. Euclidean algorithm. If $a = bq + r$ , the pairs $a, b$ and $b, r$ have the same common divisors; therefore $\operatorname{gcd}(a, b)$ is the last nonzero remainder of the successive divisions.
  Rests on: D (Well-ordering), E (Division with remainder), F (Linear combinations). Proved in: Greatest common divisor and least common multiple.
9. Bézout’s identity. There exist integers $x$ and $y$ such that $ax + by = \operatorname{gcd}(a, b)$ , and the greatest common divisor is the least natural number that can be written in that form.
  Uses: 18. Euclidean algorithm. Rests on: A (Principle of induction), F (Linear combinations), G (Anticipated numbers). Proved in: Greatest common divisor and least common multiple.
10. Product of the gcd and the lcm. It holds that $\operatorname{gcd}(a, b) \cdot \operatorname{lcm}(a, b) = ab$ , and every common multiple of $a$ and $b$ is a multiple of their least common multiple.
  Uses: 4. Multiplication and exponentiation, 16. Fundamental theorem, 17. Divisors and irrational roots. Rests on: D (Well-ordering), E (Division with remainder), F (Linear combinations). Proved in: Greatest common divisor and least common multiple.
11. Diophantine equations. The equation $ax + by = c$ has integer solutions if and only if $d = \operatorname{gcd}(a, b)$ divides $c$ , and then they are all $x = x_0 + \frac{b}{d} t$ and $y = y_0 - \frac{a}{d} t$ , with $t$ an integer.
  Uses: 19. Bézout’s identity, 20. Product of the gcd and the lcm. Rests on: F (Linear combinations), G (Anticipated numbers). Proved in: Greatest common divisor and least common multiple.
12. Congruences and remainders. Two integers are congruent modulo $n$ if and only if they leave the same remainder when divided by $n$ ; congruence is an equivalence relation compatible with addition and multiplication, and its $n$ classes, those of the remainders $0, 1, \ldots, n - 1$ , form $\mathbb{Z}_n$ .
  Uses: 1. Equivalences and partitions, 13. Remainders and tests. Rests on: E (Division with remainder), F (Linear combinations). Proved in: Congruences and modular arithmetic.
13. Invertible remainders. An integer $a$ has an inverse modulo $n$ if and only if $\operatorname{gcd}(a, n) = 1$ , and then it is unique modulo $n$ ; the congruence $ax \equiv b \pmod{n}$ has a solution if and only if $d = \operatorname{gcd}(a, n)$ divides $b$ , and then it has $d$ solutions modulo $n$ .
  Uses: 22. Congruences and remainders, 19. Bézout’s identity, 21. Diophantine equations. Rests on: F (Linear combinations). Proved in: Congruences and modular arithmetic.
14. Chinese remainder theorem. If the natural numbers $m$ and $n$ are coprime, the system formed by $x \equiv a \pmod{m}$ and $x \equiv b \pmod{n}$ has a solution, and it is unique modulo $mn$ .
  Uses: 22. Congruences and remainders, 19. Bézout’s identity, 20. Product of the gcd and the lcm. Rests on: G (Anticipated numbers). Proved in: Congruences and modular arithmetic.
15. Fermat’s little theorem. If $p$ is prime and does not divide the integer $a$ , then $a^{p - 1} \equiv 1 \pmod{p}$ ; and for every integer $a$ , $a^p \equiv a \pmod{p}$ .
  Uses: 22. Congruences and remainders, 15. Euclid’s lemma, 23. Invertible remainders. Proved in: Congruences and modular arithmetic.
Segment 4 Writing and counting
- Prove that every natural number is written in exactly one way in any base.
- Justify in every base column addition and the divisibility tests.
- Count with the addition and multiplication principles, and obtain from them the binomial coefficients and Pascal’s rule.
- Prove the binomial theorem, which brings together induction, summation notation and counting.
1. Positional representation. For every base $b \geq 2$ , every natural number is written in exactly one way as $a_k b^k + \cdots + a_1 b + a_0$ , with digits between $0$ and $b - 1$ and $a_k \neq 0$ .
  Rests on: C (Strong induction), D (Well-ordering), E (Division with remainder). Proved in: Positional numeral systems.
2. Calculation and tests in every base. Column addition gives the representation of the sum, and in base $b$ a number leaves the same remainder as the sum of its digits when divided by $b - 1$ , and the same as its alternating sum when divided by $b + 1$ .
  Uses: 7. Summation and telescoping sum, 13. Remainders and tests, 26. Positional representation. Rests on: A (Principle of induction), E (Division with remainder). Proved in: Positional numeral systems.
3. Counting principles. The union of two sets with no common elements, of $m$ and of $n$ elements, has $m + n$ elements, and a choice in two stages, of $m$ and of $n$ ways, can be made in $mn$ ways.
  Uses: 3. Recursive addition, 4. Multiplication and exponentiation, 5. Order, subtraction and division. Rests on: A (Principle of induction), H (Number of elements). Proved in: Elementary combinatorics and the binomial theorem.
4. Binomial coefficients and Pascal’s rule. A set of $n$ elements has $\binom{n}{k} = \frac{n!}{k!\,(n - k)!}$ subsets of $k$ elements; it holds that $\binom{n + 1}{k} = \binom{n}{k - 1} + \binom{n}{k}$ , whence the coefficients form Pascal’s triangle, and row $n$ sums to $2^n$ .
  Uses: 28. Counting principles. Rests on: B (Recursion theorem), H (Number of elements). Proved in: Elementary combinatorics and the binomial theorem.
5. Binomial theorem. For all numbers $x$ and $y$ , natural or, anticipating the next unit, real, and every natural number $n$ , it holds that $(x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n - k} y^k$ .
  Uses: 7. Summation and telescoping sum, 29. Binomial coefficients and Pascal’s rule. Rests on: A (Principle of induction), G (Anticipated numbers). Proved in: Elementary combinatorics and the binomial theorem.

Towards number systems. The chain stops where the natural numbers cease to suffice: subtraction and division exist only in certain cases, and the equation $x^2 = n$ has no rational solution when $n$ is not a perfect square. The next unit extends the natural numbers to remedy this.