Greatest common divisor of an integer 'a' and its sum with 2.

Question

I need to prove that the $\gcd(a, a+2)$ equals either 1 or 2. Intuitively this makes sense to me. If a is an odd integer then the gcd is 1, if a is even, the gcd is 2. I'm having trouble writing a logical proof of this, however.

I would guess that a has some prime factorization $a = p_1^{e_1} \cdots p_k^{e_k}$. Then $a+2 = p_1^{e_1} \cdots p_k^{e_k} + 2$. If a is even, then that first prime (assuming ordering) is $p_1 = 2$. We can factor out a 2 from $a+2$ as $a+2 = 2(p_1^{e_1 - 1} \cdots p_k^{e_k} + 1)$. Clearly both a and a+2 would be even numbers with gcd = 2$. If a is odd, then we cannot factor out a 2 here.

Am I on the right track with this?

Answer 1

$k|a,k|b\Rightarrow k|ax+by$ for all $x,y$. This follows immediately from the definitions. So if $k|a,k|a+2$, then $k|2$

Answer 2

let $d = \gcd(a, a+2)$
$ \implies d | a$ and $d|(a+2) $
$\implies d|(a+2)-a$

which is same as $d|2$

Answer 3

Proof:

• $a=1\implies\gcd(a+2,a)=\gcd(3,1)=1$

• $a=2\implies\gcd(a+2,a)=\gcd(4,2)=2$

• $a>2\implies\gcd(a+2,a)=\gcd(a,a+2-a)=\gcd(a,2)\leq2$