Week 2 - Day 2: GCD Theorem and Relatively Prime Integers

This session delves into the properties of the greatest common divisor (GCD), linear combinations, and relatively prime integers. We begin with the GCD theorem and its proof, followed by a discussion on prime numbers and relatively prime integers.

The GCD Theorem

Theorem: For any two integers \(a, b \in \mathbb{Z}\) (with at least one of them nonzero), there exist integers \(u\) and \(v\) such that:

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

Proof of the GCD Theorem

The proof of this theorem relies on the well-known fact that we can express the GCD of two integers as a linear combination of those integers. Let's go through this step by step:

Special Case: When One of the Numbers is Zero

If one of the numbers, say \(b\), is zero, the theorem is trivially true. In this case:

\[ GCD(a, 0) = a = a(1) + 0(0). \]

Complete Induction for General Case

For the general case, where both \(a\) and \(b\) are nonzero, we proceed by using **complete induction** on \(k = \min\{a, b\}\).

Base Case: \(k = 1\)

When \(k = 1\), either \(a\) or \(b\) is equal to 1. Without loss of generality, assume \(b = 1\). Then:

\[ GCD(a, 1) = 1 = a(0) + 1(1). \]

This confirms the base case.

Inductive Step

Now, assume the theorem holds for all integers with \(\min\{a, b\} < k\). We aim to show that the theorem is true for \(k\).

Let’s assume \(b \leq a\) (since the other case follows similarly). Thus, \(k = \min\{a, b\} = b\). We apply the **Division Algorithm**:

\[ a = bq + r, \]

where \(q\) is the quotient and \(r\) is the remainder with \(0 \leq r < b\). From our homework and previous results, we know that:

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

Since \(r < b\), we can apply the inductive hypothesis, which gives:

\[ GCD(b, r) = bU + rV, \]

for some integers \(U\) and \(V\). Substituting \(r = a - bq\) into this expression, we get:

\[ GCD(a, b) = bU + (a - bq)V = aV + b(U - qV). \]

Thus, \(GCD(a, b)\) is expressed as a linear combination of \(a\) and \(b\), completing the inductive step and proving the theorem. \( \blacksquare \)

Prime Numbers

Next, we introduced the concept of prime numbers, a foundational topic in number theory.

Definition of a Prime Number

An integer \(p \neq 0, \pm 1\) is called prime if for all divisors \(d \in \mathbb{Z}\), if \(d \mid p\), then \(d = \pm 1\) or \(d = \pm p\). This means that a prime number has no divisors other than 1 and itself (including their negative counterparts).

Remark on Prime Divisors

In the next section, we will prove a fundamental property of prime numbers:

  • \(p \mid ab \Rightarrow p \mid a\) or \(p \mid b\).

Example

If \(p = 2\), the above statement can be interpreted as: "If the product is even, then at least one of the factors must be even."

Relatively Prime Integers

Two integers are said to be relatively prime if their GCD is 1. That is, if \(GCD(a, b) = 1\), then \(a\) and \(b\) are relatively prime.

Corollary: Expressing 1 as a Linear Combination

If two integers \(a\) and \(b\) are relatively prime, then there exist integers \(u\) and \(v\) such that:

\[ 1 = au + bv. \]

Example: Finding \(x\) and \(y\)

Let’s apply this idea to the following example. We want to find integers \(x\) and \(y\) such that:

\[ 25x + 36y = 1. \]

We use the Euclidean algorithm to compute the GCD of 25 and 36, and then express 1 as a linear combination of these two numbers.

  1. \(36 = 25(1) + 11\)
  2. \(25 = 11(2) + 3\)
  3. \(11 = 3(3) + 2\)
  4. \(3 = 2(1) + 1\)

Now, we express 1 as a linear combination, working step by step:

\[ 1 = 3 + 2(-1) \]

Substitute \(3 = 25 - 11(2)\):

\[ 1 = [25 - 11(2)] + 2(-1) = 25(1) + 11(-2) + 2(-1) = 25(1) + 11(-3). \]

Next, substitute \(11 = 36 - 25(1)\):

\[ 1 = 25(1) + [36 - 25(1)](-3) = 25(1) + 36(-3) - 25(-3) = 25(4) + 36(-3). \]

This shows that \(25(4) + 36(-3) = 1\).

Thus, \(25(4) + 36(-9) = 1\), and the integers \(x = 4\) and \(y = -9\) satisfy the equation.

Theorem 1.4: Equivalent Condition for Relatively Prime Integers

Theorem: Let \(p, a \in \mathbb{Z}\). Then, \(p\) and \(a\) are relatively prime if and only if for all \(b \in \mathbb{Z}\),

\[ p \mid ab \Rightarrow p \mid b. \]

Example: Applying Theorem 1.4

Let’s consider the example of \(p = 25\) and \(a = 36\), where \(GCD(25, 36) = 1\). According to the theorem, this implies that for all integers \(b\), if \(25 \mid 36b\), then \(25 \mid b\).

This highlights a key property of relatively prime integers: their inability to share any common factors (other than 1) makes this divisibility condition possible.

Proof of Theorem 1.4 (One Direction)

We’ll prove the forward direction of this theorem, which states that if \(p\) and \(a\) are relatively prime, then for all integers \(b\), \(p \mid ab \Rightarrow p \mid b\).

Let \(p, a \in \mathbb{Z}\) and assume that \(p\) and \(a\) are relatively prime, i.e., \(GCD(p, a) = 1\). We want to prove that for all \(b \in \mathbb{Z}\), if \(p \mid ab\), then \(p \mid b\).

Step 1: Using the Linear Combination of \(p\) and \(a\)

By the corollary we covered earlier, since \(GCD(p, a) = 1\), there exist integers \(u\) and \(v\) such that:

\[ 1 = pu + av \]

This expression shows that 1 can be written as a linear combination of \(p\) and \(a\), which is a key part of the proof.

Step 2: Multiplying by \(b\)

Now, multiply both sides of the equation by \(b\):

\[ b = b(1) = b(pu + av) = bpu + abv. \]

Notice that we’ve expressed \(b\) as a sum of two terms: \(bpu\) and \(abv\).

Step 3: Applying the Assumption \(p \mid ab\)

Since we know from the assumption that \(p \mid ab\), we can see that \(p\) divides the second term, \(abv\), as well as the first term, \(bpu\), because \(p \mid pu\).

Therefore, \(p\) divides the entire right-hand side of the equation, which is \(b\). This completes the proof. \( \blacksquare \)

Conclusion

This theorem gives us a practical way to understand the relationship between relatively prime integers and divisibility, which is particularly useful when working with linear combinations and modular arithmetic.