Divisibility, GCD and LCM

The notation \(a|b\) means that the integer a divides the integer b. For example, 2|6, 7|14, etc. We note the following facts:

• If \(a|b\) and \(b|c\), then \(a|c\). This should be obvious.

• If \(a|b\), then for any integer k, \(a|kb\).

• If \(a|b\), then \(ka|kb\). That is, if b is a multiple of a, then k times b is a multiple of k times a. Once again, this should be easy to understand.

• If \(a|b\) and \(a|c\), then \(a|\left( {b \pm c} \right)\). That is, if a is a factor of b as well as c, then it is a factor of their sum and difference as well.

• If \(a|b\) and \(a|c\), then for any integers x and y, \(a|\left( {xb + yc} \right)\). This means that if a is a factor of b and c, then it is a factor of any integral linear combination of b and c. You are urged to justify this result.

 

Now, we come to the GCD. For two integers a and b, their GCD is represented as \(\left( {a,b} \right)\). For example, \(\left( {6,9} \right) = 3\), \(\left( {10,15} \right) = 5\), \(\left( {19, - 20} \right) = 1\), etc. The GCD is taken to be the greatest positive common factor.

We have seen how Euclid’s Division Algorithm enables us to calculate the GCD of two integers. Let us revisit this. Suppose that we have to find the GCD of 93 and 27 using this algorithm. We have:

\[\begin{align} S1: & 93 = 27\left( 3 \right) + 12\\S2: & 27 = 12\left( 2 \right) + 3\\S3: & 12 = \left( 4 \right) + 0\end{align}\]

Thus, the GCD is 3. Let us analyze this sequence of steps in a bit more detail. Consider the second step of the algorithm. Rearranging it slightly, we have:

\[3 = 27\left( 1 \right) - 12\left( 2 \right)\]

From Step-1, we substitute the expression for 12 above:

\[\begin{align}&3\;\; = 27\left( 1 \right) - 12\left( 2 \right)\\&\quad = 27\left( 1 \right) - \left( {93\left( 1 \right) - 27\left( 3 \right)} \right)\left( 2 \right)\\&\quad= 27\left( 7 \right) - 93\left( 2 \right)\end{align}\]

What we have done is write the GCD of 93 and 27 (which is 3) as some integral linear combination of 93 and 27:

\[\begin{align}&3 = 27\left( 7 \right) + 93\left( { - 2} \right)\\&\;\;= 27x + 93y\end{align}\]

Let us take another example. We apply Euclid’s Division Algorithm to 100 and 115:

\[\begin{align}&115 = 100\left( 1 \right) + 15\\&100 = 15\left( 6 \right) + 10\\&\;\;15 = 10\left( 1 \right) + 5\\&\;\;10 = \left( 2 \right)\end{align}\]

Now, let us see if we can express the GCD 5 as a linear combination of 100 and 115. Back-tracking from the second last step, we have:

\[\begin{align}&5 = 15\left( 1 \right) - 10\left( 1 \right)\\&\,\,\, = 15\left( 1 \right) - \left( {100\left( 1 \right) - 15\left( 6 \right)} \right)\left( 1 \right)\\&\,\,\, = 15\left( 7 \right) - 100\left( 1 \right)\\&\,\,\, = \left( {115\left( 1 \right) - 100\left( 1 \right)} \right)\left( 7 \right) - 100\left( 1 \right)\\&\,\,\, = 115\left( 1 \right) - 100\left( 8 \right)\\&\,\,\, = 115\left( 1 \right) + 100\left( { - 8} \right)\end{align}\]

It should be apparent that this can be done in every case. Thus, if \(d = \left( {a,b} \right)\), then there exist some integers x and y such that \(d = ax + by\). That is, the GCD of two numbers can be expressed as an integral linear combination of the two numbers.

Remark-1. An interesting corollary follows from this result. An integer c can be written as an integral linear combination of two integers a and b if and only if c is a multiple of \(d = \left( {a,b} \right)\). Let us prove this.

First, suppose that c can be written as \(c = ax + by\) for some integers x and y. Since \(d|a\) and \(d|b\), d divides any integral linear combination of a and b. Thus, d divides c.

Now, suppose that d divides c. Thus, for some integer k, \(c = dk\). Since \(d = \left( {a,b} \right)\), d can be written as an integral linear combination of a and b:

\[d = ax' + by'\]

Thus,

\[\begin{align}&c = dk = kax' + kby'\\&\quad\quad\;\;\; = ax + by\end{align}\]

We see that c can be expressed as a linear combination of a and b. This completes our proof.

Remark-2. If a and b are two co-prime integers, this means that they have no common factors other than 1, that is, their GCD is \(\left( {a,b} \right) = 1\). Thus, there exist integers x and y such that

\[\left( {a,b} \right) = 1 = ax + by\]

For example,

\[\begin{align}&\left( {17,10} \right) = 1 = 17\left( 3 \right) + 10\left( { - 5} \right)\\&\left( {12,11} \right) = 1 = 12\left( { - 10} \right) + 11\left( {11} \right)\end{align}\]

Example 1: For two integers a and b, if 1 can be expressed as an integral linear combination of a and b, then \(\left( {a,b} \right) = 1\).

Solution: In Remark-1 above, we saw that an integer c can be written as an integral linear combination of two integers a and b if and only if c is a multiple of \(d =(a,b)\). If \(1 = ax + by\) for some integers x and y, then 1 is a multiple of \(\left( {a,b} \right)\). This can only mean that \(\left( {a,b} \right) = 1\).

Example 2: Prove that \(d = \left( {a,b} \right)\), then \(\frac{a}{d}\) and \(\frac{b}{d}\) are co-prime integers.

Solution: We have already discussed this result informally earlier. Now, we prove it more rigorously. Since \(d = \left( {a,b} \right)\), we can find integers x and y such that \(d = ax + by\). Thus,

\[\frac{a}{d}\left( x \right) + \frac{b}{d}\left( y \right) = 1\]

We see that \(\frac{a}{d}\) and \(\frac{b}{d}\) are two integers whose linear combination can be obtained as 1. Thus,

\[\left( {\frac{a}{d},\frac{b}{d}} \right) = 1\]

In other words, \(\frac{a}{d}\) and \(\frac{b}{d}\) are co-prime, because their GCD is 1.

Example 3:   (a) a, b and c are three integers, such that \(c|ab\) and \(\left( {a,c} \right) = 1\). Prove that \(c|b\).

(b) a and b are two integers and p is a prime number which divides ab but not a. Prove that p divides b.

(c) Prove that if p is a prime number and p divides a product of integers, then p divides at least one of them.

Solution: Intuitively speaking, this result is simple to understand. If c and a are co-prime but c is a factor of ab, then c must be a factor of b. Let us prove this rigorously now.

For some integers x and y, we will have:

\[ax + cy = 1\]

Also, for some integer k, \(ab = ck\). Now,

\[\begin{align}&b = b.1 = b\left( {ax + cy} \right)\\&\qquad\quad= abx + bcy\\&\qquad\quad = ckx + bcy\\&\qquad\quad = c\left( {kx + by} \right)\end{align}\]

Clearly, b is a multiple of c.

(b) This result follows from part-(a). Since \(p|ab\) and \(\left( {p,a} \right) = 1\), this means that \(p|b\).

(c) This follows from part-(b), and is left to you as an exercise.

Next, we turn to the LCM. The LCM of two integers a and b is denoted as \(\left[ {a,b} \right]\). For example, \(\left[ {6,9} \right] = 18\), \(\left[ {10,15} \right] = 30\), etc. The LCM is taken to be the least positive common multiple of the integers.

Example 4: Let a and b be two integers. For any positive integer m, show that \(\left[ {ma,mb} \right] = m\left[ {a,b} \right]\).

Solution: The LCM of ma and mb must be a multiple of m. Assume that \(\left[ {ma,mb} \right] = km\). Also, let \(\left[ {a,b} \right] = p\).

Since p is a multiple of a as well as b, mp is a common multiple of ma as well as mb. Since the LCM of ma and mb is km, we conclude that mp is a multiple of km. Thus, \(km|mp\), or \(k|p\).

Also, since km is a multiple of ma as well as mb, we find that k is a common multiple of a as well as b. Thus, k must be a multiple of the LCM of a and b. In other words, \(p|k\).

Since \(k|p\) and \(p|k\), we conclude that \(k = p\). Thus,

\[\left[ {ma,mb} \right] = mk = mp = m\left[ {a,b} \right]\]

Example 5: For any two integers a and b, show that

\[\left( {a,b} \right)\left[ {a,b} \right] = \left| {ab} \right|\]

Solution: We have discussed an intuitive proof for this result; now we proceed more formally. We prove this result for positive a and b; the result for two general integers a and b will then follow.

We divide the situation into two cases.

Case 1: a and b are co-prime, \(\left( {a,b} \right) = 1\)

In this case, we have to prove that \(\left[ {a,b} \right] = ab\). Suppose that \(\left[ {a,b} \right) = pa = qb\) for some integers p and q. Now, we see that \(b|pa\). Since b is co-prime to a, this means that \(b|p\). Also, this means that \(b \le p\), or \(ab \le ap = \left[ {a,b} \right]\). But \(\left[ {a,b} \right]\) is the LCM of a and b, while \(ab\) is also a multiple of a and b. Clearly, \(ab \le \left[ {a,b} \right]\) in this case means that \(ab = \left[ {a,b} \right]\). This completes our proof.

Case 2: \(\left( {a,b} \right) = d > 1\)

In this case, we have \(\left( {\frac{a}{d},\frac{b}{d}} \right) = 1\); by the result from Case-1, we have:

\[\begin{align}&\left[ {\frac{a}{d},\frac{b}{d}} \right] = \frac{a}{d}.\frac{b}{d} = \frac{{ab}}{{{d^2}}}\\ &\Rightarrow \,\,\,{d^2}\left[ {\frac{a}{d},\frac{b}{d}} \right] = ab\\ &\Rightarrow \,\,\,d\left[ {d \times \frac{a}{d},d \times \frac{b}{d}} \right] = ab\\ &\Rightarrow \,\,\,d\left[ {a,b} \right] = ab\\ &\Rightarrow \,\,\,\left( {a,b} \right)\left[ {a,b} \right] = ab\end{align}\]

In the sequence of steps above, we have used the result from the previous example:

\[\left[ {ma,mb} \right] = m\left[ {a,b} \right]\]

Example 6: Prove that for two integers a and b,

\[\left( {a + b,a - b} \right) \ge \left( {a,b} \right)\]

Solution: Let

\[\begin{align}&\left( {a + b,a - b} \right) = D\\&\left( {a,b} \right) = d\end{align}\]

Now, there will exist integers x and y such that

\[\begin{align}&D = \left( {a + b} \right)x + \left( {a - b} \right)y\\&\,\,\,\,\, = ax + ay + bx - by\\&\,\,\,\,\, = a\left( {x + y} \right) + b\left( {x - y} \right)\end{align}\]

Observed that we have been able to express D as an integral linear combination of a and b, which means that D is a multiple of \(\left( {a,b} \right) = d\). Thus, \(D \ge d\).

Example 7: For any integer n, find the value of \(\left[ {9n + 8,6n + 5} \right]\).

Solution: We note that:

\[2\left( {9n + 8} \right) - 3\left( {6n + 5} \right) = 1\]

Thus, an integral linear combination of the two given numbers is 1, which means that their GCD is 1. This means that their LCM is their product, or

\[\left( {9n + 8} \right)\left( {6n + 5} \right) = 54{n^2} + 93n + 40\]

Example 8: Show that \(\left( {{a^n},{b^n}} \right) = {\left( {a,b} \right)^n}\).

Solution: Consider a prime number p which is a factor of both a and b. Let the power of p in a and b be \({k_a},{k_b}\)respectively. The power of p in \(\left( {a,b} \right)\) will be the minimum of \({k_a},{k_b}\), or \(\min \left( {{k_a},{k_b}} \right)\). Now, the power of p in \({\left( {a,b} \right)^n}\) will be \({\left\{ {\min \left( {{k_a},{k_b}} \right)} \right\}^n}\), or \(\min \left( {{k_a}^n,{k_b}^n} \right)\).

On the other hand, the power of p in \({a^n},{b^n}\) will be \({k_a}^n,{k_b}^n\), and so the power of p in \(\left( {{a^n},{b^n}} \right)\) will be \(\min \left( {{k_a}^n,{k_b}^n} \right)\).

Thus, we conclude that any prime factor p which is common to a and b will have the same power in \({\left( {a,b} \right)^n}\) as well as \(\left( {{a^n},{b^n}} \right)\). On the other hand, any prime factor which is not common to a and b will occur neither in \({\left( {a,b} \right)^n}\) nor in \(\left( {{a^n},{b^n}} \right)\).

Thus, the prime factorization of \({\left( {a,b} \right)^n}\) as well as \(\left( {{a^n},{b^n}} \right)\) will be exactly the same, which means that \(\left( {{a^n},{b^n}} \right) = {\left( {a,b} \right)^n}\).

Example 9: Find all cases of integers a and b such that \(\left( {a,b} \right) = \left[ {a,b} \right]\).

Solution: We start as in the previous problem. We consider a prime number p which is a factor of both a and b, and we let the power of p in a and b be \({k_a},{k_b}\)respectively. The power of p in \(\left( {a,b} \right)\) will be the minimum of \({k_a},{k_b}\), or \(\min \left( {{k_a},{k_b}} \right)\), and the power of p in \(\left[ {a,b} \right]\) will be \(\max \left( {{k_a},{k_b}} \right)\). If \(\left( {a,b} \right) = \left[ {a,b} \right]\), this means that \(\min \left( {{k_a},{k_b}} \right)\) and \(\max \left( {{k_a},{k_b}} \right)\) are equal, which can only happen if \({k_a} = {k_b}\).

Thus, the power of every prime factor in a is equal to the power of that prime factor in b. Also, it is easy to see that there can be no prime factor which is not common to a and b (since then it will not occur in the HCF but will occur in the LCM).

We conclude that a and b must be equal.