## 305 -1. Algebra and induction

1. Abstract algebra is the study of algebraic structures (groups, rings, fields, etc). Most of this study is done at a fairly general level, and its development marks a significant shift from how mathematics had been done before, where the emphasis was on particular structures (say, the set of reals, or triangles in Euclidean plane) and their properties. We follow the textbook in that our approach will be with the goal of solving the question of which polynomial equations (with integer) coefficients can be solved (by radicals). Concepts will be introduced with this goal in mind, and we will begin by looking at fields (mainly number fields) and move to groups, rather than the other way around, as it is customary.

The study of equations has always been an integral part of algebra, and it certainly guided its origins. The book starts with a nice short history, here is the pdf on this subject I used in lecture. It ends with a short list of names of (mostly) mathematicians that intends to illustrate the historical development of the idea of mathematical induction. Following the book, we introduce induction in the  form of the well-ordering principle.

2. Notation. ${\mathbb N}=\{0,1,2,\dots\}$ is the set of natural numbers. $P={\mathbb Z}^+={\mathbb N}^+$ is the set of positive integers. ${\mathbb Z}$ is the set of integers (or whole numbers).

The well-ordering principle. Every nonempty set of natural numbers has a least element.

This should be understood as an axiomatic property of the natural numbers.

Our first application is in proving the following result, (what one usually calls the division algorithm).

Theorem. Given integers $m,n$ with $n>0$, there are integers $q,r$ such that $m=nq+r$ and $0\le r.

Proof.  Consider the set $A$ of natural numbers that can be written in the form $m-nq$ for some integer $q$. (So, as $q$ varies, the numbers $m-nq$ belong to $A$ or not depending on whether they are nonnegative.)

This set is nonempty (this can be proved by analyzing two cases, depending on whether $m\ge0$ or not; in each case, we can explicitly exhibit an element of $A$). By the well-ordering principle, $A$ has a least element. Call it $r$.

Since $r\in A$, there is some integer $q$ such that $m=nq+r$; fix such $q$ and $r$ in what follows. It remains to show that $0\le r. That $0\le r$ follows from the fact that $r\in A$, and all the elements of $A$ are nonnegative.

That $r is proved by contradiction: Otherwise, $0\le r-n, and $r=m-nq$, so $r-n=m-n(q+1)=m-nq'$ where $q'=q+1$. It follows that $r-n\in A$, but this is impossible, since $r-n, and $r$ is the least element of $A$. This is a contradiction. It follows that it is not the case that $r\ge n$, so $r, as wanted. $\mathsf{QED}$