# Thread: Elem Number Theory - gcd theorem in proof

1. ## Elem Number Theory - gcd theorem in proof

ok - so after a long proof that I know is correct, I have come to conclude that:
given: gcd(2a+b, a+2b) = 1 or 2 or 3
I have to prove that this does not equal 2.

I also know (and have proven) that gcd(a,b)=1.

I know I need to show that for d to not equal 2, I would have to pretend and show that when d equals 2, d could not equal 1 - which is false since d has to equal 1.
So to start: Assume gcd(2a+b, a+2b) = 2, then it divides both a and b

help!?

2. Hello,

If 2a+b is even, so is b.
If a+2b is even, so is a.

Bye.

3. but I need to contradict that it equals 2, not 1.

4. He did. Reiterating what wisterville said, if the gcd of both numbers is 2, then that must mean they are both even. Since 2a + b is even, then so must b (even + even = even) and a + 2b being even also implies a is even.

So, 2 is a common factor of both a and b which contradicts that their gcd was 1 which you were given. So, our initial assumption that (2a+b, a+2b) = 2 was wrong.

5. ah! got it! thank you - that makes sense

(sorry for the lack of comprehension a minute ago)