gcd: greatest common divisor

Definition 2.3.1. Given a, b ∈ ℤ. An element d ∈ ℤ is said to be a greatest common divisor of a and b if

1. d|a, d|b

2. If d'|a, d'|b, then d'|d.

Remark. We said a greatest common divisor and not the greatest common divisor between two elements, because if d verifies i) and ii), also every associate of d (and thus ±d in ℤ) verifies the same conditions. For example, 2 and −2 are both greatest common divisors of 2 and 4. In general, when we talk about the greatest common divisor in ℤ, we mean the positive one, indicated in the following ways:

It is not though defined gcd(0,0), because each x ∈ ℤ divides zero, thus does not exists a greatest divisor.

Definition 2.3.2. Two integers a and b such that gcd(a, b) = 1 are said coprime or relatively prime.  □

The following theorems examine the existence of the gcd.

Proposition 2.3.3. (The Division Algorithm in ℤ) Let a and b two integers with, b ≠ 0. There there exist and are univocally determined two integers q and r such that

(a Dividend, b Divisor, q Quotient, r Remainder).

Proof. Existence: We examine separately the two cases we can observe i.e. a ≥ 0 or a < 0.

a ≥ 0. By applying the induction principle in the form 𝕀 with regards to a. If a = 0, it enough to put q = r = 0, and thus P(0) is true.

Let a > 0. Let's see if the hypothesis P(k) true for all k such 0 ≤ k < a implies P(a) true. If |b| > a, it is enough to put q = 0 and r = a. So we can suppose a ≥ |b|. Then a > a − |b| ≥0 and by the inductive hypothesis P(a − |b|) is true. This means there exist two integers q',r' such that a − |b| = bq' + r', 0 ≤ r' < |b|, from which we can deduce a = |b| + bq' + r'. In the case b > 0 or b < 0 we'll have respectively a = b(q' + 1) + r' or a = b(q − 1) + r', with 0 ≤ r' < |b|, i.e. P(a) is true, with q = q' + 1, r = r', in the case b > 0, and q = q' − 1, r = r', if b < 0. Owing to the inductive principle, P(a) is true for every a.

a < 0. In this case we get −a > 0. There exist thus, from what we have proved in the first part two integers r* and q* such that −a = bq* − r*, with 0 ≤ r* < |b|.

If r* = 0 then a = b(−q*), hence it is sufficient to let q = q* and r = 0. If r* > 0, then a = b(−q*) + (−r*) = b(−q*) − |b| + |b| − r* = b (−q ± 1) + (|b| − r*) with 0 < |b| − r* < |b|. In any case (b > or b < 0) there exist two integers q and r resolving the problem.

Unicity. Let a = bq + r = bq' + r', 0 ≤ r,r' < |b|. Suppose for example r' ≤ r. Then 0 ≤ r' − r = b(q−q'), from which, taking the absolute values

This is possible only if |q − q'| < 1 and |q − q'| = 0, from which q = q' and r = r'.□

Example 2.3.4. 29 = 7 ⋅ 4 + 1, -29 = 4 ⋅ (-7 -1) + (-4 -1) = 4 ⋅ (-8) + 3, 29 = (-4) ⋅ (−7) +1, -29 = −4 ⋅ (7+1) + (4-1).

Theorem 2.3.5 - Let a, b ∈ ℤ, both nonzero, there exists the greatest common divisor d = gcd(a,b). Moreover it is possible to find two integers s and t in ℤ such that d = sa + tb.

Proof. Let

We observe that S ≠ ∅ since a and b are both nonzero. Then there exists a minimum element of S; d = x₀a + y₀b = min S. We want to prove that such an element is a greatest common divisor of a and b.

If c|a and c|b then a = ck and b = ch, thus d = ax + by = ckx + chy = c(kx + hy) i.e. c|d and property ii) in the definition of gcd is verified.

It remains to verify that d|a e d|b. Dividing a by d we get: a = dq + r, with 0 ≤ r < d. We have that,

an element of S. If we want not to contradict the minimality of d, it must be r = 0 thus d|a. Analogously we can prove d | b. We have proved at the same time the existence of gcd(a,b) and its writing in the form d = sa + tb.□

The writing of d = gcd(a, b) of two integers a and b in the form

is known as Bézout's identity. This expression in not unique. For example 1 = 3 ⋅ 7 + (-4) ⋅ 5 = (-2) ⋅ 7 + 3⋅5.

Theorem 2.3.6. If a and b are relatively prime and a | bc, then a| c.

Proof. Assume that (a,b) = 1 and a | bc. Since (a,b) = 1, there are integers m and n such that 1 = am + bn by Lemma 2.16. Since a | bc, there exists an integer q such that bc = aq. Now,

1 = am + bn

multiplying by c

c = acm + bcn

replacing bc = aq into the latter:

c = acm + aqn

Thus

c = a(cm + qn)   ⇒ a | c.□

We've already proved (Proposition 2.2.11) that any prime element in ℤ, is an irreducible element; We are now able to prove that also the converse holds true in ℤ:

Corollary 2.3.7 If a, b divide c and a, b are relatively prime, then ab divides c.

Proof. There are integers m, n such that am + bn = 1. We have c = au and c = bv for certain integers u, v. Then

We've already proved that any prime element in ℤ, is also irreducible (see Proposition 2.2.11). Now we are able to prove that the converse in ℤ holds as well.

Proposition 2.3.8. Every irreducible element in ℤ, is prime.

Proof. We must prove that by being p irreducible element in ℤ, follows that if p divides the product ab, then p divides either a or b. Let ab = ph and suppose p does not divide a. Then, since p has as divisors p and 1, gcd(a,p) = 1. Thus there exist s,t such that 1 = sa + tp. Multiplying by b both sides of the equation, we get b = sab + tpb; since p|ab and p|p, we get p|b.□

Lemma 2.3.9: Let a, b, and c be positive integers with gcd(a, c) = 1. Then gcd(ab, c) = gcd(b, c).

Proof: Let d₁ = gcd(b, c) and d₂ = gcd(ab, c). Now d₁ = gcd(b, c) ⇒[(d₁ divides b) and (d₁ divides c)]. Consequently, d₁ divides ab, and so it follows that d₁ divides d₂.
With gcd(a, c) = 1, there exist integers x and y such that ax + cy = 1. Therefore, abx + bcy = b. Now d₂ = gcd(ab, c) ⇒ [(d₂ divides ab) and (d₂ divides c)], so d₂ divides (ab)x + b(c)y = b. Then [(d₂ divides b) and (d₂ divides c)] ⇒ [d₂ divides d₁]. Finally, since d₁ divides d₂, and d₂ divides d₁, and d₁, d₂ are positive, we have d₁ = d₂ — or gcd(ab, c) = gcd(b, c).□

Proposition 2.3.10. Let a and b be two positive integers. They are coprime if and only if there exist two integers α, β such that

Proof. If a and b are coprime, we have gcd(a, b) = 1 and the claim follows from Bézout’s identity. On the other hand, suppose equation (2.16) holds. Let d be a common divisor of a and b. Then clearly d divides αa + βb too, and so divides 1. Thus either d = 1 or d = −1, and consequently a and b are relatively prime.□

Corollary 2.3.11. Let a and b be two positive integers and let d = gcd(a, b). If a = dn and b = dm, we have gcd(n, m) = 1.

Proof. Equation (2.15) may now be written as

By dividing by d both sides we get

and by applying Proposition 2.3.9 we conclude that n and m are relatively prime.  □

Corollary 2.3.12. Let a, b₁, and b₂ be integers such that a and b₁ are coprime, and so are a and b₂. Then a is coprime with b₁b₂.

Proof. We can write

By multiplying them, we get

proving the claim.□

Lemma 2.3.13: Let a and b be two integers, then gcd(a,b) = gcd(a, a ± b).

Proof. We prove something stronger: every integer which is a common divisor of a and b is also a common divisor of a and a ± b; conversely, every integer which is a common divisor of a and a ± b is also a common divisor of a and b. In math language we show that the two sets:

and

are the same. To prove that the two sets are the same we will show that if we pick an element s in A₁ then s is also an element of A₂ and if we pick an element t ∈ A₂ then t is also an element of A₁: in mathematical language we prove that A₁ ⊆ A₂ and A₂ ⊆ A₁. From the equality condition of the two sets A₁ = A₂ follows that if d = gcd(a,b) then it is also true that d = gcd(a ± b). We need to prove two statements:

1. If x|a and x|b then x|a ± b;

2. If x|a and x|a ± b then x|b.

We know from Lemma 2.2.5 that this is true.□