Abstract Algebra/Number Theory

As numbers of various number systems form basic units with which one must work when studying abstract algebra, we will now define the natural numbers and the rational integers as well as the basic operations of addition and multiplication. Using these definitions, we will also derive important properties of these number sets and operations. Following this, we will discuss important concepts in number theory; this will lead us to discussion of the properties of the integers modulo n.

The Peano postulates and the natural numbers

Definition: Using the undefined notions "1" and "successor" (denoted by $'$), we define the set of natural numbers without zero $\mathbb {N} ^{*}$, hereafter referred to simply as the natural numbers, with the following axioms, which we call the Peano postulates:

Axiom 1. $\exists 1(1\in \mathbb {N} ^{*}).$

Axiom 2. $\forall a(a\in \mathbb {N} ^{*}\implies \exists b(b=a')).$

Axiom 3. $\lnot \exists a(a'=1).$

Axiom 4. $\forall a\in \mathbb {N} ^{*}(\forall b\in \mathbb {N} ^{*}(a'=b'\implies a=b)).$

Axiom 5. $\forall A\subseteq \mathbb {N} ^{*}((1\in A)\land \forall a\in A(a'\in A)\implies A=\mathbb {N} ^{*}).$

We can prove theorems for natural numbers using mathematical induction as a consequence of the fifth Peano Postulate.

Addition

Definition: We recursively define addition for the natural numbers as a composition using two more axioms; the other properties of addition can subsequently be derived from these axioms. We denote addition with the infix operator +.

Axiom 6. $\forall a\in \mathbb {N} ^{*}(a+1=a').$

Axiom 7. $\forall a\in \mathbb {N} ^{*}(\forall b\in \mathbb {N} ^{*}(a+b'=(a+b)')).$

Axiom 6 above relies on the first Peano postulate (for the existence of 1) as well as the second (for the existence of a successor for every number).

Henceforth, we will assume that proven theorems hold for all $a,b,c,\ldots ,n$ in $\mathbb {N} ^{*}$.

Multiplication

Definition: We similarly define multiplication for the natural numbers recursively, again using two axioms:

Axiom 8. $a(1)=a.$

Axiom 9. $ab'=ab+a.$

Properties of addition

We start by proving that addition is associative.

Theorem 1: Associativity of addition: $(a+b)+c=a+(b+c).$

Proof: Base case: By axioms 6 and 7, $a+(b+1)=(a+b)'$.

By axiom 6, $a+(b+1)=(a+b)+1$.

Inductive hypothesis: Suppose that, for $k'>1$, $(a+b)+k=a+(b+k)$.

Inductive step: By axiom 7, $(a+b)+k'=\left[(a+b)+k\right]'$.

By the inductive hypothesis, $(a+b)+k'=\left[a+(b+k)\right]'$.

By axiom 7, $(a+b)+k'=a+(b+k)'$.

By axiom 7, $(a+b)+k'=a+(b+k')$.

By induction, $(a+b)+c=a+(b+c)$. QED.

Lemma 1: $a+1=1+a.$

Proof: Base case: 1+1=1+1.

Inductive hypothesis: Suppose that, for $k'>1$, $k+1=1+k$.

Inductive step: By axiom 6, $k'+1=(k+1)+1$.

By the inductive hypothesis, $k'+1=(1+k)+1$.

By theorem 1, $k'+1=1+(k+1)$.

By axiom 6, $k'+1=1+k'$.

By induction, $a+1=1+a$. QED.

Theorem 2: Commutativity of addition: $a+b=b+a.$

Proof: Base case: By lemma 1, $a+1=1+a$.

Inductive hypothesis: Suppose that, for $k'>1$, $a+k=k+a$.

By axiom 6, $a+k'=a+(k+1)$.

By theorem 1, $a+k'=(a+k)+1$.

By the inductive hypothesis, $a+k'=(k+a)+1$.

By theorem 1, $a+k'=k+(a+1)$.

By lemma 1, $a+k'=k+(1+a)$.

By theorem 1, $a+k'=(k+1)+a$.

By axiom 6, $a+k'=k'+a$.

By induction, $a+b=b+a$. QED.

Theorem 3: $a+b=a+c\implies b=c$.

Proof: Base case: Suppose $1+b=1+c$.

By theorem 2, $b+1=c+1$.

By axiom 6, $b'=c'$.

By axiom 4, $b=c$.

Inductive hypothesis: Suppose that, for $k'>1$, $k+b=k+c\implies b=c$.

Inductive step: Suppose $k'+b=k'+c$.

By axiom 6, $(k+1)+b=(k+1)+c$.

By theorem 2, $(1+k)+b=(1+k)+c$.

By theorem 1, $1+(k+b)=1+(k+c)$.

By the base case, $k+b=k+c$. Thus, $k'+b=k'+c\implies k+b=k+c$.

By the inductive hypothesis, $k'+b=k'+c\implies b=c$.

By induction, $a+b=a+c\implies b=c$. QED.

Properties of multiplication

Theorem 4: Left-distributivity of multiplication over addition: $a(b+c)=ab+ac$.

Proof: Base case: By axioms 6 and 9, $a(b+1)=ab+a$.

By axiom 8, $a(b+1)=ab+a(1)$.

Inductive hypothesis: Suppose that, for $k'>1$, $a(b+k)=ab+ak$.

Inductive step: By axiom 7, $a(b+k')=a(b+k)'$.

By axiom 9, $a(b+k')=a(b+k)+a$.

By the inductive hypothesis, $a(b+k')=(ab+ak)+a$.

By theorem 1, $a(b+k')=ab+(ak+a)$.

By axiom 9, $a(b+k')=ab+ak'$.

By induction, $a(b+c)=ab+ac$. QED.

Theorem 5: $1a=a$.

Proof: Base case: By axiom 8, 1(1)=1.

Inductive hypothesis: Suppose that, for $k'>1$, $1k=k$.

Inductive step: By axiom 6, $1k'=1(k+1)$.

By theorem 4, $1k'=1k+1(1)$.

By the base case, $1k'=1k+1$.

By the inductive hypothesis, $1k'=k+1$.

By axiom 6, $1k'=k'$.

By induction, $1a=a$. QED.

Theorem 6: $a'b=ab+b$.

Proof: Base case: By axiom 8, $a'(1)=a'$.

By axiom 6, $a'(1)=a+1$.

By axiom 8, $a'(1)=a(1)+1$.

Inductive hypothesis: Suppose that, $k'>1$, $a'k=ak+k$.

Inductive step: By axiom 9, $a'k'=a'k+a'$.

By the inductive hypothesis, $a'k'=ak+k+a'$.

By axiom 6, $a'k'=ak+k+(a+1)$.

By theorem 1, $a'k'=ak+(k+a)+1$.

By theorem 2, $a'k'=ak+(a+k)+1$.

By theorem 1, $a'k'=ak+a+k+1$

By axiom 9, $a'k'=ak'+k+1$.

By theorem 1, $a'k'=ak'+(k+1)$.

By axiom 6, $a'k'=ak'+k'$.

By induction, $a'b=ab+b$. QED.

Theorem 7: Associativity of multiplication: $(ab)c=a(bc).$

Proof: Base case: By axiom 8, $ab(1)=ab=a\left[b(1)\right]$.

Inductive hypothesis: Suppose that, for $k'>1$, $(ab)k=a(bk)$.

Inductive step: By axiom 9, $(ab)k'=(ab)k+ab$.

By the inductive hypothesis, $(ab)k'=a(bk)+ab$.

By theorem 4, $(ab)k'=a(bk+b)$.

By axiom 9, $(ab)k'=a(bk')$.

By induction, $(ab)c=a(bc)$. QED.

Theorem 8: Commutativity of multiplication: $ab=ba$.

Proof: Base case: By axiom 8 and theorem 5, $a(1)=a=1a$.

Inductive hypothesis: Suppose that, for $k'>1$, $ak=ka$.

Inductive step: By axiom 9, $ak'=ak+a$.

By the inductive hypothesis, $ak'=ka+a$.

By theorem 6, $ak'=k'a$.

By induction, $ab=ba$. QED.

Theorem 9: Right-distributivity of multiplication over addition: $(a+b)c=ac+bc$.

Proof: By theorems 4 and 7, $(a+b)c=ca+cb$.

By theorem 7, $(a+b)c=ac+bc$. QED.

The integers

The set of integers $\mathbb {Z}$ can be constructed from ordered pairs of natural numbers (a, b). We define an equivalence relation on the set of all such ordered pairs such that

$(a,b)\equiv (c,d)\Leftrightarrow a+d=c+b.$

Then the set of rational integers is the set of all equivalence classes of such ordered pairs. We will denote the equivalence class of which some pair (a, b) is a member with the notation [(a, b)]. Then, for any natural numbers a and b, [(a, b)] represents a rational integer.

Integer addition

Definition: We define addition for the integers as follows:

$\left[(a,b)\right]+\left[(c,d)\right]=\left[(a+c,b+d)\right].$

Using this definition and the properties for the natural numbers, one can prove that integer addition is both associative and commutative.

Integer multiplication

Definition: Multiplication for the integers, like addition, can be defined with a single axiom:

$\left[(a,b)\right]\left[(c,d)\right]=\left[(ac+bd,ad+bc)\right].$

Again, using this definition and the previously-proven properties of natural numbers, it can be shown that integer multiplication is commutative and associative, and furthermore that it is both left- and right-distributive with respect to integer addition.