gcd of 3 integers

Consider three positive integers a, b, and c, and let d = gcd(a,b). Prove that the greatest number dividing all three of a,b,c is gcd(d,c). We know that the common divisors of a and b are the divisors of d.


I can certainly see why this is true, but I'm not really sure where to start here. Would I break a,b, and c up into their prime factors and say that p(1),...,p(i) are common between all three? Then maybe show that d contains all those factors as well? I'm not really sure how this would exactly work.

Quote:

---

Originally Posted by uberbandgeek6

Consider three positive integers a, b, and c, and let d = gcd(a,b). Prove that the greatest number dividing all three of a,b,c is gcd(d,c). We know that the common divisors of a and b are the divisors of d.


I can certainly see why this is true, but I'm not really sure where to start here. Would I break a,b, and c up into their prime factors and say that p(1),...,p(i) are common between all three? Then maybe show that d contains all those factors as well? I'm not really sure how this would exactly work.

---

Prime factorization would work I think, but it should also follow from the definition of gcd.

For any integers x and y where x and y are not both 0, g=gcd(x,y) iff

1) g | x
2) g | y
3) for all integers z: z | x and z | y implies g | z.

Notice that by this general definition the gcd is unique up to multiplication by units (1 or -1) but by convention we take the positive value.

Still not sure what to start with. I'm thinking "Suppose there is a number k such that k > gcd(d,c) and k divides a,b,c," and show a contradiction, but I don't understand where I should go from there.

Suppose that
Is it clear to you that divides
What if some divides

Quote:

---

Originally Posted by uberbandgeek6

Still not sure what to start with. I'm thinking "Suppose there is a number k such that k > gcd(d,c) and k divides a,b,c," and show a contradiction, but I don't understand where I should go from there.

---

We can actually use direct proof.

Given d = gcd(a,b). Let g = gcd(d,c).

Then by definition,

1) g | d
2) g | c
3) for all z: z | d and z | c implies z | g

(Note that g | d implies g | a and g | b.)

Suppose z | a and z | b and z | c.

From the definition of gcd, z | a and z | b implies z | d.

So z | d and z | c.

Again by definition, z | g.