# gcd of 3 integers

• Sep 16th 2010, 06:45 AM
uberbandgeek6
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.
• Sep 16th 2010, 06:48 AM
undefined
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.
• Sep 16th 2010, 07:15 AM
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.
• Sep 16th 2010, 07:28 AM
Plato
Suppose that $e = \gcd \left\{ {c,d} \right\}$
Is it clear to you that $e$ divides $a,~b,~\&~c?$
What if some $f>e$ divides $a,~b,~\&~c?$
• Sep 16th 2010, 07:33 AM
undefined
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.