Chapter 2 Divisibility and Euclid’s Algorithm
Let \(d, a\) be integers. (The integers are the positive or negative ‘’whole numbers’’ - these are all the numbers you can get by adding or subtracting 1 to 0 as many times as necessary)
The processes of addition, subtraction and multiplication on the integers are examples of binary operations. That is to say, if we add, subtract or multiply two integers, the result is another integer. Division, on the other hand, is not a binary operation on the set of integers.
We all know that \(2\) is a factor, (or in other words a divisor) of \(6\), but that it is NOT a divisor of \(7\). It is tempting to say that this is because \(6/2\) is a whole number but \(7/2\) is not, and if we are working in the world of fractions (or the real numbers or the complex numbers) this would make sense. However the very fact that \(7/2\) is not an integer means that the operation of division is not defined in general for pairs of integers unless we do work in these worlds.
In this course we want to work largely inside the set of integers without reference to the larger number systems, so we won’t usually be allowed to divide and we therefore try to avoid using arguments involving the concept of division, wherever possible.
This raises the question of how to define a factor or a divisor without referring to division. We do this as follows:
Since \(2.3=6\), \(2\) is a divisor of \(6\). On the other hand if we consider the equation \(2b=7\) we see that the left hand side is even and the right hand side is odd so there are no solutions, hence \(2\) is not a divisor of \(7\). We denote this by \(2\not|\ \ 7\).
The fact that not every integer is a divisor of every other integer is what makes number theory interesting. The question of which integers divide a given integer is of crucial importance as the factorisation of large numbers plays a key role in modern cryptography and secure communications. It can be reduced to the question of finding the prime factorisation of a number. While in general it is hard to do this there is a related problem that is a lot easier to solve, and we will start with that.
Let \(a,b,d\) be integers.
If \(d| a\) and \(d| b\) we say that \(d\) is a common divisor (or common factor) of \(a\) and \(b\); for instance, \(1\) is a common divisor of any pair of integers \(a\) and \(b\).
The greatest common divisor (or highest common factor) of \(a\) and \(b\) is the unique integer \(d\) satisfying
- \(d| a\) and \(d| b\) (so that \(d\) is a common divisor),
- If \(c| a\) and \(c| b\) then \(c\le d\) (so that no common divisor exceeds \(d\)).
We denote the greatest common divisor of \(a,b\) by \(\gcd(a,b)\). Some books also call this the highest common factor and denote it \(\text{hcf}(a,b)\).
Find the gcd of \(a=30\) and \(b=42\):
The set of divisors of \(30\) is \(X=\{\pm1, \pm 2, \pm 3, \pm 5, \pm 6, \pm 10, \pm 15, \pm 30\}\).
The set of divisors of \(42\) is \(Y=\{\pm1, \pm 2, \pm 3, \pm 6, \pm 7, \pm 14, \pm 21, \pm 42\}\).
The set of common divisors of \(30\) and \(42\) is \(X\cap Y = \{\pm1, \pm 2, \pm 3, \pm 6\}\)
This is fine for relatively small integers such as 30 and 42, but how would we find the greatest common divisor of \(765432\) and \(56789\)?
The Euclidean Algorithm
](Euclid.png)
For larger integers we can automate the process using one of the oldest algorithms in mathematics, Euclid’s algorithm:
Euclid’s algorithm (published in Book VII of Euclid’s Elements around 300 BC) is based on the following simple observation:
If \(a,b\) are integers with \(a>b\) then \(\gcd(a, b)=\gcd(a-b, b)\).
By repeated application of Euclid’s observation, we can reduce the size of the numbers involved in our calculations.
For example, suppose we wish to calculate \(\gcd(765432,56789)\). Euclid’s observation says that as \(765432 - 56789 = 708643\) then \(\gcd(765432,56789) = \gcd(708643,56789)\). But then \(708643 - 56789 = 651854\) and so \(\gcd(765432,56789) = \gcd(651854,56789)\). We continue our calculations in this fashion:
\[\begin{eqnarray*} 765432 - 56789 &= &708643\\ 708643 - 56789 &=& 651854\\ 651854 -56789&=& 595065\\ \vdots\\ \end{eqnarray*}\]
We can speed this process up slightly by observing that if \(a,b\) are integers with \(a>b\) then
\[\begin{eqnarray*} \gcd(a, b)&=&\gcd(a-b, b)\\ &=&\gcd(a-2b, b)\\ \vdots\\ &=&\gcd(r,b)\\ \end{eqnarray*}\]
where \(r\) is the remainder when we divide \(a\) by \(b\).
Now we can subtract 56789 from 765432, 13 times.
\[\begin{eqnarray*} 765432 - 13 * (56789) &= &27175\\ \gcd(765432,56789)&=&\gcd(56789,27175)\\ \end{eqnarray*}\]
We then repeat the process with the two smaller numbers 56789 and 27175.
\[\begin{eqnarray*} 765432 - (13) * (56789) &= &27175\\ \gcd(765432,56789)&=&\gcd(56789,27175)\\ 56789 - (2) * (27175) &=& 2439\\ \gcd(765432,56789)&=&\gcd(27175,2439)\\ \end{eqnarray*}\]
Carrying on in this way we can deduce the value of the \(\gcd(765432,56789)\).
\[\begin{eqnarray*} 765432 - (13) * (56789) &= &27175\\ 56789 - (2) * (27175) &=& 2439\\ 27175 - (11) * (2439) &=& 346\\ 2439 - (7) * (346) &=& 17\\ 346 - (20) * (17) &=& 6\\ 17 - (2) * (6) &=& 5\\ 6 - (1) * (5) &=& 1\\ 5 - (5) * (1) &=& 0.\\ \end{eqnarray*}\]
So gcd of \(765432\) and \(56789\) is \(1\).
At each stage of the process above, given integers \(a\) and \(b\), we have to find integers \(q\) and \(r\) such that \[a=qb+r\qquad\text{and}\qquad 0\le r<b.\] Later, we shall prove that this is always possible, but for now we notice that
\[\frac{a}{b}=q+\frac{r}{b}\qquad\text{and}\qquad 0\le\frac{r}{b}<1,\] \(q\) is the integer part \(\lfloor a/b\rfloor\) of \(a/b\), the greatest integer \(i\le a/b\)
This makes it easy to calculate \(q\), and then to compute \(r\). For example, \[ 765432/56789 = 13.478525\ldots \] and so \(q = 13\). To find \(r\), we multiply the decimal part, \(0.478525\ldots\) by \(56789\) to get \(r=27175\). We shall consider lots of example later in this chapter.
For now, we want to focus on proving that Euclid’s observation and the resultant algorithm is true and gives the correct result.
Recall our definition of a divisor
We say that an integer \(d\) is a divisor of the integer \(a\) if and only if there is an integer \(b\) such that \(a=db\).
Notice that the definition is phrased entirely using properties of the integers encoded in the axioms given in Chapter 1.
Now what can we say about divisors using the axioms and the definitions?
- Every integer divides \(0\). This is because \(0=d.0\). Notice that this is not one of our axioms but we can deduce it from the axioms, and will do so in one of the tutorial sheets for the course.
- \(1\) divides every integer. This is because \(a=1.a\) from axiom [A2].
- Every integer divides itself. This is because \(a=a.1\) from axiom [A2].
- \(0\) does not divide any integer except itself. If \(a=0.b\) then \(a=0\), from the first of these observations.
We have already mentioned that we shall attempt to avoid using division whenever possible. The following important result will often help us in this task.
If \(m,n,p\) are integers with \(m.p=n.p\) then either \(p=0\) or \(m=n\).
Proof. Since \(m.p=n.p\) we have \(m.p-n.p=n.p-n.p=0\) by axiom A3.
By axiom A4 we get \(p.m-p.n=0\) and by axiom A6 we get \(p(m-n)=0\).
Now by axiom A7 either \(p=0\) or \(m-n=0\), and so \(p=0\) or \((m-n)+n=0+n\) which means \(m + (-n+n)=n\) by A8, A9, A2 and A5. Hence \(m=m+0=m+(n-n)=n\) by A2, A3 and A4 as required.
Let \(a,b\) and \(c\) be integers.
- If \(a| b\) and \(b| c\) then \(a| c\).
- If \(a| b\) and \(c| d\) then \(ac| bd\).
- If \(m\neq 0\), then \(a| b\) if and only if \(ma| mb\).
- If \(d| a\) and \(a\ne 0\) then \(|d| \le|a|\).
Proof. Let \(a,b\) and \(c\) be integers.
- If \(b=ma\) for some integer \(m\), and \(c=nb\) for some integer \(n\), then \(c=n(ma)=(nm)a\) and \(nm\) is an integer.
- If \(b=ma\) for some integer \(m\) and \(d=nc\) for some integer \(n\), then \(bd=(ma)(nc)=((ma)n)c=(m(an))c=(m(na))c=((mn)a)c =(mn)(ac)\).
- If \(ma|mb\) then there is an integer \(k\) such that \(mb=k(ma)=m(ka)\).
Since \(m\neq 0\) we can apply the cancellation lemma to see that \(ka=b\). It follows that \(a|b\) as required.
Now suppose that \(a|b\). Since \(m|m\) and \(a|b\) it follows that \(ma|mb\) by part 2. - If \(a=md\) for some integer \(m\) then \[|a|=|md|=|m||d|.\] Since \(a\neq 0\) then \(m\neq 0\) and so \(|m|\geq 1\). Hence \(|a|\geq |d|\).
This concludes the proof.
Notice that in part (4), we have mentioned that \(|md| = |m||d|\). This is not one of the axioms, but can be deduce from the axioms and will appear as an example in one of the tutorial sheets for the course.
Let \(a_1,\ldots, a_k, u_1, \ldots, u_k\) be integers. We shall refer to an expression of the form \[ a_1u_1+\cdots+a_ku_k \] as a linear combination of the integers \(a_1,\ldots, a_k\).
Let \(a_1,\ldots, a_k, u_1, \ldots, u_k, a, b, c\) be integers
- If \(c\) divides \(a_1, \ldots, a_k\), then \(c\) divides any linear combination of the integers \(a_1,\ldots, a_k\).
- \(a| b\) and \(b| a\) if and only if \(a=\pm b\).
Proof. Let \(a_1,\ldots a_k, u_1, \ldots u_k, a, b, c\) be integers
- If \(c\) divides \(a_i\) then \(a_i=q_ic\) for some integers \(q_i\) (\(i=1, \ldots, k\)). Then \(a_1u_1+\cdots+a_ku_k=q_1cu_1+\cdots+q_kcu_k=(q_1u_1+\cdots+q_ku_k)c\), and as \(q_1u_1+\cdots+q_ku_k\in\mathbb Z\) (since \(q_i, u_i\in\mathbb Z\)) we see that \(c| (a_1u_1+\cdots+a_ku_k)\).
NOTE:
The fact that we can “pull” the factor of \(c\) out of this expression is due to the distributive law (axiom A6), the commutative law (axiom A4) and the associative law (axiom A5) for integer multiplication and addition.
- If \(a=\pm b\) then \(b=qa\) and \(a=q'b\) where \(q=q'=\pm 1\). Hence \(a| b\) and \(b| a\).
Conversely, suppose that \(a| b\) and \(b| a\), so \(b=qa\) and \(a=q'b\) for some integers \(q\) and \(q'\).
If \(b=0\) then the second equation gives \(a=0\), and so \(a=\pm b\) as required. Suppose now that \(b\neq 0\).
Combining the two equations, we have \(1.b = b = qq'b\), and so by the cancellation lemma, and since \(b\neq 0\), we deduce that \(qq'=1\).
Hence \(q\) and \(q'\) both divide \(1\), and by Lemma 2.5(4), \(|q|\le |1|=1\) and \(|q'|\le 1\).
Hence \(q\) and \(q'\) are both in the set \(\{-1, +1\}\) and \(a=\pm b\).
We get the following very useful Corollary for the case \(k=2\).
If \(c\) divides \(a\) and \(b\), then \(c\) divides \(au+bv\) for all integers \(u\) and \(v\).
We are now in a position to prove Euclid’s observation mentioned earlier.
If \(a,b\) are integers with \(a=qb+r\) and \(0\le r<b\) then \(\gcd(a,b)=\gcd(b, r)\).
Proof. By Corollary 2.7, any common divisor of \(b\) and \(r\) also divides any integer of the form \(ub+vr\).
Now if \(a=qb+r\) we can put \(u=q\) and \(v=1\) to see that any common divisor of \(b\) and \(r\) is also a divisor of \(a\). Hence any common divisor of \(b\) and \(r\) is also a common divisor of \(a\) and \(b\).
Conversely, any common divisor of \(a\) and \(b\) also divides \(a-qb\) (again by Corollary 2.7, with \(u=1\) and \(v=-q\)).
Hence any common divisor of \(a\) and \(b\) is also a common divisor of \(b\) and \(r=a-qb\).
Thus the two pairs \(a, b\) and \(b, r\) have the same common divisors, so they have the same greatest common divisor.
The Remainder Theorem
In order to be able to apply Lemma 2.8, we require the following important theorem.
If \(a\) and \(b\) are integers with \(b>0\), then there is a unique pair of integers \(q\) and \(r\) such that \(a=qb+r\text{ and } 0\le r<b.\)
NOTES:
- We refer to the value \(q\) as the quotient and \(r\) as the remainder.
- This result is also referred to as the division algorithm.
- We say that \(x<y\) or \(y>x\) if \(x\le y\) and \(y\ne x\). The set \(\{b\in \mathbb Z\mid b>0\}\) is called the natural numbers and denoted \(\mathbb N\)
- Without the constraint \(0\le r<b\) we could still assert existence of \(q\) and \(r\), but we could not assert uniqueness.
- What happens if we drop the constraint \(b>0\)?
Proof. Theorem 2.9 asserts that something exists and that it is unique. We have to prove both:
Existence: It is easy to see that there are integers \(q,r\) such that \(a=qb+r\). For example we may put \(q=0\) and \(r=a\). We need to show that we can choose \(q,r\) so that \(0\le r<b\).
Let \[S=\{a-qb\mid q\in{\mathbb Z }\}=\{a, a\pm b, a\pm 2b, \ldots\}.\]
We first want to show that \(S\) contains a non-negative integer.
Putting \(q=-|a|\) we get \(u=a+|a|b\in S\)
Since \(b>0\), \(u=a+|a|b\ge a+|a|\ge 0\).
Now we want to pick out the least non-negative element of \(S\) and show that it is less than \(b\). To do so we need to know that \(S\) has a least non-negative element!
The Well Ordering Principle
“Given any non-empty subset of non-negative integers there is a unique least element.”
As we saw above \(S\) contains the non-negative integer \(a+|a|b\), so by the well-ordering principle, (applied to the set of non-negative integers in \(S\)), the set \(S\) has a least non-negative element \(r\).
It remains to show that \(r<b\). We do so using a proof by contradiction.
If \(r\geq b\) then \(r-b\ge0\). But then \(a=qb+(b+r-b)=(q+1)b+(r-b)\) so \((r-b)\) is also in \(S\).
But the non-negative integer \(r-b\) is less than \(r\) since \(b>0\); this contradicts the minimality of \(r\), so \(r<b\) after all.
Uniqueness: Suppose that
\[a=qb+r=q'b+r'\text{ with }0\le r<b\text{ and }0\le r'<b\]
with \(q\neq q'\). Then \(r-r'=(q'-q)b\).
Since \(q'\neq q\) then \(| q'-q| \geq 1\), so \(| r-r'| \geq b\). This is impossible since \(r\) and \(r'\) lie between \(0\) and \(b-1\) inclusive. Hence \(q'=q\) and so \(r'=r\).
Generalising the result
When \(b<0\) we need to adjust the statement a bit.
If \(a\) and \(b\) are integers with \(b<0\), then there is a unique pair of integers \(q\) and \(r\) such that \[a=qb+r\qquad \text{ and }\qquad 0\le r<-b.\]
To prove this it is possible to imitate the argument in Theorem 2.9, but this is not necessary:
\[b<0\Rightarrow -b>0,\]
so by Theorem 2.9 there are unique integers \(q^*\) and \(r\) such that \(a=q^*(-b)+r\) with \(0\le r<-b\). Putting \(q=-q^*\) we have \(a=qb+r\), with \(0\le r< -b\).
Furthermore if \(a=qb+r=q'b+r'\) with \(0\le r,r'<-b\) then \(a=-q\times-b+r=-q'\times-b+r'\) so by Theorem 2.9, \(-q=-q'\) and \(r=r'\). It follows that \(q=q'\) and \(r=r'\) as required.
If \(a\) and \(b\) are integers with \(b\neq 0\), then there is a unique pair of integers \(q\) and \(r\) such that \[a=qb+r\qquad\text{ and}\qquad 0\le r<| b|.\]
Let \(a\) and \(b\) be integers with \(b\ne0\). Show that there exists a unique pair of integers \(q\) and \(r\) such that \[ a = qb + r\qquad\text{ and } -|b|/2<r\le|b|/2. \]
The following example will prove useful in Chapter 4.
If \(n\) is a square then \(n\) leaves a remainder \(0\) or \(1\) when divided by \(4\).
Solution. Let \(n=a^2\).
According to Corollary 2.10 \(a=4q+r\) where \(r=0, 1, 2\) or \(3\), so that
\[n=(4q+r)^2= 16q^2+8qr+r^2.\]
- If \(r=0\) then \(n=4(4q^2+2qr)+0\),
- if \(r=1\) then \(n=4(4q^2+2qr)+1\),
- if \(r=2\) then \(n=4(4q^2+2qr+1)+0\),
- and if \(r=3\) then \(n=4(4q^2+2qr+2)+1\).
This completes the result.
Show that any number that is both a square and a cube leaves a remainder of either 0 or 1 when divided by \(7\).
Solution. Let \(a\) be an integer. By the Remainder Theorem there exists integers \(q\) and \(r\) such that \(a = 7q + r\) and \(0\le r\le 6\). Hence \[ a^2 = (7q+r)^2 = 49q^2 + 14qr + r^2 = 7(7q^2+2qr) + r^2. \] Then \(r^2\in\{0^2,\ldots, 6^2\} = \{0,1,4,9,16,25,36\}\). But \(9 = 7+2\), \(16 = 7\times2+2\), \(25=7\times3+4\), \(36=7\times5+1\) and so \(a^2 = 7q' + r'\) where \(r'\in\{0,1,2,4\}\).
Using a similar argument, we see that if \(b=7q+r\) then \[ b^3 = (7q+r)^3 = 343q^3 + 147q^2r + 21qr^2 + r^3. \] We can then easily check that \(r^3\) leaves a remainder of \(0,1\) or \(6\) on division by \(7\) and hence \(b^3 = 7q'' + r''\) where \(r''\in\{0,1,6\}\).
So if a number is both a square and a cube it must have a remainder of either 0 or 1 when divided by \(7\).
Proof of Euclid’s Algorithm
We are now in a position to prove that Euclid’s algorithm, both terminates, and produces the desired greatest common divisor. We use the remainder theorem to successively define the integers \(r_i\) so that \(r_1\) is the remainder upon dividing \(a\) by \(b\) and for \(i\geq 1\) each \(r_{i+1}\) is the remainder upon dividing \(r_{i-1}\) by \(r_{i}\). \[ \begin{array}{rclcr} a&=&q_1b+r_1&&0\le r_1<b\\ b&=&q_2r_1+r_2&&0\le r_2<r_1\\ r_1&=&q_3r_2+r_3&&0\le r_3<r_2\\ &\ldots&\\ r_{i-1}&=&q_{i+1}r_i+r_{i+1}&&0\le r_{i+1}<r_i\\ &\ldots&\\ r_{n-1}&=&q_{n+1}r_{n}+r_{n+1}&\qquad&0\le r_{n+1}<r_n\\ r_n&=&q_{n+2}r_{n+1}+0.\\ \end{array} \] In particular we have \(a\geq b>r_1>r_2>\ldots \geq 0\). By the well ordering principle this process stops, and by inspection we see it can only stop when the final remainder is \(0\).
By Lemma 2.8 we see that \[ \gcd(a,b)=\gcd(b,r_1)=\gcd(r_1,r_2)=\ldots \] and in general each pair \(r_i, r_{i+1}\) has the same greatest common divisor as the successor pair \(r_{i+1}, r_{i+2}\) so in particular (and by induction) \(\gcd(a, b)=\gcd(r_n,r_{n+1})=r_{n+1}\) as required.
Euclid’s algorithm for polynomials
A polynomial over the integers is a function like \(5x^3+2x^2+7x-4\) with integer coefficients. It’s degree is the highest power of the variable which arises in the expression. [There is a much more formal definition which can be given, but it agrees with this naive idea.]
The set of all integer polynomials shares certain similarities with the integers. In particular we can add, subtract and multiply polynomials just as we can integers, and these operations satisfy all the axioms [A1]-[A7], as the integers do. If we define an order on the polynomials, by saying that \(f\le g\) if and only if \(g\) has degree greater than or equal to the degree of \(f\) then the set of polynomials satisfies all the axioms [A1]-[A9] and ‘almost’ [A10].
Our description of divisors, greatest common divisor, the remainder theorem and Euclid’s algorithm all used just these axioms, so we really ought to be able to define the greatest common divisor of two polynomials, and to compute it using Euclid’s algorithm.
This can be done, and you will find a description of the process on the page
http://en.wikipedia.org/wiki/Greatest common divisor of two polynomials
To calculate \(d=\gcd(1815, 1415)\) we write
\[ \begin{array}{rcr} 1815&=&1\times1415+400\\ 1415&=&3\times400 +215\\ 400&=&1\times215+185\\ 215&=&1\times185+30\\ 185&=&6\times30+5\\ 30&=&6\times5+0\\ \end{array} \] The last non-zero remainder is \(5\), so \(d=5\).
In many cases, the value of \(d\) can be identified before a zero remainder is reached: since \(d=\gcd(a,b)=\gcd(b,r_1)=\gcd(r_1,r_2)=\ldots\), one can stop as soon as one recognises the greatest common divisor of a pair of consecutive terms in the sequence \(a, b, r_1, r_2, \ldots\). In Example 2.14, for instance, the remainders \(185\) and \(30\) clearly have greatest common divisor \(5\), so \(d=5\).
Use Exercise 2.11 to devise an alternative algorithm to Euclid’s for calculating the greatest common divisor. This is known as the least remainders algorithm.
If \(a\) and \(b\) are integers (not both \(0\)), then there exist integers \(u\) and \(v\) such that \[\gcd(a,b)=au+bv.\]
NOTE: The values of \(u\) and \(v\) are not uniquely determined by \(a\) and \(b\).
Proof. We use the equations which arise when we apply Euclid’s algorithm to calculate \(d=\gcd(a,b)\):
The penultimate equation, of Euclid’s algorithm has the form \[r_{n-1}-q_{n+1}r_{n} = r_{n+1},\]
Recall that \(d={r_{n+1}}\). So we get \(d={r_{n-1}-q_{n+1}r_{n}}\). Marching back up Euclid’s algorithm we have: \[r_{n}=r_{n-2}-q_{n}r_{n-1},\]
This allows us to eliminate \(r_{n}\)
\[d={r_{n-1}-q_{n+1}(r_{n-2}-q_{n}r_{n-1})}={(1+q_{n-1}q_n)r_{n-1}-q_{n+1}r_{n-2}},\]
- Gradually work backwards through the equations in the algorithm, eliminating \(r_{n-1}, r_{n-2}, \ldots\) in succession.
- eventually we express \(d\) in terms of \(r_1\) and \(r_2\),
- then in terms of \(b\) and \(r_1\),
- and finally in terms of \(a\) and \(b\).
- that is, \(d=au+bv\) for some integers \(u\) and \(v\).
Hence the result.
In Example 2.14 we used Euclid’s algorithm to calculate \(d\), where \(a=1815\) and \(b=1415\). Use those equations again to obtain \(u\) and \(v\).
\[ \begin{array}{rcl} 5&=&1\times185-6\times30\\ &=&1\times185-6\times(215-1\times185)\\ &=&7\times185-6\times215\\ &=&7\times(400-1\times215) - 6\times215\\ &=&7\times400-13\times215\\ &=&7\times400-13\times(1414-3\times400)\\ &=&46\times400-13\times1414\\ &=&46\times(1815-1\times1415)-13\times1415\\ &=&46\times1815-59\times1415\\ \end{array} \] and so \(u=46, v=-59\).
Find \(d=\gcd(1068, 4294)\) and express \(d\) in the form \(d=1068u + 4294v\):
First we use Euclid’s algorithm \[ \begin{array}{rcr} 4294&=&4\times1068+22\\ 1068&=&48 \times 22+12\\ 22&=&1 \times 12+10\\ 12&=&1 \times 10+2\\ 10&=&5 \times 2+0\\ \end{array} \]
Next we apply Bezout’s identity \[ \begin{array}{rcl} 2&=&12-10\\ 2&=&12-(22-12)\\ 2&=&2\times12-22\\ 2&=&2\times(1068-48\times22)-22\\ 2&=&2\times1068-97\times22\\ 2&=&2\times1068-97(4294-4\times 1068)\\ 2&=&390\times1068-97\times 4294\\ \end{array} \]
The number of steps in the Euclidean algorithm does not exceed 5 times the number of decimal digits in the smaller of the two numbers.
Proof. Writing \(a=r_0\) and \(b=r_1\) we can apply the Euclidean algorithm to \(a\) and \(b\) to get a sequence of equations. \[ \begin{array}{rclcr} r_0&=&q_1r_1+r_2&&0\le r_2<r_1\\ r_1&=&q_2r_2+r_3&&0\le r_3<r_2\\ r_2&=&q_3r_3+r_4&&0\le r_4<r_3\\ &\ldots&\\ r_{n-3}&=&q_{n-2}r_{n-2}+r_{n-1}&\qquad&0\le r_{n-1}<r_{n-2}\\ r_{n-2}&=&q_{n-1}r_{n-1}+r_{n}&\qquad&0\le r_{n}<r_{n-1}\\ r_{n-1}&=&q_{n}r_{n}\\ \end{array} \]Notice that \(q_1, \ldots,q_{n-1}\ge 1\) and that \(q_n\ge 2\) (as \(r_n<r_{n-1}\)). Consequently we see that \[ \begin{array}{rcl} r_n\ge 1& = &f_2\\ r_{n-1}\ge2r_n\ge 2f_2 & = &f_3\\ r_{n-2}\ge r_{n-1}+r_n\ge f_3+f_2&=&f_4\\ &\ldots&\\ r_2\ge r_3+r_4\ge f_{n-1}+f_{n-2}&=&f_n\\ b = r_1\ge r_2+r_3\ge f_n+f_{n-1}&=&f_{n+1} \end{array} \] But from Example 1.21 we see that \(f_{n+1}\ge \alpha^{n-1}\) for \(n\ge 2\), where \(\alpha = (1+\sqrt{5})/2\). Now since \(\log_{10}\alpha > 1/5\) it follows that \[ \log_{10} b \ge (n-1)\log_{10}\alpha > (n-1)/5. \] If \(b\) has \(k\) decimal digits then \(b< 10^k\) and so \(\log_{10}b< k\). Hence \(n-1< 5k\) and the result follows.
So, for example, if we apply the Euclidean algorithm to integers with 100 digits, then we require no more than 500 steps in the algorithm.
The gcd of a set of integers
Having seen how to calculate the greatest common divisor of two integers, it is a straightforward matter to extend this to any finite set of integers (not all \(0\)). The method, which involves repeated use of Euclid’s algorithm, is based on the following observation.
Prove that for any \(k\ge 2,\) \[\gcd(a_1,\ldots,a_k)=\gcd(\ldots\gcd(\gcd(a_1,a_2), a_3), \ldots, a_k).\]
For example, to calculate \(\gcd(36,24,54,27)\) we calculate \[ \begin{array}{rcrcr} d_2&=&\gcd(36, 24)&=&12\\ d_3&=&\gcd(12, 54)&=&6\\ \text{and finally }d_4&=&\gcd(6, 27)&=&3\\ \end{array} \]
Let \(a\) and \(b\) be integers (not both \(0\)) with greatest common divisor \(d\). Then an integer \(c\) has the form \(ax+by\) for some \(x, y\in{\mathbb Z }\) if and only if \(c\) is a multiple of \(d\). In particular, \(d\) is the least positive integer of the form \(ax+by\;(x, y\in{\mathbb Z })\).
We saw in Example 2.14 that if \(a=1815\) and \(b=1415\) then \(d=5\), so the integers of the form \(c=1815x+1415y\) are the multiples of \(5\). Example 2.17 gives \(5=1815\times46+1415\times(-59)\), so multiplying through by \(e\) we can express any multiple of 5, \(5e\), in the form \(1815x+1415y\): for instance, \(-10=1815\times(-92)+1415\times118\).
Proof. If \(c=ax+by\) where \(x, y\in{\mathbb Z }\), then since \(d\) divides \(a\) and \(b\), we deduce by Corollary 2.7 that \(d\) divides \(c\).
Conversely, suppose that \(c=de\) for some integer \(e\). By Bezout’s identity (Theorem 2.16) we can write \(d=au+bv\) for some integers \(u,v\) and hence \(c=de=(au+bv)e=aue+bve=ax+by\), where \(x=ue\) and \(y=ve\) are both integers. Thus the integers of the form \(ax+by\;(x, y\in{\mathbb Z })\) are the multiples of \(d\), and the least positive integer of this form is the least positive multiple of \(d\), namely \(d\) itself.
Coprime Integers
Two integers \(a\) and \(b\) are coprime (or relatively prime) if \(\gcd(a, b)=1\).
For example, \(15\) and \(23\) are coprime, but \(15\) and \(20\) are not.
When dealing with more than two integers, there is two ways to generalise.
- The integers \(a_1, a_2, \ldots, a_n\) are coprime if {\(\gcd(a_1, a_2, \ldots, a_n)=1\).}
- The integers \(a_1, a_2, \ldots, a_n\) are mutually coprime if {\(\gcd(a_i, a_j)=1\) whenever \(i\neq j\).}
It should be clear that if the integers \(a_1, a_2, \ldots, a_n\) are mutually coprime then they are coprime (since \(\gcd(a_1, a_2, \ldots)|\gcd(a_i, a_j)\)).
The converse is false: for example, the integers \(6, 10, 15\) are coprime but are not mutually coprime.
Two integers \(a\) and \(b\) are coprime if and only if there exist integers \(x\) and \(y\) such that \[ax+by=1.\]
Proof. Let \(\gcd(a, b)=d\). If we put \(c=1\) in Theorem 2.21, we see that \(ax+by=1\) for some \(x, y\in{\mathbb Z }\) if and only if \(d|1\), that is, \(d=1\).
The following two corollaries will prove extremely useful, and will be used on a number of occasions in subsequent chapters.
If \(\gcd(a, b)=d\) then \[\gcd(ma, mb)=md\] for every integer \(m>0\), and \[\gcd(u,v)=1\]
where \(u\) is the unique integer such that \(a=ud\) and \(v\) is the unique integer such that \(b=vd\).
Proof. By Theorem 2.21, \(\gcd(ma, mb)\) is the smallest positive value of \(max+mby=m(ax+by)\), where \(x, y\in{\mathbb Z}\), while \(d\) is the smallest positive value of \(ax+by\), so \(\gcd(ma, mb)=md\). Write \(d=ax+by = (du)x + (dv)y\). Then by the cancellation lemma \(ux+vy=1\). Corollary 2.23 then implies that \(u\) and \(v\) are coprime.
Let \(a\) and \(b\) be coprime integers.
- If \(a|c\) and \(b|c\) then \(ab|c\).
- If \(a|bc\) then \(a|c\).
Proof. Let \(a\) and \(b\) be coprime integers.
We have \(ax+by=1,\; c=ae\) and \(c=bf\) for some integers \(x, y, e\) and \(f\). Then \(c=cax+cby=(bf)ax+(ae)by=ab(fx+ey)\), so \(ab|c\).
As in (a), \(c=cax+cby\). Since \(a|bc\) and \(a|a\), Corollary 2.7 implies that \(a|(cax+cby)=c\).
Least Common Multiple
If \(a\) and \(b\) are integers, then a common multiple of \(a\) and \(b\) is an integer \(c\) such that \(a|c\) and \(b|c\). If \(a\) and \(b\) are both non-zero, then they have positive common multiples (such as \(|ab|\)), so by the well-ordering principle they have a least common multiple or, more precisely, a least positive common multiple; this is the unique positive integer \(l\) satisfying
- \(a|l\) and \(b|l\) (so \(l\) is a common multiple), and
- if \(a|c\) and \(b|c\), with \(c>0\), then \(l\le c\) (so no positive common multiple is less than \(l\)).
Let \(a\) and \(b\) be positive integers, with \(d=\gcd(a, b)\) and \(l=\text{ lcm}(a, b)\). Then \[dl=ab.\]
NOTE: We can assume that \(a,b>0\) since \(\gcd(a,b)=\gcd(|a|,|b|)\) and \(\text{lcm}(a,b)=\text{lcm}(|a|,|b|)\).
Proof. Let \(a = ed\) and \(b = fd\), so that \[ab=efd^2.\] Now consider \(efd\), clearly this is positive, so we can show that it is equal to \(l\) by showing that it satisfies conditions (1) and (2) of the definition of \(\text{lcm}(a,b)\).
Firstly, \[efd=(ed)f=af\quad\text{and}\quad edf=(fd)e=be;\] thus \(a|def\) and \(b|def\), so (1) is satisfied.
Secondly, suppose that \(a|c\) and \(b|c\), with \(c>0\); it follows that there exist integers \(p,q\) such that \(c=ap = bq\). We need to show that \(def\le c\).
By Theorem 2.16 there exist integers \(u\) and \(v\) such that \(d=au+bv\). Now \[(ab) (qu+pv)= abqu+abpv = acu+bcv = c(au+bv) = cd\]
hence \(ab\) is a divisor of \(cd\).
This implies that \(cd=kab\) for some integer \(k\), so \(cd=kd(def)\). The cancellation lemma means that \(c=kdef\). Hence \(def\) divides \(c\), and so, as we noted in Lemma 2.5, \(def\le c\) as required.
If \(a=16\) and \(b=12\), then \(d=4\) and \(l=48\); thus \(dl=192=ab\), agreeing with Theorem 2.26.
We can use Theorem 2.26 to find \(l=\text{ lcm}(a, b)\) efficiently by first using Euclid’s algorithm to find \(d=\gcd(a, b)\), and then calculating \(l=ab/d\).
Since \(\gcd(1815, 1415)=5\) we have \(\text{lcm}(1815, 1415)=(1815\times 1415)/5=513645\).
Linear Diophantine Equations
Find the general solution to \[1815x+1415y=-10,\] Equations in one or more variables, for which we seek integer-valued solutions.
Simplest example is the linear Diophantine equation \[ax+by=c\] The following result was known to the Indian mathematician Brahmagupta, around 628 AD:
Let \(a, b\) and \(c\) be integers, with \(a\) and \(b\) not both \(0\), and let \(d=\gcd(a, b)\). Then the equation \[ax+by=c\] has an integer solution \(x, y\) if and only if \(c\) is a multiple of \(d\), in which case there are infinitely many solutions.
Writing \(a=pd\) and \(b=qd\) the solutions are
\[x=x_0+{qn},\quad y=y_0-{pn}\qquad(n\in{\mathbb Z }),\]
where \(x_0, y_0\) is any particular solution.
Proof. The fact that there is a solution if and only if \(d|c\) is simply a restatement of Theorem 2.21.
To find the general form of the solutions, let \(x_0, y_0\) be a particular solution, so \(ax_0+by_0=c.\)
Let \(n\in\mathbb Z\) and put \[x=x_0+{qn},\quad y=y_0-{pn}.\] Then \[ax+by=a(x_0+{qn})+b(y_0-{pn})=\] \[ax_0+by_0+(aqn-bpn)=c+(pdqn-qdpn)=c,\] and so \(x, y\) is also a solution. As this holds for an integer \(n\) then there are therefore infinitely many solutions.
Now suppose that \(x, y\) is any integer solution, so that \(ax+by=c\). Since \(ax+by=c=ax_0+by_0\) we have \[a(x-x_0)=b(y_0-y).\]
Now \(a=pd\) and \(b=qd\) and so \[pd(x-x_0)=qd(y_0-y).\] Applying the cancellation lemma to cancel \(d\) we get \[p(x-x_0)=-q(y-y_0).\qquad(*)\] Hence \(q\) is a divisor of \(p(x-x_0)\), and \(p\) is a divisor of \(q(y-y_0)\).
Since \(a\) and \(b\) are not both \(0\), we can suppose that \(b\neq 0\) (otherwise we can interchange the roles of \(a\) and \(b\)). Consequently \(q\ne0\).
We also note that \(q\) is coprime to \(p\) by Corollary 2.24, and so it divides \(x-x_0\) by Corollary 2.25(b). Thus \(x-x_0=qn\) for some integer \(n\) and so \[x=x_0+{qn}.\]
Substituting back for \(x-x_0\) in \((*)\) we get \[-q(y-y_0)=p(x-x_0)=pqn,\]
Since \(q\neq 0\) the Cancellation Lemma implies that \[y=y_0-pn.\]
Thus we can find the solutions of any linear Diophantine equation \(ax+by=c\) by the following technique:
- Calculate \(d=\gcd(a, b)\), either directly or by Euclid’s algorithm.
- Check whether \(d\) is a divisor of \(c\): if it is not, there are no solutions, so stop here; if it is, write \(c=de\).
- If \(d|c\), use the method of proof of Theorem 2.16 to find integers \(u\) and \(v\) such that \(au+bv=d\); then \(x_0=ue, y_0=ve\) is a particular solution of \(ax+by=c\).
- Use Theorem 2.29 to find the general solution \(x, y\) of the equation.
Find the general solution to \[1815x+1415y=-10,\] so \(a=1815,\; b=1415\) and \(c=-10\).
In step (1), we use Example 2.14 to see that \(d=5\).
In step (2) we check that \(d\) divides \(c\): in fact, \(c=-2d\), so \(e=-2\).
In step (3) we use Example 2.17 to write \(d=46\times1815+(-59)\times1415\); thus \(u=46\) and \(v=-59\),
so \(x_0=46\times(-2)=-92\) and \(y_0=(-59)\times(-2)=118\) give a particular solution of the equation.
By Theorem 2.29, the general solution has the form
\[x=-92+\frac{1415n}{5}=-92+283n,\quad y=118-\frac{1815n}{5}=118-363n \]
\[n\in{\mathbb Z }.\]