Problem 39 - Discrete Mathematics with Applications

Question

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

Step-by-Step Solution

Answer

In summary, we have shown that if \(d = gcd(a, b)\), then \(a = md\) and \(b = nd\), where m and n are integers, and a and b are divisible by d. We then found that the gcd of \(m = \frac{a}{d}\) and \(n = \frac{b}{d}\) must be 1, as any common divisor greater than 1 would contradict the fact that d is the greatest common divisor of a and b. Therefore, \(\frac{a}{d}\) and \(\frac{b}{d}\) are relatively prime, proving the statement.

Step 1: Understanding gcd

The gcd of two numbers a and b, denoted as gcd(a, b), is the largest positive integer that divides both a and b without leaving a remainder. In this exercise, we are given that d = gcd(a, b).

Step 2: Rewrite a and b using d

Since d is the gcd of a and b, we can write a = md and b = nd, where m and n are integers.

Step 3: Find the gcd of md/d and nd/d

Now we have to find the gcd of md/d and nd/d. Since they are two fractions, we can simplify them and get that they are equal to m and n respectively, since the d's will cancel out.

Step 4: Show that gcd(m, n) = 1

Let's assume that there exists a common divisor k of m and n, which is greater than 1. Then, there are integers x and y such that m = kx and n = ky, as k divides m and n. Now, we can write a = md = (kx)d and b = nd = (ky)d. So, the greatest common divisor of a and b is, gcd(a, b) = gcd((kx)d, (ky)d) Since k and d are common factors of a and b, it means that gcd(a, b) is at least kd, which contradicts the fact that d is the greatest common divisor of a and b. This contradiction means that our assumption that there exists a common divisor k of m and n, greater than 1, must be false. Therefore, gcd(m, n) = 1.

Step 5: Conclusion

We have shown that the gcd of m and n, which are equal to a/d and b/d respectively, is 1. Thus, when dividing the gcd(d) from a and b, the resulting numbers are relatively prime.

Key Concepts

Relatively Prime Numbers

Understanding the concept of relatively prime numbers is crucial when dissecting the intricacies of the Greatest Common Divisor (gcd). Two numbers are said to be relatively prime if their gcd is 1. This means that, apart from the number 1 itself, there is no other positive integer that divides both numbers without leaving a remainder.

For instance, consider the numbers 8 and 15. Their gcd is 1 since no number other than 1 can divide both evenly. As a result, 8 and 15 are relatively prime, even though neither of them is necessarily a prime number. Understanding this concept helps in seeing the bigger picture in our exercise which showcases that after dividing two numbers by their gcd, the resulting numbers are relatively prime to each other.

Prime Numbers

In mathematics, prime numbers hold a special place due to their unique properties. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. Examples include 2, 3, 5, 7, 11, and so on. It's also interesting to note that 2 is the only even prime number; all other prime numbers are odd, making them relatively prime to all even numbers.

Prime numbers are the 'building blocks' of integers since any integer can be expressed as a product of primes, a fact known as the Fundamental Theorem of Arithmetic. This theorem is a building block in our textbook problem, as it is used to rewrite numbers as multiples of their greatest common divisor, which relates primes to the concept of relative primality.

Integer Division

Integer division involves dividing one integer by another and producing a quotient and possibly a remainder. Unlike division in real numbers that can produce fractions or decimals, integer division deals solely with whole numbers. For example, dividing 15 by 6 yields a quotient of 2 and a remainder of 3, often written as 15 = 6 * 2 + 3. It is key to note that in integer division, the divisor must be a non-zero integer.

This concept is integral to our exercise as the gcd is used to divide both a and b, giving us new integers that exemplify the properties of relative primality. By understanding integer division, students can better grasp how breaking down numbers into their components provides insight into their fundamental relationships.

Proof Techniques in Mathematics

Mathematics relies heavily on proofs to verify the truth of statements. One common proof technique, as used in our example, is 'proof by contradiction.' This method involves assuming the opposite of what we want to prove and then logically deducing a statement that contradicts known facts, thereby proving that the initial assumption must be incorrect.

In our textbook solution, we assume that there's a common divisor greater than 1 and show that this leads to a contradiction with the definition of the gcd. Through this proof, the initial assumption is proven to be false, thus reinforcing the statement that a/d and b/d are relatively prime. Understanding various proof techniques is fundamental to solving complex mathematical problems and is an essential skill for any mathematics student.