Let a be a positive integer. What is $\gcd(a,2a), \gcd(a,2+a)$ and $\gcd(a,1+a)$?

Question

I want to find some arithmetic way of solving these. For the first one:

$$\gcd(1,2) = 1 \Rightarrow 2 = 1*2 + 0 \\ \gcd(a,b) = d \Rightarrow \gcd(ak,bk)=dk,\\ \gcd(a,2a) = a$$

How do you do something like this for the others?

Answer 1

HINT: $\gcd (a,b) = \gcd(a,a-b)$. (Prove this with the Euclidean algorithm if you'd like, or just from the usual definition.)

Answer 2

$\gcd(a,a+k)$ must divide $a$ and $a+k$ and therefore it must divide $(a+k)-a=k.$

So $\gcd(a,a+2)$ must divide $2$ and $\gcd(a,a+1)$ must divide $1$.

Therefore $\gcd(a,a+2)=1 $ or $2$

(if $a$ is odd then $2\nmid a$ so it's $1$; if $a$ is even then $2|a, a+2$ so it's $2$),

and $\gcd(a,a+1)=1$.

Answer 3

• $\gcd(a,2a)=a$ simply because $a\mid 2a$.
• As $\gcd(a,b)=\gcd(a,a-b)$, we have $\gcd(a, 2+a)=\gcd(a,2)=2$ if $a$ is even, $=1$ if $a$ is odd.
• For the same reason, $\gcd(a,a+1)=\gcd(a,1)=1$.