authored by Premmi and Beguène
Previous Topic : The Division Algorithm
It is worthwhile to study in detail the case wherein the remainder in the Division Algorithm turns out to be zero. Such a study leads to some very interesting insights that form the cornerstone of number theory.
Divisibility of Integers
Definition
An integer b is said to be divisible by an integer a \neq 0, symbolically written as a \,|\, b, if there exists some integer c such that b = ac.
We write a \nmid b to indicate that b is not divisible by a.
Examples
For example, -24 is divisible by 3, because -24 = 3(-8). However, 10 is not divisible by 7 because there is no integer c that makes the statement 10 = 7c true.
There are a multitude of ways for expressing the divisibility relation a \,|\, b. We could say that a is a divisor of b, that a is a factor of b or that b is a multiple of a.
It should be noted that whenever the notation a \,|\, b is used, it is understood that a is a nonzero integer.
If a is a divisor of b, then there exists an integer c such that b = ac. This implies that b = (-a)(-c), which means that b is also divisible by -a. Hence, the divisors of an integer always occur in pairs.
To find all the divisors of a given integer, it will suffice to deduce the positive integers and adjoin to them the corresponding negative integers. For this reason, we will usually limit ourselves to a consideration of only the positive divisors.
We list below some immediate consequences of the above definition.
Theorem
For integers a, b \text{ and } c the following hold:
(a) a \,|\, 0, 1 \,|\, a, a \,|\, a
(b) a \,|\, 1 if and only if a = \pm 1
(c) If a \,|\, b \text{ and } c \,|\, d, then ac \,|\, bd
(d) If a \,|\, b \text{ and } b \,|\, c, then a \,|\, c
(e) a \,|\, b \text{ and } b \,|\, a if and only if a =\pm b
(f) If a \,|\, b \text{ and } b \neq 0, then |a| \leq |b|
(g) If a \,|\, b \text{ and } a \,|\, c, then a \,|\, (bx + cy) for arbitary integers x \text{ and } y
Proof
We will now prove assertions (a) to (g).
(a) a \,|\, 0, 1 \,|\, a, a \,|\, a
\quad Integer b = 0 is divisible by integer a because there exists an integer c = 0 such that b = ac.
\quad We can verify this by substituting the respective values for b \text{ and } c which results in the equality, 0 = a(0).
\quad Similarly, a is divisible by 1 because a = 1 \cdot a.
\quad a is divisible by a because a = a \cdot 1.
(b) a \,|\, 1 if and only if a = \pm 1
\quad Let us prove the first part of the assertion, namely, “If a \,|\, 1, then a =\pm 1.”
\quad If a \,|\, 1, then there exists an integer b such that 1 = ab.
\quad ab = 1 implies that either a = 1 \text{ and } b = 1 or a = -1 \text{ and } b = -1.
\quad This proves the assertion that if a \,|\, 1, then a =\pm 1.
\quad Let us prove the second part of the assertion, namely, “If a =\pm 1, then a \,|\, 1 .”
\quad If a = 1 it follows that 1 = ab where b = 1. Hence, 1 is divisible by a.
\quad Similarly, if a = -1 it follows that 1 = ab where b = -1. Hence, 1 is divisible by a.
\quad Therefore, a \,|\, 1 if and only if a = \pm 1.
(c) If a \,|\, b \text{ and } c \,|\, d, then ac \,|\, bd
\quad If a \,|\, b, then there exists some integer e such that
b = ae
\quad Similarly, since c \,|\, d,
d = cf
\quad for some integer f.
\quad Therefore,
bd = aecf = acef = acg
\quad where g = ef.
\quad Since the product of two integers is also an integer, bd \text{ and } ac are also integers.
\quad Hence, integer bd is divisible by integer ac because there exists an integer g such that bd = acg.
\quad Thus we have proved the assertion that if a \,|\, b \text{ and } c \,|\, d, then ac \,|\, bd.
(d) If a \,|\, b \text{ and } b \,|\, c, then a \,|\, c
\quad If a \,|\, b, then there exists some integer d such that
b = ad
\quad Similarly, if b \,|\, c, then there exists some integer e such that
c = be
\quad Multiplying both the equations together, we get
bc = adbe
\quad Dividing both sides of the equation by b, results in
c = ade = af
\quad where f = de.
\quad The integer c is divisible by integer a because there exists an integer f such that c = af.
\quad This proves the assertion that if a \,|\, b \text{ and } b \,|\, c, then a \,|\, c.
(e) a \,|\, b \text{ and } b \,|\, a if and only if a =\pm b
\quad Let us prove the first part of the assertion, namely, “If a \,|\, b \text{ and } b \,|\, a, then a =\pm b.”
\quad If a \,|\, b \text{ and } b \,|\, a, then there are integers c \text{ and } d such that
b = ac
\quad and
a = bd
\quad Multiplying both the equations, we get
ba = acbd
\quad Rearranging the terms of the above equation, results in
ab = abcd
\quad Dividing both sides of the equation by ab,
1 = cd
\quad Since c \text{ and } d are both integers, cd = 1 only when c = d = 1 or c = d = -1.
\quad Since b = ac, when c = 1, \, b = a \implies a = b and when c = -1, \, b = -a \implies a = -b.
\quad Therefore, we have proved that if a \,|\, b \text{ and } b \,|\, a then a =\pm b.
\quad Let us now prove the second part of the assertion, namely, “If a =\pm b, then a \,|\, b \text{ and } b \,|\, a.”
\quad Let us consider the case when a = b.
a = b \implies b = a \implies b = a \cdot 1
\quad b is divisible by a because there exists an integer c = 1 such that b = ac.
\quad Also,
a = b \implies a = b \cdot 1
\quad a is divisible by b because there exists an integer c = 1 such that a = bc.
\quad Therefore, when a = b we have proved that a \,|\, b \text{ and } b \,|\, a.
\quad Next, let us consider the case when a = -b.
a = -b \implies b = -a \implies b = a \cdot (-1)
\quad b is divisible by a because there exists an integer c = -1 such that b = ac.
\quad Similarly,
a = -b \implies a = b \cdot (-1)
\quad a is divisible by b because there exists an integer c = -1 such that a = bc.
\quad Therefore, when a = -b we have proved that a \,|\, b \text{ and } b \,|\, a.
\quad Hence, we have proved that a \,|\, b \text{ and } b \,|\, a if and only if a =\pm b.
(f) If a \,|\, b \text{ and } b \neq 0, then |a| \leq |b|
\quad If a \,|\, b, then there exists an integer c such that b = ac.
\quad Also, b \neq 0 implies that c \neq 0.
\quad Upon taking absolute values, we get
|b| = |ac| = |a|\cdot|c|
\quad Since c \neq 0, it implies that |c| \geq 1.
\quad Hence,
|b| = |a|\cdot|c| \geq |a|
\quad Therefore, we have proved the assertion that if a \,|\, b \text{ and } b \neq 0, then |a| \leq |b|.
(g) If a \,|\, b \text{ and } a \,|\, c, then a \,|\, (bx + cy) for arbitary integers x \text{ and } y
\quad The relation a \,|\, b \text{ and } a \,|\, c implies that b = ad \text{ and } c = ae, for some integers d \text{ and } e.
\quad For arbitrary integers x \text{ and } y,
bx + cy = adx + aey = a(dx + ey) = af
\quad where f = dx + ey.
\quad Since f is an integer, a \,|\, (bx + cy); thus, the assertion is proved.
It is worth noting that this assertion extends by induction to sums of more than two terms.
That is, if a \,|\, b_k \text{ for } k = 1, 2, \ldots, n, then
a \,|\, (b_1x_1 + b_2x_2 + \cdots + b_nx_n)
for all integers x_1, x_2, \ldots, x_n.
Let us prove this assertion using proof by induction.
We will first establish the basis for induction i.e., prove the assertion for k = 1.
If a \,|\, b_1, then a \,|\, b_1x_1 for arbitary integer x_1.
If a \,|\, b_1, then there exists an integer c such that b_1 = ac. Therefore,
b_1x_1 = acx_1 = a(cx_1)
where cx_1 is an integer. Hence, a \,|\, b_1x_1.
Next let us prove the induction step by using the inductive hypothesis which is stated below.
We will assume that if a \,|\, b_k \text{ for } k = 1, 2, \ldots, m, then
a \,|\, (b_1x_1 + b_2x_2 + \cdots + b_mx_m)
for all integers x_1, x_2, \ldots, x_m, where m is some fixed but unspecified positive integer .
Under the assumption that this assertion is true, we will prove that the assertion “If a \,|\, b_k \text{ for } k = 1, 2, \ldots, m+1, then
a \,|\, (b_1x_1 + b_2x_2 + \cdots + b_{m+1}x_{m+1}) for all integers x_1, x_2, \ldots, x_{m+1}” must be true.
Since a \,|\, (b_1x_1 + b_2x_2 + \cdots + b_mx_m) it implies that there exists an integer d such that
b_1x_1 + b_2x_2 + \cdots + b_mx_m = ad
Adding b_{m+1}x_{m+1} to both sides of the equation we get,
b_1x_1 + b_2x_2 + \cdots + b_mx_m + b_{m+1}x_{m+1} = ad + b_{m+1}x_{m+1}Since b_{m+1} is divisible by a, there exists an integer e such that
b_{m+1} = aeSubstituting for b_{m+1} on the right hand side of the equation, we get
b_1x_1 + b_2x_2 + \cdots + b_mx_m + b_{m+1}x_{m+1} = ad + aex_{m+1} = a(d + ex_{m+1})Since d + ex_{m+1} is an integer it implies that b_1x_1 + b_2x_2 + \cdots + b_mx_m + b_{m+1}x_{m+1} is divisible by a. This proves the induction step.
Our reasoning shows that whenever the assertion is true for any integer m it is also true for integer m+1. We have already proved that the assertion is true for 1. Consequently, it is also true for 1+1 = 2 and so on ad infinitum. Hence the assertion, namely,
“If a \,|\, b_k \text{ for } k = 1, 2, \ldots, n, then
a \,|\, (b_1x_1 + b_2x_2 + \cdots + b_nx_n)
for all integers x_1, x_2, \ldots, x_n” is true for every positive integer n.
Common Divisors
Intuition
Annie is organizing her wardrobe for storage. She has 24 pants and 36 shirts which she needs to store in boxes such that each box has the same type (either all pants or all shirts) and number of clothing items. Also, each box must contain at least 2 pieces of clothing. What are the possible number of clothing items in each box?
Since each box has either pants or shirts and the number of clothing items in each box is the same and greater than 1, we need to find the positive common divisors of 24 \text{ and } 36 that are greater than 1.
Let us now list the positive divisors of each of 24 \text{ and } 36.
\begin{equation*}
\begin{split}
\text{Positive divisors of } 24 &: 1, 2, 3, 4, 6, 8, 12, 24 \\
\text{Positive divisors of } 36 &: 1, 2, 3, 4, 6, 9, 12, 18, 36 \\
\end{split}
\end{equation*}Since there are at least 2 items of clothing per box, the possible numbers of clothing items in each box are 2, 3, 4, 6 \text{ and } 12.
Definition
If a \text{ and } b are arbitrary integers, then an integer d is said to be a common divisor of a \text{ and } b if both d \,|\, a \text{ and } d \,|\, b.
Greatest Common Divisor
Intuition
Now suppose Annie has to use the least number of boxes to store her clothes, while still ensuring that each box contains the same type of clothing and the same number of clothing items. How would be she go about this task?
In order to use the minimum number of boxes, Annie has to store the maximum number of clothing items in each box while still ensuring that each box contains the same type of clothing and the same number of clothing items. That is, Annie should find the largest integer that divides both 24 \text{ and } 36, as this would equal the number of clothing items to place in each box. We have already calculated in the example above that 12 is the largest integer that divides both 24 \text{ and } 36. So Annie will place 12 items of clothing in each box. She will use 24 / 12 = 2 boxes to store her 24 pants and 36 / 12 = 3 boxes to store her 36 shirts. Hence, she will need a minimum of 5 boxes to store her clothes. The integer 12 is called the greatest common divisor of the integers 24 \text{ and } 36.
Let a \text{ and } b be arbitrary integers.
Since 1 is a divisor of every integer, 1 is a common divisor of a \text{ and } b. Hence, the set of positive common divisors of a \text{ and } b is nonempty.
Also, since every integer divides 0, if a = b = 0, then every integer serves as a common divisor of both a \text{ and } b. In this case, the set of positive common divisors of a \text{ and } b is infinite.
However, when at least one of a \text{ or } b is different from zero, there are only a finite number of positive common divisors. Among these, there is a largest one, called the greatest common divisor of a \text{ and } b.
Definition
Let a \text{ and } b be given integers, with at least one of them different from zero. The greatest common divisor of a \text{ and } b, denoted by gcd(a, b), is the positive integer d satisfying the following conditions:
(a) d \,|\, a \text{ and } d \,|\, b
(b) If c \,|\, a \text{ and } c \,|\, b, then c \leq d
Examples
Example 1
Let us find the greatest common divisor of -12 \text{ and } 30.
We begin by listing the positive divisors of each of -12 \text{ and } 30.
\begin{equation*}
\begin{split}
\text{Positive divisors of } -12 &: 1, 2, 3, 4, 6, 12 \\
\text{Positive divisors of } \quad \,30 &: 1, 2, 3, 5, 6, 10, 15, 30 \\
\end{split}
\end{equation*}Therefore, the positive common divisors of -12 \text{ and } 30 are 1, 2, 3 \text{ and } 6. Since 6 is the largest of these integers, it follows that gcd(-12, 30) = 6.
Example 2
Marie and Annie ate some mango gummies for fun. 😃 Marie ate 40 gummies and Annie ate 24. If each packet of gummies from which Marie and Annie ate their respective gummies from contain the same number of gummies, what is the largest possible number of gummies in a packet?
\text{Number of gummies eaten by a person} = \text{Number of gummies in each packet} \times \text{Number of packets}Hence, the number of gummies in a packet should be a divisor of both 40 \text{ and } 24, i.e., the number of gummies eaten by Marie and Annie respectively. Therefore, the largest possible number of gummies in a packet is gcd(40, 24) = 8.
Note: The gcd(40, 24) can be calculated by following the procedure shown in example 1.
We will next prove that gcd(a, b) can be represented as a linear combination of a \text{ and } b. (The linear combination of integers a \text{ and } b is an expression of the form ax + by, where x \text{ and } y are integers.)
For example,
\text{gcd}(-12, 30) = 6 = (-12) \cdot 2 + 30 \cdot 1and
\text{gcd}(40, 24) = 8 = 40 \cdot (-1) + 24 \cdot 2Theorem
Given integers a \text{ and } b, with at least one of them different from zero, there exist integers x \text{ and } y such that
\text{gcd}(a, b) = ax + byWe prove this theorem by showing that the following assertions hold good.
(i) There exists a positive integer, d, such that d = ax + by
(ii) gcd(a, b) = d
We prove assertion (ii) by showing that
(a) d is a positive common divisor of integers a \text{ and } b
(b) there exists no other positive common divisor of integers a \text{ and } b greater than d
Let us prove assertion (i), namely, the existence of a positive integer ax + by.
In order to prove that a positive integer d = ax + by exists, we construct a set of all positive linear combinations of a \text{ and } b i.e., a set of all positive integers of the form au + bv, where u \text{ and } v are integers and prove that this set is not empty. Then from the Well-Ordering Principle we know that such a nonempty set of positive integers will have a least element or equivalently, a smallest integer. We will next prove that this smallest integer d = \text{gcd}(a, b).
We begin by proving that the set, S, of all positive linear combinations of a \text{ and } b, written in set notation as,
S = \{au + bv \,|\, au + bv > 0; u, v \text{ are integers} \}is nonempty.
In order to prove that S is nonempty it suffices to find just one value for each of u \text{ and } v such that au + bv is positive.
If a \neq 0, then the integer |a| = au + b \cdot 0 lies in S, where we choose u = 1 \text{ or } u = -1 depending on whether a is positive or negative. Hence, S is nonempty.
Therefore, by virtue of the Well-Ordering Principle the set S must contain a smallest element d. Thus, by the very definition of S, there exist integers x \text{ and } y for which d = ax + by. We claim that d = \text{gcd}(a, b).
In order to prove this claim, we will first show using the Division Algorithm that d divides a \text{ and } b i.e., d is the positive common divisor of a \text{ and } b. Then we will show that any arbitrary positive common divisor of a \text{ and } b cannot be greater than d.
From the Division Algorithm, we know that we can obtain integers q \text{ and } r such that a = qd + r, where 0 \leq r < d. Then r can be written in the form
r = a - qd
Substituting d = ax + by in the above equation, we get
\begin{equation*}
\begin{split}
r &= a - q(ax + by) \\
&= a(1 - qx) + b(-qy) \\
\end{split}
\end{equation*}
If r were positive, then this representation would imply that r is a member of S, contradicting the claim that d is the least integer in S since r < d. Therefore, r = 0 and so a = qd, or equivalently, d \,|\, a. By similar reasoning, d \,|\, b which implies that d is a common divisor of a \text{ and } b.
Now if c is an arbitrary positive common divisor of a \text{ and } b, then part (g) of the Theorem stated above, allows us to conclude that c \,|\, (ax + by) i.e., c \,|\, d. From part (f) of the same theorem, we know that if c \,|\, d, then c = |c| \leq |d| = d i.e., d is greater than every other positive common divisor of a \text{ and } b.
We have proved that d is a common divisor of a \text{ and } b and is greater than every other positive common divisor of a \text{ and } b. Therefore, d = \text{gcd}(a, b).
Since d = ax + by and d = \text{gcd}(a, b) we can conclude that \text{gcd}(a, b) = ax + by.
Alternate Definition of the Greatest Common Divisor of Two Integers
The above theorem, which expresses the greatest common divisor of two integers as a linear combination of them, leads to an alternate definition of the greatest common divisor of two integers, which is given below.
Theorem
Let a\text{ and } b be integers, not both zero. For a positive integer d, d = \text{gcd}(a, b) if and only if
(a) d \,|\, a \text{ and } d \,|\, b
(b) Whenever c \,|\, a \text{ and } c \,|\, b, then c \,|\, d
First we will suppose that d = \text{gcd}(a, b) and prove that conditions (a) and (b) hold.
Since d = \text{gcd}(a, b), by definition, d \,|\, a \text{ and } d \,|\, b. Therefore, condition (a) holds.
From part (g) of the theorem we have already proved we know that if c \,|\, a \text{ and } c \,|\, b, then c \,|\, (ax + by) for arbitrary integers x \text{ and } y.
Also, in light of the theorem we just proved above, we can express d as d = ax + by for some integers x \text{ and } y.
Thus c \,|\, d and condition (b) holds.
Next, let us prove the converse i.e., if there exists a positive integer d such that conditions (a) and (b) hold, then d = \text{gcd}(a, b).
From part (b), we know that if c is a positive common divisor of a \text{ and } b, then c \,|\, d. If c \,|\, d, part (f) of the theorem we have already proved lets us conclude that c \leq d. Also, from (a) we know that d is the positive common divisor of a \text{ and } b. Hence, by definition, d = \text{gcd}(a, b).
Relatively Prime Integers
It might happen that 1 \text{ and } -1 are the only common divisors of a given pair to integers a \text{ and } b and consequently, \text{gcd}(a, b) = 1.
For example, \text{gcd}(3, 7) = \text{gcd}(-15, 22) = \text{gcd}(-41, -42) = 1.
This situation occurs offer enough to merit a definition.
Definition
Two integers a \text{ and } b, not both of which are zero, are said to be relatively prime whenever \text{gcd}(a, b) = 1.
The following theorem expresses relatively prime integers as linear combinations.
Theorem
Let a \text{ and } b be integers, not both zero. Then a \text{ and } b are relatively prime if and only if there exist integers x \text{ and } y such that 1 = ax + by.
We prove this theorem by showing that the following assertions are true :
- If integers a \text{ and } b, not both of which are zero, are relatively prime then there exist integers x \text{ and } y such that 1 = ax + by
- If a \text{ and } b are integers, not both of which are zero, and there exist integers x \text{ and } y such that 1 = ax + by then a \text{ and } b are relatively prime.
If a \text{ and } b are relatively prime, then \text{gcd}(a, b) = 1. The Theorem stated above guarantees the existence of integers x \text{ and } y such that \text{gcd}(a, b) = ax + by. Since \text{gcd}(a, b) = 1, it implies that 1 = ax + by.
As for the converse, i.e., assertion (2), suppose that 1 = ax + by for some choice of x \text{ and } y and that d = \text{gcd}(a, b). Since d \,|\, a \text{ and } d \,|\, b, part (g) of the Theorem stated above yields d \,|\, (ax + by). Since ax + by = 1, d \,|\, 1. Since d is a positive integer, part (b) of the Theorem stated above lets us conclude that d = 1. Since d = \text{gcd}(a, b) and d = 1, it follows that \text{gcd}(a, b) = 1. Therefore, a \text{ and } b are relatively prime.
As an aside, let us consider an alternate way of proving the converse.
Suppose there exists integers x \text{ and } y such that 1 = ax + by. The Theorem stated above guarantees the existence of integers x \text{ and } y such that \text{gcd}(a, b) = ax + by. Therefore, \text{gcd}(a, b) = 1, which implies that a \text{ and } b are relatively prime.
Is this proof correct? Unfortunately, not. The fallacy in this argument is the assumption that the integers x \text{ and } y in 1 = ax + by is the same as the integers x \text{ and } y in \text{gcd}(a, b) = ax + by. However, this is incorrect since \text{gcd}(a, b) could equal ax^\prime + by^\prime such that x \neq x^\prime \text{ and } y \neq y^\prime.
The point of this discussion is that while writing proofs one should always guard against making such fallacious arguments.
Application
We will now apply this theorem to prove an interesting observation made by Pythagoras.
Pythagoras. The number \sqrt{2} is irrational.
Before proving this assertion, we will elucidate a bit about its origin and significance.
An irrational number is a number that cannot be expressed as a ratio of two integers. That is, any number that cannot be written in the form \dfrac{p}{q}, where p is an integer and q is a non-zero integer is an irrational number.
Interestingly, the first irrational number to be discovered was \sqrt{2}. The Pythagoreans were an ancient Greek philosophical university and religious brotherhood which originated in the sixth century B.C. They stumbled upon \sqrt{2} as the length of a diagonal of a square with side lengths 1. They held the doctrine that all is number and viewed numbers, particularly whole numbers i.e., integers as fundamental to understanding the universe. Since they believed that everything could be explained by relationship between integers, when it was proven that the number \sqrt{2} did not fit this doctrine, they killed the man who proved it. 😱 The Greeks then rationalized this discrepancy by supposing that \sqrt{2} was an anomaly of the square. However, when they discovered \sqrt{3}, they ultimately had to confront the existence of irrational numbers, which complicated their understanding of the universe.
Now that we know about the macabre history of \sqrt{2} lets prove that it is irrational.
Proof. Suppose \sqrt{2} is not irrational. Then it can be expressed as a ratio of two integers i.e.,
\sqrt{2} = \frac{a}{b}with \text{gcd}(a, b) = 1.
Consequently, it follows from the theorem we have just proved that there must exist integers r \text{ and } s satisfying ar + bs = 1.
As a result,
\sqrt{2} = \sqrt{2} \cdot 1 = \sqrt{2} (ar + bs)Since \sqrt{2} = \dfrac{a}{b}, it follows that
a = \sqrt{2} b \quad \quad \text{ and } \quad \quad b = \frac{a}{\sqrt{2}}Therefore,
\sqrt{2} = \sqrt{2} (ar + bs) = \sqrt{2} \bigg(\sqrt{2} br + \frac{a}{\sqrt{2}}s\bigg) = 2br + asSince 2br + as is the sum of products of integers, it is an integer. Hence, this representation of \sqrt{2} leads us to conclude that \sqrt{2} is an integer, which is an obvious impossibility.
Hence, our supposition that \sqrt{2} is not irrational leads to a contradiction. Since \sqrt{2} can only be either irrational or not irrational and \sqrt{2} being not irrational leads to a contradiction, it must be the case that \sqrt{2} is irrational.
This theorem we have just proved leads to an observation stated below.
Corollary 1
If a \text{ and } b are integers, not both of which are zero, and \text{gcd}(a, b) = d, then \text{gcd}(a/d, b/d) = 1.
The Theorem stated above guarantees the existence of integers x \text{ and } y such that \text{gcd}(a, b) = ax + by. Since \text{gcd}(a, b) = d, it follows that
d = ax + by
Dividing each side of this equation by d, we get
1 = \Big(\frac{a}{d}\Big)x + \Big(\frac{b}{d}\Big)ySince d is the greatest common divisor of a \text{ and } b, d \,|\, a \text{ and } d \,|\, b. Therefore, \dfrac{a}{d} \text{ and } \dfrac{b}{d} are integers. Hence by the theorem stated above, \dfrac{a}{d} \text{ and } \dfrac{b}{d} are relatively prime i.e., \text{gcd}(a/d, b/d) = 1.
For example, \text{gcd}(21, -49) = 7 and \text{gcd}(21/7, -49/7) = \text{gcd}(3, -7) = 1 which concurs with the statement of the corollary.
If a \,|\, c \text{ and } b \,|\, c, does it imply that ab \,|\, c ?
In order to prove or disprove this assertion, we will first try to find a counterexample that disproves this claim. If we are unable to do so, then we will try and prove the assertion.
For example, when a = 4, b = 6 \text{ and } c = 12, 4 \,|\, 12 \text{ and } 6 \,|\, 12 but 4 \cdot 6 \nmid 12.
However, when a = 2, b = 3 \text{ and } c = 12, 2 \,|\, 12 \text{ and } 3 \,|\, 12 and 2 \cdot 3 \,|\, 12.
We can see that when a \text{ and } b are relatively prime, then the assertion is true. This leads us to corollary 2.
Corollary 2
If a \,|\, c \text{ and } b \,|\, c, with \text{gcd}(a, b) = 1, then ab \,|\, c.
Since a \,|\, c \text{ and } b \,|\, c, there exist integers r \text{ and } s such that c = ar = bs.
The relation \text{gcd}(a, b) = 1 implies that
1 = ax + by
for some choice of integers x \text{ and } y.
Multiplying the above equation by c, we get
c = 1 \cdot c= (ax + by)c = acx + bcy
Making the appropriate substitutions on the right hand side of the equation yields,
c = a(bs)x + b(ar)y = ab(sx + ry)
which as a divisibility statement can be written as ab \,|\, c.
Our next theorem which also relates to integers a \text{ and } b being relatively prime is of fundamental importance.
Theorem
Euclid’s Lemma
If a \,|\, bc, with \text{gcd}(a, b) = 1, then a \,|\, c.
Theorem states that if \text{gcd}(a, b) = 1, then there exist integers x \text{ and } y such that
1 = ax + by
Multiplying the above equation by c, we get
c = 1 \cdot c = (ax + by)c = acx + bcy
Since a \,|\, ac and a \,|\, bc, from part (g) of the Theorem stated above we can infer that a \,|\, (acx + bcy).
Since c = acx + bcy, a \,|\, c.
Next Topic : The Euclidean Algorithm