Problem 34 - Discrete Mathematics with Applications

Question

Let \(a, b, c,\) and \(n\) be any positive integers and \(p\) be any prime. Prove each. Let \(a > b .\) Then \(\operatorname{gcd}\\{a, b\\}=\operatorname{gcd}\\{a, a-b\\}\).

Step-by-Step Solution

Answer

Write the prime factorizations of \(a\) and \(b\) as \(a = p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}\) and \(b = p_1^{b_1}p_2^{b_2}\cdots p_k^{b_k}\). Then, write the prime factorization of \((a-b)\) as \((a-b) = p_1^{c_1}p_2^{c_2}\cdots p_k^{c_k}\). Notice that \(\gcd(a, b) = p_1^{\min(a_1, b_1)}p_2^{\min(a_2, b_2)} \cdots p_k^{\min(a_k, b_k)}\) and \(\gcd(a, a-b) = p_1^{\min(a_1, c_1)}p_2^{\min(a_2, c_2)} \cdots p_k^{\min(a_k, c_k)}\). We must show that \(\min(a_1, b_1) = \min(a_1, c_1)\), \(\min(a_2, b_2) = \min(a_2, c_2)\), ..., and \(\min(a_k, b_k) = \min(a_k, c_k)\). Since this holds for every \(i\), we can conclude that \(\gcd(a, b) = \gcd(a, a-b)\), proving the given statement.

Step 1: Write down the prime factorization of a and b

Since a and b are positive integers, they can be written in terms of their prime factors. Let's denote the prime factorization of a as \(a = p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}\), and the prime factorization of b as \(b = p_1^{b_1}p_2^{b_2}\cdots p_k^{b_k}\), where \(p_i\) are prime numbers and \(a_i, b_i\) are their respective exponents.

Step 2: Write down the prime factorization of a-b

Since a and b are positive integers, and \(a > b\), then their difference, \((a-b)\) is also a positive integer and hence can be written in terms of its prime factors. Let's denote the prime factorization of \(a-b\) as \((a-b) = p_1^{c_1}p_2^{c_2}\cdots p_k^{c_k}\), where \(p_i\) are prime numbers and \(c_i\) are their respective exponents.

Step 3: Analyze the Greatest Common Divisors (GCDs)

To prove that \(\gcd(a, b) = \gcd(a, a-b)\), we will analyze the GCDs in terms of their prime factorization. The GCD of a and b is formed by the prime factors they have in common taken with the lowest exponent, so \(\gcd(a, b) = p_1^{\min(a_1, b_1)}p_2^{\min(a_2, b_2)} \cdots p_k^{\min(a_k, b_k)}\). The GCD of a and (a-b) is formed by the prime factors they have in common taken with the lowest exponent as well. The prime factorization of \((a-b)\) can be expressed as a function of the prime factorizations of a and b since \((a-b) = a - b = p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k} - p_1^{b_1}p_2^{b_2}\cdots p_k^{b_k}\). As a result, we can deduce that the GCD of a and \((a-b)\) will also include the same common prime factors as the GCD of a and b, so \(\gcd(a, a-b) = p_1^{\min(a_1, c_1)}p_2^{\min(a_2, c_2)} \cdots p_k^{\min(a_k, c_k)}\).

Step 4: Prove that the GCDs are equal

Now we need to show that \(\gcd(a, b) = \gcd(a, a-b)\). To do this, we need to show that \(\min(a_1, b_1) = \min(a_1, c_1)\), \(\min(a_2, b_2) = \min(a_2, c_2)\), ..., and \(\min(a_k, b_k) = \min(a_k, c_k)\). From the prime factorization of \((a-b)\), for every \(i\), we have \[c_i \leq \min(a_i,b_i).\] Therefore, for every \(i\), we can say that \[\min(a_i, c_i) \leq \min(a_i, b_i). \] Similarly, we can reverse the roles of \(a-b\) and \(b\) in our analysis and get that \[\min(a_i, b_i) \leq \min(a_i, c_i).\] Combining these two inequalities, we arrive at: \[\min(a_i, c_i) = \min(a_i, b_i).\] Since this holds for every \(i\), we can conclude that: \[\gcd(a, b) = \gcd(a, a-b)\] This proves the given statement that if \(a > b\), then \(\gcd(a, b) = \gcd(a, a-b)\).

Key Concepts

Prime Factorization

Understanding the concept of prime factorization is essential when dealing with greatest common divisors (GCD) of positive integers. Prime factorization is the process of breaking down a number into its building blocks—prime numbers, which are numbers greater than 1 that have no positive divisors other than 1 and themselves.

When we express a positive integer as a product of prime numbers, we're conducting what is known as its prime factorization. For example, the prime factorization of 12 is represented as \( 2^2 \cdot 3 \). In the given exercise, the integer \( a \) can be written as \( p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k} \) where \( p_i \) are the distinct prime factors and \( a_i \) are the respective exponents.

This technique not only simplifies the process of finding the GCD of two numbers but also deepens the student's comprehension of the fundamental building blocks of numbers in mathematics.

Positive Integers

Positive integers, often referred to as natural numbers, are the numbers starting from 1 and increasing indefinitely. They are essential for counting discrete objects and form the backbone of basic arithmetic. Each positive integer has unique prime factors and these prime factors are crucial when computing the GCD.

In our exercise, both \( a \) and \( b \) are positive integers, with \( a > b \). The condition that \( a \) is greater than \( b \) guarantees that the difference \( a-b \) is also a positive integer. The prime factorization of this difference, although possibly different from that of \( a \) or \( b \) itself, shares common factors with them which is pivotal to determining the GCD, thereby illustrating how properties of positive integers underpin fundamental operations in number theory.

Proof Techniques

Proof techniques are varied and multifaceted tools used in mathematics to validate conjectures, theorems, and statements. In our example, the proof utilizes direct proof and substitution methods to establish the equality of GCDs.

A direct proof is built on logical deduction from known truths, whereas a substitution method replaces parts of a statement with equivalent expressions to simplify the proof or to draw parallels. By systematically showing that each prime factor's minimum power in \( a \) and \( b \) will be equal to its minimum power in \( a \) and \( a-b \) for all primes present, the proof confirms the validity of the initial statement. These are core skills in mathematical rigor and are key to advancing in more complex and abstract areas of mathematics.