2. The Greatest Common Divisor

We have seen what it means for an integer to divide another. In this post we will explore division further and delve into the idea of the greatest common divisor, seeing how this gives us information on the solubility of linear equations in the integers. I will begin by formally defining some terms formally.

Definition 2.1: Sets, Elements and the Empty Set

A Set is a collection of objects. The objects that make up a set are called the Elements of the set. The Empty Set denoted $\emptyset$ is the unique set with no elements.

Example 2.1:

$\mathbb{Z}$ is the set of integers, $1729\in \mathbb{Z}$ means that 1729 is an element of the set of integers.
$\mathbb{N}$ is the set of natural numbers $1999\in \mathbb{N}$ .

Definition 2.2: Subset

Let A and B be sets. A is a Subset of B if every element of A is an element of B. This is denoted by A $\subseteq$ B.

Proposition 2.1: a|b and b|a implies |a|=|b|, i.e $a=\pm b$

The proof of this proposition is omitted for now! This requires ring theory as we need the fact that $\pm 1$ are the only units of the ring of integers. I will do some posts on rings in the future and will return to this proof then.

The Well-Ordering Principle is an axiom that states that every non-empty subset of $\mathbb{N}\cup \{0\}$ contains a least element, it is a property of the integers which is pretty intuitive.

Theorem 2.1: Given $a\in \mathbb{Z}$ and $b\in \mathbb{N}$ , there exists unique integers q and r satisfying $a=bq+r$ and $0\leq r<b$ . q is known as the quotient and r is known as the remainder.

Proof:

We will begin by proving the existence of such a pair of integers, and then we will go on to establish their uniqueness. Let us begin by defining the set $S:=\{a-xb: x\in \mathbb{Z}$ and $a-xb\geq 0\}$ . S is non-empty because if $a\geq 0$ by choosing m=0 we get $a-mb=a\geq 0$ which is indeed an element of S, and if $a<0$ by choosing m=a, we get $a-mb=a-ab=(-a)(b-1)\geq 0$ since $-a>0$ and $b>0$ . We have now shown that S is a non empty set (it is easy to see that it is a non empty subset of $\mathbb{N}\cup \{0\}$ ) which means we can now apply the well-ordering principle! So we have that S contains a least element, lets call it r. we have that $r\geq 0$ because $r\in S$ also by our construction of the set S we see that $r=a-qb$ so $a=qb+r$ . All that remains for us to show (to establish existence) is that $r<b$ (we already know that $r \geq 0$ because $r\in S$ ). We assume for contradiction that $r\geq b$ and let $r_{1}=r-b\geq 0$ , then $a=qb+r=qb + (r_{1}+b) = (q+1)b + r_{1}$ and so $a-(q+1)b=r_{1}\in S$ , $r_{1}=a-(q+1)r<a-qb=r$ so we have $r_{1}<r$ which is a contradiction because r is the least element of S.

We now prove that the pair q,r such that a=qb+r with $0\leq r<b$ is unique. Assume that there is another pair of integers q’ and r’ such that a=q’b+r’ with $0\leq r'<b$ . Then we have a=qb+r=q’b+r’ from which we obtain (q-q’)b=(r-r’). If q=q’ then we must have r=r’ and hence we have shown uniqueness, so it suffices for us to show that q=q’. So suppose for a contradiction that $q \neq q'$ , Then $b\leq|q-q'||b|$ because $|q-q'|\geq 1$ . We have that $b\leq|q-q'||b|=|r'-r|$ but recall that $0\leq r<b$ and $0\leq r'<b$ so $|r'-r|<b$ which means $b\leq|r'-r|<b$ which is a contradiction because |r-r’|cannot be greater than or equal to and less than b simultaneously.

QED

The theorem above is essentially saying that every integer, a, can be expressed in terms of a quotient and a remainder. This is the essence of division among the integers.

Theorem 2.2: Let $a,b\in \mathbb{Z}$ . Then there exists a unique $d\in \mathbb{N}\cup \{0\}$ and (non-unique) $x,y\in \mathbb{Z}$ such that;

d|a and d|b
if $e\in \mathbb{Z}$ , e|a and e|b then e|d.
d=ax+by (Bezout’s Identity)

Proof:

If a=b=0, then it is easy to check that we have d=0. So suppose that a and b are not both zero i.e requiring that $a^{2}+b^{2}>0$ . Let $S:=\{am+bn:m,n\in \mathbb{Z}$ and $am+bn>0\}$ since $a^{2}+b^{2}>0$ S is a non-empty subset of $\mathbb{N}\cup \{0\}$ . So we can now use the well ordering principle to establish a least element say, d>0. $d\in S$ so we can write $d=ax+by$ for some $x,y\in \mathbb{Z}$ . Also by theorem 2.1 we can write a=qd+r for some $q,r \in \mathbb{Z}$ with $0\leq r<d$ . We want to show that d|a so assume for contradiction that $r \neq 0$ , then $0<r=a-qd=a-q(ax+by)=(1-qx)a-qby$ therefore $r\in S$ . But r<d contradicting the fact d is the least element of S, so we must have that r=0 and hence d|a. The same argument shows that d|b.

Suppose that $e\in \mathbb{Z}$ , e|a and e|b. Then by the linearity of division (proposition 1.2) e divides any linear combination of a and b, recall that $d=ax+by$ for some $x,y\in \mathbb{Z}$ (i.e d is a linear combination of a and b) and so e|d.

It remains to show that d is unique, so suppose that there exists $f\in \mathbb{N}\cup \{0\}$ that also satisfies 1. and 2.. Then f|d and d|f and so $d=\pm f$ by proposition 2.1. But $d,f\geq 0$ so we have d=0, thus d is unique.

QED

Definition 2.3: Greatest Common Divisor

Let $a,b\in \mathbb{Z}$ , then the d given in theorem 2.2 is called the greatest common divisor of a and b, written as gcd(a,b). This is sometimes referred to as the highest common factor of a and b, hcf(a,b).

Bezout’s Identity is part 3 of theorem 2.2, here it is stated in terms of definition 2.3. Given $a,b\in \mathbb{Z}$ there exist (non-unique) $x,y\in \mathbb{Z}$ such that gcd(a,b)=ax+by.

Definition 2.4: Coprime

Let $a,b\in \mathbb{Z}$ , we say that a and b are coprime or relatively prime if gcd(a,b)=1.

Theorem 2.3: (Euclid’s Lemma) Let $a,b,c\in \mathbb{Z}$ . If a|bc and gcd(a,b)=1 then a|c.

Proof:

Suppose that a|bc and gcd(a,b)=1. By Bezout’s Identity there exist $x,y\in \mathbb{Z}$ such that 1=ax+by. Hence c=acx+bcy. But a|acx and a|bcy, so by the linearity of divisibility (proposition 1.2) a|(acx+bcy) which implies a|c(ax+by) i.e a|c because ax+by=1.

QED

The following theorem will show under what conditions some linear equations in the integers are soluble (i.e have a solution).

Theorem 2.4: Let $a,b,c\in \mathbb{Z}$ . The equation $ax+by=c$ is soluble with $x,y\in \mathbb{Z}$ if and only if gcd(a,b)|c.

Proof:

Let d=gcd(a,b). Then by the definition of the greatest common divisor d|a and d|b so if there exists $x,y \in \mathbb{Z}$ such that c=ax+by (i.e there exists a solution to the equation) then d|c by the linearity of divisibility (porposition 1.2). So suppose that the equation is soluble i.e that d|c. Then c=qd for some $q\in\mathbb{Z}$ . By Bezouts Identity there exists $x',y'\in\mathbb{Z}$ such that d=ax’+by’. Therefore we can write c=qd=aqx’+bqy’ and so x=qx’ and y=qy’ gives a suitable solution.