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}\).
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|\).
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
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.
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\).
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.
Suppose \(a,b\in\mathbb{Z}\) with \(a\) and \(b\) not both 0.
We have \(\gcd(a,b)=\gcd(|a|,b)=\gcd(a,|b|)=\gcd(|a|,|b|).\)
Set \(c=\gcd(a,b)\), and take \(x,y\in\mathbb{Z}\) so that \(a=cx\), \(b=cy\); then \(\gcd(x,y)=1\).
For all \(x\in \mathbb{Z}\) we have \(\gcd(a,b)=\gcd(a,ax+b)\).
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)\).
Exercise.
□
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.\)
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.\)□
□
This theorem has several important corollaries (and one generalisation).
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)\).
Exercise.
□
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\).
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.
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.
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\).
The Extended Euclidean algorithm terminates and is correct.
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\).
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).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)\).