Week 2 - Day 1: Greatest Common Divisors (GCD)

In this session, we focus on the concept of the greatest common divisor (GCD). We’ll explore how to compute GCDs, examine some key properties, and introduce the Euclidean Algorithm. We will also look at examples that illustrate how to express the GCD as a linear combination of two numbers, which is crucial for understanding number theory.

Greatest Common Divisors (GCD)

The greatest common divisor of two integers \(a\) and \(b\), denoted \((a, b)\), is the largest integer \(d\) that divides both \(a\) and \(b\). To illustrate how GCDs work, let’s look at an example using prime factorizations:

Example: GCD and LCM of Two Numbers

Consider the two integers:

\[ a = 2^3 \cdot 3^4 \cdot 7^0, \quad b = 2^5 \cdot 3^5 \cdot 7^{12}. \]

To compute the GCD, we look at the common bases (2, 3, and 7) and take the lowest power for each base:

\[ GCD(a, b) = 2^3 \cdot 3^4 \cdot 7^0 = 3^4. \]

Similarly, the least common multiple (LCM) is found by taking all bases and selecting the highest power of each base:

\[ LCM(a, b) = 2^5 \cdot 3^5 \cdot 7^{12}. \]

Notice that the GCD and LCM are related by the formula:

\[ LCM(a, b) = \frac{ab}{GCD(a, b)}. \]

Example: GCD of Simple Numbers

Next, let’s compute the GCD of 8 and 12:

\[ GCD(8, 12) = 4. \]

We can list several common divisors of 8 and 12: \(-4, -2, -1, 1, 2, 4\). Here, 4 is the greatest common divisor. This example shows that negative numbers can also be common divisors, but we usually consider the positive GCD.

GCD of 1 and Any Integer

An important special case is when one of the numbers is 1. The GCD of any integer and 1 is always 1. For example:

\[ GCD(4, 1) = 1. \]

This leads to the general rule: \(GCD(a, 1) = 1\) for any integer \(a\).

Formal Definition of the GCD

Let \(a, b \in \mathbb{Z}\), not both zero. The greatest common divisor (GCD) of \(a\) and \(b\), denoted \(d\), is an integer that satisfies two properties:

  1. \(d \mid a\) and \(d \mid b\) (i.e., \(d\) divides both \(a\) and \(b\)).
  2. For all \(c \in \mathbb{Z}\), if \(c \mid a\) and \(c \mid b\), then \(c \leq d\) (i.e., \(d\) is greater than or equal to any other common divisor).

Notation and Simple GCD Facts

The GCD of \(a\) and \(b\) is written \((a, b)\). We can establish a few basic facts about GCDs using this notation:

Examples

\[ (12, 20) = 4, \quad (-12, 20) = 4, \quad (12, -20) = 4, \quad (-12, -20) = 4. \]

This shows that the GCD is unaffected by the signs of the numbers. More generally, we can say:

\[ (a, b) = (|a|, |b|). \]

Another useful fact is that \(GCD(a, 0) = |a|\). For example:

\[ GCD(4, 0) = 4 \quad \text{and} \quad GCD(a, 0) = |a|. \]

This applies to any integer \(a\).

Proof: GCD of 12 and 20 is 4

Let’s prove that the GCD of 12 and 20 is indeed 4.

  1. We first verify that \(4 \mid 12\) and \(4 \mid 20\). Since \(12 = 4 \cdot 3\) and \(20 = 4 \cdot 5\), this condition is satisfied.
  2. Now, let \(c \in \mathbb{Z}\) and assume that \(c \mid 12\) and \(c \mid 20\). We need to show that \(c \leq 4\).
  3. By the definition of divisors, \(12 = cq\) and \(20 = cQ\) for some integers \(q\) and \(Q\). We can express 4 as:
    4. \[ 4 = 2(12) - 20 = 2cq - cQ = c(2q - Q). \]
  4. Thus, \(c \mid 4\), meaning that \(c \leq 4\). Therefore, the greatest common divisor is 4. \(\blacksquare\)

Lemma: Common Divisors and the Division Algorithm

This lemma connects the GCD of two integers to their remainders from the division algorithm. Specifically, it tells us that the common divisors of \(a\) and \(b\) are the same as the common divisors of \(b\) and the remainder \(r\) when \(a\) is divided by \(b\). Formally:

\[ \text{Common divisors of } a \text{ and } b = \text{Common divisors of } b \text{ and } r. \]

Thus, we can conclude that:

\[ GCD(a, b) = GCD(b, r), \]

where \(r\) is the remainder when dividing \(a\) by \(b\). This is the foundation of the Euclidean Algorithm, which allows us to repeatedly apply this lemma to reduce the size of the numbers we are working with until we find the GCD.

Example: Computing \(GCD(60, 42)\)

Let’s compute the GCD of 60 and 42 using the lemma:

  • We begin by dividing 60 by 42, giving a remainder of 18: \((60, 42) = (42, 18)\).
  • Next, divide 42 by 18, giving a remainder of 6: \((42, 18) = (18, 6)\).
  • Finally, divide 18 by 6, giving a remainder of 0: \((18, 6) = (6, 0)\).

The last nonzero remainder is 6, so the GCD is \(GCD(60, 42) = 6\).

GCD Theorem: Expressing the GCD as a Linear Combination

One of the most important theorems regarding GCDs is that for any two integers \(a\) and \(b\), not both 0, we can express their GCD as a linear combination of \(a\) and \(b\). This means that there exist integers \(u\) and \(v\) such that:

\[ GCD(a, b) = au + bv. \]

Example: Expressing the GCD of 12 and 20 as a Linear Combination

We already know that \(GCD(12, 20) = 4\). Now, we want to find integers \(u\) and \(v\) such that:

\[ 4 = 12u + 20v. \]

Using the Euclidean Algorithm, we compute the GCD step-by-step and then work backwards to express it as a linear combination:

  • First, divide 20 by 12: \(20 = 12(1) + 8\).
  • Next, divide 12 by 8: \(12 = 8(1) + 4\).
  • Finally, divide 8 by 4: \(8 = 4(2) + 0\).

The last nonzero remainder is 4, so the GCD is 4. Now, we express 4 as a linear combination:

  1. From \(12 = 8(1) + 4\), we get \(4 = 12 - 8\).
  2. Substitute \(8 = 20 - 12\) into this equation:
    3. \[ 4 = 12 - (20 - 12) = 2(12) - 20. \]
  3. Thus, we can express the GCD as \(4 = 12(2) + 20(-1)\).

This linear combination tells us that the GCD of 12 and 20 can be written as \(4 = 12(2) + 20(-1)\).

The Euclidean Algorithm: An Efficient Method for GCDs

The Euclidean Algorithm is an efficient procedure to compute the GCD of two integers by repeatedly applying the division algorithm. At each step, we replace the larger number with the remainder when it is divided by the smaller number. This process continues until the remainder is zero, at which point the GCD is the last nonzero remainder.

Steps of the Euclidean Algorithm

  1. Divide the larger number by the smaller number and record the quotient and remainder.
  2. Replace the larger number with the smaller number, and replace the smaller number with the remainder from step 1.
  3. Repeat this process until the remainder is zero. The last nonzero remainder is the GCD.

Example: Applying the Euclidean Algorithm

Let’s use the Euclidean Algorithm to find the GCD of 710 and 507. We start by applying the division algorithm at each step:

  • First, divide 710 by 507: \(710 = 507(1) + 203\).
  • Next, divide 507 by 203: \(507 = 203(2) + 101\).
  • Next, divide 203 by 101: \(203 = 101(2) + 1\).
  • Finally, divide 101 by 1: \(101 = 1(101) + 0\).

The last nonzero remainder is 1, so the GCD of 710 and 507 is 1.

Expressing 1 as a Linear Combination

  1. Start with the equation \(1 = 203 - 101(2)\).
  2. Substitute \(101 = 507 - 203(2)\) into this equation:
    3. \[ 1 = 203 - = 203(5) - 507(2). \]
  3. Finally, substitute \(203 = 710 - 507(1)\) into this equation:
    4. \[ 1 = (710 - 507)(5) - 507(2) = 710(5) - 507(7). \]

Thus, we have expressed the GCD of 710 and 507 as a linear combination:

\[ 1 = 710(5) - 507(7). \]

This method demonstrates the power of the Euclidean Algorithm not only in finding GCDs but also in expressing them as linear combinations.

Conclusion

In this session, we explored how to compute the GCD of two integers, how to express the GCD as a linear combination, and how to use the Euclidean Algorithm to solve GCD problems efficiently. These techniques are foundational tools in number theory and have broad applications in topics such as modular arithmetic and cryptography. Be sure to practice these methods in the homework assignments to gain proficiency!