Problem 10 - A Computational Introduction to Number Theory and Algebra

Question

Show that for all integers \(a, b\) with \(d:=\operatorname{gcd}(a, b) \neq 0\), we have \(\operatorname{gcd}(a / d, b / d)=1\)

Step-by-Step Solution

Answer

Question: Show that if the greatest common divisor of two integers \(a\) and \(b\) is \(d (\neq 0)\), then the greatest common divisor of \(a/d\) and \(b/d\) is 1. Answer: If the gcd of two integers \(a\) and \(b\) is \(d\), then the gcd of \(a/d\) and \(b/d\) is 1 because any common divisor greater than 1 would contradict the fact that \(d\) is the greatest common divisor of \(a\) and \(b\).

Step 1: Recall the definition of the greatest common divisor

The greatest common divisor (gcd) of two integers \(a\) and \(b\), denoted by \(\operatorname{gcd}(a, b)\), is the largest positive integer that divides both \(a\) and \(b\) without leaving a remainder.

Step 2: Apply the definition to the given integers

We are given that the greatest common divisor of \(a\) and \(b\) is \(d\), that is, \(\operatorname{gcd}(a, b) = d\). By definition, this means that \(d\) is the largest integer that divides both \(a\) and \(b\) without leaving a remainder. Since \(d \neq 0\), let \(a = d \cdot p\) and \(b=d \cdot q\) for some integers \(p\) and \(q\). Then, the problem reduces to showing that \(\operatorname{gcd}(p, q) = 1\).

Step 3: Suppose there is a common divisor of \(p\) and \(q\)

Let's assume that there is a divisor \(r\) such that it divides both \(p\) and \(q\) (i.e., \(r \mid p\) and \(r \mid q\)), and \(r > 1\). We'll try to derive a contradiction by showing that \(r\) can also divide \(a\) and \(b\), which would contradict the fact that \(d\) is the greatest common divisor of \(a\) and \(b\).

Step 4: Show that the common divisor would also divide \(a\) and \(b\)

Since \(r \mid p\) and \(r \mid q\), we can write \(p = r \cdot m\) and \(q = r \cdot n\) for some integers \(m\) and \(n\). Now, let's look at \(a\) and \(b\): \(a = d \cdot p = d \cdot (r \cdot m) = (d \cdot r) \cdot m\) \(b = d \cdot q = d \cdot (r \cdot n) = (d \cdot r) \cdot n\) Notice that in both cases, we have expressed \(a\) and \(b\) as a multiple of \(d \cdot r\). This implies that \(d \cdot r\) is a divisor of both \(a\) and \(b\).

Step 5: Derive a contradiction and conclude that the gcd of \(p\) and \(q\) is 1

Since \(d \cdot r\) is a divisor of both \(a\) and \(b\), and \(r > 1\), the product \(d \cdot r\) is larger than \(d\). This contradicts the fact that \(d\) is the greatest common divisor of \(a\) and \(b\). Therefore, our assumption that there exists a divisor \(r > 1\) for both \(p\) and \(q\) must be false. The only divisor left for both \(p\) and \(q\) is 1. Hence, \(\operatorname{gcd}(p, q) = 1\), or equivalently, \(\operatorname{gcd}(a / d, b / d)=1\).

Key Concepts

GCD Definition

Understanding the greatest common divisor (GCD) is a fundamental concept in number theory, essential for mastering various mathematical exercises, including problems on divisibility and simplification of fractions. At its core, the GCD of two integers, say a and b, is the largest positive integer d that divides both numbers without leaving a remainder. In other words, d = gcd(a, b) implies that d is the maximum number that can exactly divide a and b.

This concept is pivotal not only for mathematical proofs but also in applications such as reducing fractions to their simplest form. For example, if we are given a fraction a/b, to simplify it, we would divide both the numerator and the denominator by their gcd. If the gcd of a and b turns out to be 1, the fraction is already in its simplest form, indicating that a and b are coprime—another term for mutually prime integers.

Integer Factorization

Integer factorization is the process of breaking down a number into a set of other numbers, or factors, which, when multiplied together, give the original number. This method is crucial when we try to determine the GCD. For instance, consider the number 12. Its factorization would be 2 × 2 × 3, or 2² × 3. Knowing the prime factorization of numbers enables us to find their GCD efficiently by taking the product of the lowest powers of common prime factors.

In the context of our exercise, breaking down a and b into their prime factors would have provided another proof method for demonstrating that \(gcd(a / d, b / d)=1\). After dividing a and b by d, their common factors are effectively canceled out, leaving behind a pair of coprime integers whose GCD is necessarily 1.

Divisibility

At the heart of many number theory concepts lies divisibility, an easily visualized principle. An integer a is divisible by another integer d, if after dividing a by d, the remainder is zero. The notation for this is \(d \mid a\), read as 'd divides a'.

Divisibility is directly linked with finding the GCD because the GCD is, by its very nature, a divisor of the numbers in question. It is employed in every step of our textbook exercise to establish relationships between numbers, and to show that if a third number divided both p and q, then it would also divide the original integers a and b. Divisibility rules are also indispensable tools used to simplify problems and to prove or disprove the possibility of certain numerical relationships, such as in proofs by contradiction.

Proof by Contradiction

Proof by contradiction is a powerful deductive reasoning approach, where we assume the opposite of what we aim to prove, and then show that this assumption leads to a logical impossibility. In the given exercise, after positing that the GCD of p and q might be greater than 1, this assumption eventually leads to a contradiction, proving it incorrect.

This method hinges on the laws of logic which state that a statement and its negation cannot both be true. When the negation of a statement leads to a contradiction, the original statement must be true. By showing that assuming there is a common divisor greater than 1 results in a larger GCD for a and b than d, which is against our precondition, we confirm that our initial statement is true: \(gcd(a / d, b / d) = 1\). Thus, this method elegantly wraps up the proof that the only common divisor for p and q is 1, reinforcing the initial definition of GCD and the properties of divisibility.