Consider $n, k ∈ \mathbb{N}$. Prove that $\gcd(n, n + k)\mid k$

Question

Consider $n, k\in\mathbb N$. Prove that $\gcd(n, n + k)\mid k$

Here is my proof. Is it correct?

A proposition in number theory states the following:

$$\forall a, b \in \mathbb{Z}, \ \gcd(n,m)\mid an+bm$$

A corollary (consequence) to this is that if $an+bm=1$ for some $a, b \in \mathbb{Z}$, then $\gcd(n,m)=1$.

Again in our problem $(n+k)-n=k$, therefore we can use this to see that $\gcd(n,n+k)=k$.

Answer 1

I would do it simpler. We know that $\gcd(n, n+k) | n$ and $\gcd(n, n+k)|(n+k)$. From that, it is pretty clear that $\frac{n+k}{\gcd(n, n+k)} = \frac{n}{\gcd(n, n+k)} + \frac{k}{\gcd(n, n+k)}$. The left side is an integer by definition. $\frac{n}{gcd(n, n+k)}$ is also an integer by definition. Therefore, $\frac{k}{\gcd(n, n+k)}$ is also an integer. Result follows.

Answer 2

Even easier $d=\gcd(n,n+k)$

• if $d=1$ then $d \mid k$
• if $d>1$ then $d \mid n$ and $d \mid n+k$ or $d\cdot q_1=n$ and $d\cdot q_2=n+k$. Altogether $d\cdot q_2 = d\cdot q_1 +k$ or $d(q_1-q_2)=k \Rightarrow d \mid k$

Answer 3

We want to show that $\gcd (a, a + k) | k$

Let $\gcd (a, a + k) = d$ say, where $d$ is an integer

$d| a \implies a = md$ , $m$ is an integer

$d| a + k \implies a + k = nd$ , $n$ is an integer

$a + k - a = nd - md $

$k = d (n - m)$

$\implies d | k$

$\implies \gcd(a,a + k) | k$ [as required]