Proving Greatest Common Divisor of a,b,c | Abstract Algebra 1

[silvermane]

1. The problem statement:
Consider 3 positive integers, a, b, c. Let $$d_{1}$$ = gcd(b,c) = 1. Prove that the greatest number dividing all three of a, b, c is gcd($$d_{1}$$,c)


3. My go at the proof and thoughts:

Well, I know that the common divisors of a and b are precisely the divisors of $$d_{1}$$

I also know that to get the gcd(a,b,c) we need to consider a,b's gcd with c to get the overall gcd for all three numbers.

I think that I need to write it as a linear combination for a,b, and c, but I'm stuck. This problem seems easy too, but I think there's something that I'm missing.

 

[mighty2000]

Hi there,

I can understand your frustration with this problem. However, let me assure you that it is indeed a simple proof that just requires a bit of logical thinking. I'll walk you through the steps and hopefully, it will make more sense to you.

First, let's restate the problem: we have three positive integers, a, b, and c, where d_{1} = gcd(b,c) = 1. Our goal is to prove that the greatest number dividing all three of a, b, and c is gcd(d_{1},c).

To start off, let's consider the definition of gcd: it is the largest positive integer that divides all given numbers. So, if we can show that the greatest number dividing a, b, and c is also a divisor of d_{1} and c, then we have proven our statement.

Now, we know that d_{1} = gcd(b,c) = 1, which means that there are no common divisors between b and c besides 1. This also means that d_{1} does not have any factors other than 1, making it the greatest number dividing both b and c. So, we can say that d_{1} is a divisor of both b and c.

Next, let's consider a, b, and c. We know that d_{1} is a divisor of b and c, so it is also a divisor of their greatest common divisor, which is gcd(a,b,c). This means that d_{1} is a divisor of gcd(a,b,c).

Now, let's look at c. Since d_{1} is a divisor of c, we know that it is also a divisor of gcd(d_{1},c). This is because gcd(d_{1},c) is the largest number that divides both d_{1} and c, and since d_{1} is a divisor of c, it must also divide gcd(d_{1},c).

Therefore, we have shown that d_{1} is a divisor of both gcd(a,b,c) and gcd(d_{1},c), which means that it must also be a divisor of their greatest common divisor. And since d_{1} is the greatest number that divides both b and c, it must also be the greatest number that divides all three of a, b, and c.

I hope this helps clarify the proof for you. Remember