Chapter status:   🚧   draft   🚧

Basic Arithmetic

In this chapter, we cover a number of fundamental notions and results about arithmetic over integers, such as divisibility, greatest common divisors, and unique factorization. Most of them will be generalized in the chapter about rings. We will return to the axiomatic definition of integers in a later chapter (to wit, the set of integers is, up to isomorphism, the unique non-trivial, ordered, unitary commutative ring whose positive elements are well-ordered).

Contents

• Basic Definitions
• Divisibility
• Euclidean Division
• Greatest Common Divisor
• Computing GCDs and Bézout Relations
• GCDs and Ideals
• Prime Numbers

Basic Definitions

In all the following, we adopt the following notation and conventions:

• we let $\mathbb{N}$ denote the set of non-negative integers (also called natural numbers): $$\mathbb{N}:=\{0,1,2\dots \};$$
• we let ${\mathbb{N}}^{\ast }$ denote the set of positive integers: $${\mathbb{N}}^{\ast }:=\mathbb{N}\setminus \{0\}=\{1,2\dots \};$$
• we let $\mathbb{Z}$ denote the set of integers: $$\mathbb{Z}:=\{\dots ,-2,-1,0,1,2,\dots \}.$$

We will not explicitly formulate here all standard properties of addition, multiplication, and of the order relation and defer a more formal treatment to the chapter about rings.

We only state two salient properties of the integers: the cancellation law (a consequence of $\mathbb{Z}$ being a so-called integral domain) and the well-ordering principle (or well-ordering axiom), which is one of the axioms governing integers.

The absolute value of an integer $a\in \mathbb{Z},$ denoted $|a|,$ is defined as $$|a|:=\{\begin{array}{ll}a& \text{if }a>0\\ 0& \text{if }a=0\\ -a& \text{if }a<0.\end{array}$$

Proposition 3.1 (cancellation law for integers). Let $a,b,c\in \mathbb{Z}$ be integers such that $a\ne 0.$ Then $ab=ac$ implies $b=c.$

Proposition 3.2 (well-ordering axiom). Let $S\subseteq \mathbb{N}$ be a non-empty subset of $\mathbb{N}.$ Then $S$ contains a smallest element, i.e., there exists $m\in S$ such that for any $s\in S,$ $m\le s.$

It is immediate that the smallest element is necessarily unique.

Proposition 3.3. Let $S\subseteq \mathbb{N}$ be a non-empty subset of $\mathbb{N}.$ Then it has a unique smallest element.

Proof

Assume that $S$ has two smallest elements $m$ and $m^{\prime }.$ Then $m\le m^{\prime }$ (since $m$ is a smallest element) and $m^{\prime }\le m$ (since $m^{\prime }$ is a smallest element). Hence, $m=m^{\prime }.$

It is also the case that a finite non-empty subset of $\mathbb{N}$ (or $\mathbb{Z})$ has a largest element.

Proposition 3.4. Let $S\subseteq \mathbb{Z}$ be a finite non-empty subset of $\mathbb{Z}.$ Then $S$ contains a unique largest element, i.e., there exists a unique $M\in S$ such that for any $s\in S,$ $s\le M.$

Divisibility

Let $a,b\in \mathbb{Z}.$ We say that $a$ divides $b,$ or that $a$ is a divisor of $b,$ or that $b$ is a multiple of $a,$ denoted $a\mid b,$ if there exists $q\in \mathbb{Z}$ such that $b=qa.$

Let us list a number of basic properties of divisibility.

Proposition 3.5. For every $a,b\in \mathbb{Z},$ $$a\mid b⟺-a\mid b⟺a\mid -b⟺-a\mid -b.$$

Proof

Assume that $a\mid b.$ Then $b=qa$ for some $q\in \mathbb{Z}.$ This implies that $b=(-q)(-a),$ hence $-a\mid b.$ All other implications can be proven in a similar way.

Proposition 3.6. The only integers dividing $1$ are $1$ and $-1.$

Proof

Let $a\in {\mathbb{N}}^{\ast }$ be a positive divisor of $1.$ By [??], $a\ge 1.$ On the other hand, since $a\mid 1,$ there exists $q$ such that $aq=1.$ Clearly, $q$ must be positive and cannot be $0.$ Hence, by [??], $q\ge 1.$ Multiplying both sides by $a,$ we obtain $aq=1\ge a.$ Hence, we have both $a\le 1$ and $a\ge 1,$ which implies that $a=1.$

Proposition 3.7. For every $a,b,c\in \mathbb{Z}$ with $c\ne 0,$ $$a\mid b⟺ca\mid cb.$$

Proof

If $a\mid b$ then $b=qa$ for some $q\in \mathbb{Z}.$ This implies that $cb=q(ca)$ and hence $ca\mid cb.$

Conversely, assume that $ca\mid cb.$ Then $cb=q(ca)$ for some $q\in \mathbb{Z}.$ Since $c\ne 0,$ by the cancellation law for integers, $b=qa$ and hence $a\mid b.$

Proposition 3.8. For every $a,b\in \mathbb{Z},$ $$a\mid b\text{ and }b\mid a⟺a=\pm b.$$

Proof

If $a=\pm b$ then clearly $a\mid b$ and $b\mid a.$

Conversely, assume that $a\mid b$ and $b\mid a.$ Then $b=qa$ and $a=q^{\prime }b$ for some integers $q,q^{\prime }\in \mathbb{Z}.$ If $a=b=0$ then $a=\pm b$ and the conclusion holds. Assume now that either $a$ or $b$ is not zero. Let us consider the case $a\ne 0$ (the case $b\ne 0$ is similar). Multiplying $b=qa$ by $q^{\prime },$ we get $q^{\prime }b=q{q}^{\prime }a,$ hence $a=q{q}^{\prime }a.$ Since $a\ne 0,$ by the cancellation law for integers, this implies that $q{q}^{\prime }=1,$ i.e., $q^{\prime }$ divides $1.$ By Proposition 3.6, this implies $q^{\prime }=\pm 1,$ hence $a=\pm b.$

Proposition 3.9. For every $a,b,c\in \mathbb{Z},$ $$a\mid b\text{ and }b\mid c⟹a\mid c.$$

Proof

If $a\mid b$ then $b=qa$ for some $q\in \mathbb{Z}.$ Similarly, if $b\mid$c then $c=q^{\prime }b$ for some $q^{\prime }\in \mathbb{Z}.$ This implies that $c=q{q}^{\prime }a,$ i.e., $a\mid c.$

Divisibility defines an order relation over ${\mathbb{N}}^{\ast }:$

• it is reflexive since $a\mid a;$
• it is anti-symmetric since by Proposition 3.8, if $a\mid b$ and $b\mid a,$ then $a=\pm b,$ but for $a,b\in {\mathbb{N}}^{\ast }$ this implies $a=b;$
• it is transitive by Proposition 3.9.

Unlike $\le$ which is total, this order relation is only partial since there are integers $a$ and $b$ such that neither $a\mid b$ nor $b\mid a$ hold. These two order relations are "consistent" if the sense of the following proposition.

Proposition 3.10. For every $a,b\in {\mathbb{N}}^{\ast },$ $a\mid b⟹a\le b.$

Proof

Let $a,b\in {\mathbb{N}}^{\ast }$ such that $a\mid b.$ Then $b=qa$ for some $q\in \mathbb{Z}.$ We cannot have $q=0$ as this would imply $a=0.$ Moreover, $q\ge 0$ as $q<0$ would imply $b<0.$ Hence, $q\ge 1,$ which implies $b=qa\ge a.$

Euclidean Division

Proposition 3.11 (Euclid's division lemma). Let $a,n\in \mathbb{Z}$ be integers with $n>0.$ Then there exists unique integers $q$ and $r$ such that $$a=qn+r$$ and $0\le r<n.$ Moreover, $n\mid a$ if and only if $r=0.$

Proof

Let us show existence first. Consider the set $S$ defined as $$S=\{a-kn:k\in \mathbb{Z}\}\cap \mathbb{N}.$$ This set is non-empty: if $a\ge 0$ then $a=a-0n\in S$ whereas if $a<0$ then $a-an=a(1-n)\in S.$ By the well-ordering axiom, $S$ has a minimal element $r.$ Since $r\in S,$ there exists $q\in \mathbb{Z}$ such that $r=a-qn.$ Moreover, $r\ge 0$ by definition of $S.$ Assume that $r\ge n.$ Then $r-n\in S,$ contradicting the minimality of $r.$ Hence, $a=qn+r$ with $0\le r<n$ as claimed.

Let us now show uniqueness. Assume that $a=qn+r=q^{\prime }n+r$ with $0\le r<n$ and $0\le r^{\prime }<n.$ Then $$r-r^{\prime }=n(q^{\prime }-q)$$ meaning $r-r^{\prime }$ is a multiple of $n.$ But note that $$-n<r-r^{\prime }<n.$$ This implies that $r=r^{\prime }$ since the only multiple of $n$ in $\{-(n-1),\dots ,0,\dots ,n-1\}$ is $0.$ Hence, $n(q^{\prime }-q)=0,$ which by the cancellation law for integers implies that $q=q^{\prime }.$

Finally, let us show that $n\mid a$ if and only if $r=0.$ If $r=0,$ then $a=qn$ and hence $n\mid a.$ Conversely, if $n\mid a,$ then $a=q^{\prime }n$ for some $q^{\prime }\in \mathbb{Z}.$ But then uniqueness of $q$ and $r$ implies that $q=q^{\prime }$ and $r=0.$

The four integers $a,$ $n,$ $q,$ and $r$ each have a name:

• $a$ is called the dividend,
• $n$ is called the divisor,
• $q$ is called the quotient,
• $r$ is called the remainder.

Greatest Common Divisor

Let $a,b\in \mathbb{Z}$ be integers such that $a$ and $b$ are not both zero. A common divisor of $a$ and $b$ is an integer $d\in \mathbb{Z}$ such that $d$ divides both $a$ and $b.$ A greatest common divisor (GCD) of $a$ and $b$ is a common divisor $d$ of $a$ and $b$ such that $d\ge 0$ and any other common divisor of $a$ and $b$ divides $d.$

Note that this is different from the definition one usually encounters in high school, which is as follows. Consider the set $S$ of all common divisors of $a$ and $b.$ This set is non-empty since $1\in S.$ It is also finite since any common divisor $d$ of $a$ and $b$ satisfies $-a\le d\le a$ if $a\ne 0$ and $-b\le d\le b$ if $b\ne 0$ and $a$ and $b$ are not both zero. Then the GCD of $a$ and $b$ is defined as the largest element of $S,$ which by Proposition 3.4 exists and is unique.

The reason we prefer to former definition is that it is closer to the definition of a GCD in a commutative ring (the only difference is that condition $d\ge 0$ is dropped since in general, there might be no order relation over an arbitrary ring). Working with this definition, it is not immediately clear though that a greatest common divisor always exists and is unique (in fact, there exists commutative rings where two elements might not have a GCD), nor that it is equal to the GCD according to the later definition. The following proposition proves this, and more.

$${\Lambda }_{a,b}:=\{ua+bv:u,v\in \mathbb{Z}\}.$$ This set has the following interesting property: if $c\in {\Lambda }_{a,b},$ then every multiple $kc$ of $c$ also belongs to ${\Lambda }_{a,b}.$

Consider for example $a=6=2\cdot 3$ and $b=10=2\cdot 5.$ We can quickly establish (using any of the two definitions above) that the greatest common divisor of $6$ and $10$ is $2.$

Proposition 3.12 (Bézout's lemma). Let $a,b\in \mathbb{Z}$ be integers such that $a$ and $b$ are not both zero. Then there exists a unique greatest common divisor $d$ of $a$ and $b.$ Moreover, $d$ is the smallest non-negative integer which can be written as a linear combination of $a$ and $b.$ In particular, there exists integers $u,v\in \mathbb{Z}$ such that $$d=ua+vb.$$

Proof

Let us show uniqueness first. Assume that $a$ and $b$ have two GCDs $d$ and $d^{\prime }.$ Then $d\mid d^{\prime }$ and $d^{\prime }\mid d$ and hence by Proposition 3.8, one has $d=\pm d^{\prime }.$ Since a GCD must be positive, it follows that $d=d^{\prime }.$

Let us show existence by proving that the smallest non-negative integer which can be written as a linear combination of $a$ and $b$ in indeed their GCD. consider the set of all non-negative linear combinations of $a$ and $b,$ namely $$S:=\{ua+vb:u,v\in \mathbb{Z}\}\cap {\mathbb{N}}^{\ast }.$$ This set is non-empty. Indeed, assume that $a\ne 0$ (the case $b\ne 0$ is similar). Then either $a$ or $-a$ is in $S.$ By the well-ordering axiom, $S$ has a minimal element $d.$ We claim that $d$ is the GCD of $a$ and $b.$

First, we clearly have $d\ge 0.$ Second, let us show that $d$ is a common divisor of $a$ and $b.$ For this, we will show the following stronger statement: every element in $S$ is divisible by $d.$ Since $a\in S$ and $b\in S,$ this will imply in particular that $d$ divides both of them. Let $c=ua+vb$ be any element in $S.$ Since $d\in S,$ let us also write $d=u_{0}a+v_{0}b.$ By Euclid's division lemma, there exists $q$ and $r$ with $0\le r<d$ such that $$c=qd+r.$$ Then $$\begin{array}{rl}r& =c-qd\\ & =ua+bv-q(u_{0}a+b_{0}v)\\ & =(u-q{u}_0)a+(v-q{v}_0)b.\end{array}$$ Hence, $r\in S.$ But since $0\le r<d$ and $d$ is the minimal element of $S,$ one must have $r=0.$ Hence, $c=qd,$ i.e., $d$ divides $c.$

It remains to show that every common divisor $d^{\prime }$ of $a$ and $b$ divides $d.$

The greatest common divisor of $a$ and $b$ is denoted $\gcd (a,b)$ (or sometimes $(a,b)$ but this notation is confusing and will not be used here). By convention, although the set of common divisors of $a=0$ and $b=0$ is $\mathbb{Z},$ $\gcd (0,0)$ is defined as $0$ (we will see why this makes sense when relating GCDs and ideals).

Expressing the GCD as a linear combination of $a$ and $b,$ i.e., writing $$\gcd (a,b)=ua+vb$$ with explicit values $u,v\in \mathbb{Z}$ is often called a Bézout relation.

Two integers $a,b\in \mathbb{Z}$ are said coprime or relatively prime if $\gcd (a,b)=1,$ which is equivalent to $a$ and $b$ having only $1$ and $-1$ as common divisors.

Proposition 3.13. Let $a,b\in \mathbb{Z}.$ Then $a$ and $b$ are coprime if and only if there exists $u,v\in \mathbb{Z}$ such that $$ua+vb=1.$$

Proof

If $a$ and $b$ are coprime, then existence of $u,v\in \mathbb{Z}$ such that $ua+bv=1$ is established by Proposition 3.12. Conversely, assume that there exists $u,v\in \mathbb{Z}$ such that $ua+bv=1.$

Computing GCDs and Bézout Relations

The GCD can be computed using Euclid's algorithm. It relies on the following lemma.

Proposition 3.14. Let $a,b\in \mathbb{Z}$ such that $a$ and $b$ are not both zero. Then, for any $k\in \mathbb{Z},$ $$\gcd (a+kb,b)=\gcd (a,b).$$

Proof

GCDs and Ideals

In this section, we give another interpretation of GCDs in terms of ideals of $\mathbb{Z}.$ As pretty much any notion we encounter in this chapter, ideals can be defined for any ring.

A subset $\mathbb{I}\subseteq \mathbb{Z}$ of the integers is called an ideal of $\mathbb{Z}$ if it satisfies the following properties:

Proposition 3.15. Let $a,b\in \mathbb{Z}.$ Then $$a\mathbb{Z}+b\mathbb{Z}=\gcd (a,b)\mathbb{Z}.$$

Prime Numbers