5.1 Greatest common divisor

While we can not do division in general, there are cases when we can divide b \in \mathbb{Z} by a \in \mathbb{Z}.

Definition 5.1:
For a,b\in\mathbb{Z}, we say that a divides b, denoted by a\mid b, if \exists\, c\in\mathbb{Z} such that b=ac. That is b \in a\mathbb{Z} = \{ax: x \in \mathbb{Z}\}. In this case we say a is a divisor of b.
Remark:
We negate the above definition to say that a does not divide b, (or a is not a divisor of b) denoted by a\nmid b, if \forall\,c\in\mathbb{Z} we have b\not=ac. That is b\notin a\mathbb{Z}.
Interest:

Notice that if we tried to extend this definition into \mathbb{Q}, we will find that for all a\in\mathbb{Q}\setminus\{0\}, b\in \mathbb{Q} we have a\mid b.

Note that if b\neq 0 then a\mid b implies |a|\leq |b|.

Theorem 5.2: (Division Theorem)

Let a,b \in \mathbb{Z} with a\neq 0. Then there exists a unique q,r\in \mathbb{Z} such that b=aq+r and 0\le r<|a|.

We call q the quotient and r the remainder

Proof.

Let A = \{b-ak: k \in \mathbb{Z} \wedge b-ak \in \mathbb{Z}_{\geq 0}\}. By definition A\subseteq \mathbb{Z}_{\geq 0}. If b\geq0, taking k=0 gives b\in A. If b<0, taking k=a\cdot b gives b-a^2b = b(1-a^2) \in A, since b<0 and (1-a^2)\leq 0. So A is non-empty, and contains a least element. Let this element be r and the corresponding k be q. Since r\in A, we know r\geq 0. We show r<|a| by contradiction. Suppose r\geq |a| and consider r>r-|a|\geq 0. Note that r-|a| = (b-ak)-|a| =b-(k\pm 1)a \in A, which contradicts the minimality of r. Hence r<a as required.

It remains to show that r and q are unique. For the sake of a contradiction, suppose there exists q_1,q_2,r_1,r_2 \in \mathbb{Z} with 0\leq r_1 < r_2 <|a| (without loss of generality, we assume r_1<r_2 as they are not equal) and b = q_ia+r_i for i=1,2. Then q_1a+r_1 = q_2a+r_2 means r_2-r_1 = q_1a-q_2a = a(q_1-q_2). Since q_1,q_2\in \mathbb{Z}, we have q_1-q_2 \in \mathbb{Z}, so a|(r_2-r_1), i.e. (r_2-r_1) \in a\mathbb{Z}. But 0<r_2-r_1 < |a| and there are no integers between 0 and |a| which is divisible by a. This is a contradiction to our assumption. Hence r_1=r_2, and we deduce that q_1=q_2.

Note that the division theorem shows that a|b if and only if the remainder is equal to 0.

Because we have a notion of division, the following definition is natural.

Definition 5.3:
Let a,b,c\in\mathbb{Z}. We say that c is a common divisor of a and b if c\mid a and c\mid b.

Note that 1 is always a common divisor of a and b, and if a\not=0, no integer larger than |a| can be a common divisor of a and b.

Definition 5.4:
Let a,b\in\mathbb{Z} with a,b not both equal to 0. We define the greatest common divisor of a and b, denoted by \gcd(a,b) (or \text{hcf}(a,b) for highest common factor), to be largest positive divisor that divides both a and b.
Remark:
Note that \gcd(0,0) does not exist since every integer is a divisor of 0. However, for a\in\mathbb{Z} with a\not=0, we have that \gcd(a,0)=|a|.
Definition 5.5:

Let a_1,a_2,\dots,a_n \in \mathbb{Z} with not all the a_i’s being equal to 0. We define the greatest common divisor of a_1 to a_n, denoted by \gcd(a_1,\dots,a_n), to be the largest positive divisor that divides a_i for all 1\leq i \leq n.

The following lemma showcases different properties of the gcd.

Lemma 5.6:

Suppose a,b\in\mathbb{Z} with a and b not both 0.

  1. We have \gcd(a,b)=\gcd(|a|,b)=\gcd(a,|b|)=\gcd(|a|,|b|).

  2. Set c=\gcd(a,b), and take x,y\in\mathbb{Z} so that a=cx, b=cy; then \gcd(x,y)=1.

  3. For all x\in \mathbb{Z} we have \gcd(a,b)=\gcd(a,ax+b).

  4. For all a_1,a_2,a_3 \in \mathbb{Z} we have \gcd(a_1,a_2,a_3) = \gcd(\gcd(a_1,a_2),a_3).

Proof.

Exercise.

Theorem 5.7:

Let a,b\in\mathbb{Z} with a,b not both equal to 0, and let \gcd(a,b)=c. Then there exists s,t\in\mathbb{Z} such that c=as+bt.

Proof.

Let A be the set A=\{as+bt: (s,t\in\mathbb{Z}) \wedge (as+bt>0)\ \}.

By taking s=a, t=b we see that a^2+b^2 \in A, hence A is a non-empty subset of \mathbb{Z}_+. By the Well Ordering Principle, it has a minimal value. We denote this minimum value by d and take s,t\in\mathbb{Z} such that d=as+bt. Note that since c\mid a and c\mid b, we have c|(as+bt), so c|d. Hence, c\le d.

Now, using Theorem 5.2 on a and d, let q,r\in\mathbb{Z} be such that a=dq+r with 0\le r<d. Then r=a-dq=a-(as+bt)q=a(1-sq)+b(-tq). If r>0, then r\in A with r<d, contrary to how we chose d. Hence, we must have that r=0, which means d\mid a. Similarly, we can show that d\mid b, so d is a common divisor of a and b. Since c=\gcd(a,b), we have that d\le c.

Since c\le d and d\le c, it follows that c=d. Hence, \gcd(a,b)=c=d=as+bt.

Proof techniques:
Note here that we proved x=y by showing x\leq y and y\leq x. This trick is often exploited when tryingt to prove two numbers are the same.

Remark:
Note that s and t are not unique at all. Suppose that s,t \in \mathbb{Z} are such that \gcd(a,b)=as+bt, then using the fact that ab+b(-a)=0, we see that \gcd(a,b)=as+bt+(ab+b(-a))=a(s+b)+b(t-a), i.e., s+b, t-a\in \mathbb{Z} also satisfies Theorem 5.7.

This theorem has several important corollaries (and one generalisation).

Corollary 5.8:

Let a,b,c\in\mathbb{Z} with c\neq 0.

  • If c\mid ab and \gcd(b,c)=1, then c\mid a.

  • If c\mid a and c \mid b then c\mid \gcd(a,b).

Proof.

Exercise.

Corollary 5.9:

Let a_1,\dots,a_n\in\mathbb{Z}, not all a_i’s equal to 0. Then there exists s_1,\dots,s_n \in \mathbb{Z} such that \gcd(a_1,\dots,a_n) = a_1s_1+\dots+a_ns_n.

Proof.

Exercise.

Note that the proof of Theorem 5.7 only shows the existence of s and t but doesn’t give us a way to find/calculate the value of s and t (that is the proof is not constructive). To find s and t we need to use an algorithm. An algorithm is a logical step-by-step procedure for solving a problem in a finite number of steps. Many algorithms are recursive, meaning that after one or more initial steps, a general method is given for determining each subsequent step on the basis of steps already taken.

Etymology:

The word algorithm comes from Abu Ja’far Muhammad ibn Musa Al-Khwarizmi (Arabic Mathematician, 780-850). Al-Khwarizmi (meaning “from Khwarazm”) wrote a book detailing how to use Hindu-Arabic numerals. When this book was translated for Europeans, it was given the Latin name Liber Algorismi meaning “Book of al-Khowarazmi”. As a consequence, any manipulation of Arabic numerals (which are the ones we use nowadays) was known as an algorism. The current form algorithm is due to a “pseudo-etymological perversion” where algorism was confused with the word arithmetic to give the current spelling of algorithm.

It is interesting to note that Al-Khwarizmi also wrote the book Hisab al-jabr w’al-muqabala. We have al-jabr comes from the Arabic al- meaning “the” and jabara meaning “to reunite”, so his book was on “the reunion of broken part”, i.e. how to solve equations with unknowns. When the book made its way to Europe, Europeans shorten the Arabic title to algeber. Over time, this mutated to the word algebra which is currently used.

Algorithm 5.10: (Extended Euclidean algorithm)

Input: Integers a and b such that a> 0.

Output: Integers s, t and \gcd(a,b) such that \gcd(a,b)=as+bt.

Algorithm:

  • Step 0: Set s_0=0, t_0=1 and r_0 = a

  • Step 1: Set s_1=1 and t_1=0. Find unique q_1, r_1 \in \mathbb{Z} such that b = aq_1+r_1 and 0\leq r_1 < a. If r_1 = 0 then proceed to the final step, else go to Step 2.

  • Step 2: Set s_2=s_0-q_1s_1 and t_2=t_0-q_1t_1. Find unique q_2, r_2 \in \mathbb{Z} such that a = r_1q_2+r_2 and 0\leq r_2<r_1. If r_2=0 then proceed to the final step, else go to Step 3.

  • Step k (for k\geq 3): Set s_k=s_{k-2}-q_{k-1}s_{k-1} and t_k=t_{k-2}-q_{k-1}t_{k-1}. Find unique q_k, r_k \in \mathbb{Z} such that r_{k-2} = r_{k-1}q_k + r_k and 0\leq r_k < r_{k-1}. If r_k = 0 then proceed to the final step, else go to Step k+1.

  • Final Step: If the last step was Step n (with n\geq 1) then output r_{n-1}=\gcd(a,b), s_n = s and t_n = t.

Proposition 5.11:

The Extended Euclidean algorithm terminates and is correct.

Proof.

Notice that after k steps, we have a>r_1>r_2>\cdots>r_k\ge 0. Hence, the algorithm must terminate after at most a steps.

If it terminates after Step 1 (i.e. r_1=0), then \gcd(a,b)=a=r_0. Furthermore a = a\cdot 1+ b\cdot 0 = as_1+bt_1.

So suppose the algorithm terminates after n steps, for n>1. We note that r_1=b-a\cdot q_1 and r_2=a-r_1\cdot q_2, and for 3\le k<n, we have r_k=r_{k-2}-r_{k-1}\cdot q_k. Then by Lemma 5.6, we have \gcd(a,b)=\gcd(a,r_1)=\gcd(r_1,r_2)=\cdots=\gcd(r_{n-1},r_n)=\gcd(r_{n-1},0)=r_{n-1}.

Finally, we prove by (strong) induction that as_n+bt_n = r_{n-1} at every stage of the algorithm. So let P(n) be the statement that as_n+bt_n = r_n. We have seen above that P(1) holds. We also have s_2=-q_1 and t_2=1. So r_1=b-a\cdot q_1 = a\cdot (-q_1)+b\cdot 1 = as_2+bt_2. So P(2) holds. Assume P(n) holds for all n<k, then we have \begin{align*} as_{k}+bt_{k}&=a(s_{k-2}-q_{k-1}s_{k-1})+b(t_{k-2}-q_{k-1}t_{k-1}) \\ &=(as_{k-2}+bt_{k-2})+q_{k-1}(as_{k-1}+bt_{k-1}) \\ &=r_{k-3}-r_{k-2}\cdot q_{k-1} \\ &= r_{k-1}. \end{align*} Hence P(k) holds, so by strong induction P(n) holds.

Notice that if a<0, then apply the above algorithm to |a| and b then use -s instead of s.

History:

Theorem 5.7 is often known as Bezout’s identity named after Étienne Bézout (French mathematician 1730–1783), while the Extended Euclidean algorithm is named after Euclid of Alexandria (Greek mathematician, 325BC-265BC). One might wonder at the gap between between those two mathematicians given Bezout’s identity follows immediately from the algorithm.

In his series of books The Elements, Euclid gives an algorithm to find the gcd of two numbers. The algorithm uses the fact that \gcd(a,b) = \gcd(a,b-a) and Euclid uses repeated subtractions. This was improved to give the above algorithm without s_k and t_k. Around 1000 years later, Aryabhata (Indian mathematician, 476-550) wrote the book Aryabhatiya which contained a version of the Extended Euclidean Algorithm. It is not clear when the algorithm was known in Europe, but it was used by Claude Gaspar Bachet de Méziriac (French mathematician, 1581-1638), who was alive a full 100 years before Bezout. What Bezout did was to show that a version the Extended Euclidean Algorithm could be used for polynomials and a version of Bezout’s identity existed for polynomials (You can find out how polynomial rings are similar to \mathbb{Z} in units like Algebra 2).

Example:

We want to compute \gcd(323,1451) and find s,t\in\mathbb{Z} such that \gcd(1451,323)=323s+1451t. We go through the algorithm using the following table

k s_k t_k Calculation q_k r_k
0 0 1 - - -
1 1 0 1451=323\cdot 4+159 4 159
2 0-1\cdot 4 = -4 1-0\cdot4=1 323=159\cdot 2+5 2 5
3 1-(-4)\cdot2=9 0-1\cdot2=-2 159=5\cdot 31+4 31 4
4 -4-9\cdot31 = -283 1-(-2)\cdot31=63 5=4\cdot 1+1 1 1
5 9-(-283)\cdot1=292 -2-63\cdot1=-65 4=1\cdot 4+0 4 0

Hence \gcd(323,1451)= 1 = 323\cdot(292)+1451\cdot(-65).