Why Is gcd(k, n+k) = 1 Exactly When gcd(k, n) = 1?

The statement follows from a basic fact about greatest common divisors: adding a multiple of one integer to another does not change the gcd. Here, the two pairs $(k,n)$ and $(k,n+k)$ have exactly the same common divisors, so their greatest common divisors are equal—not merely both equal to $1$ in the coprime case.

Assume $k$ and $n$ are integers, and use the standard convention that a gcd is nonnegative. Under the common definition of gcd as the greatest positive common divisor, $\gcd(0,0)$ is undefined; some conventions instead define it as $0$. We exclude $k=n=0$ under the former convention.

Compare the common divisors

Let $d$ be a common divisor of $k$ and $n$. Then $d\mid k$ and $d\mid n$, so $d$ also divides their sum:

$$d\mid n+k.$$

Thus every common divisor of $k$ and $n$ is also a common divisor of $k$ and $n+k$.

Now reverse the reasoning. If $d\mid k$ and $d\mid n+k$, then $d$ divides the difference:

$$d\mid (n+k)-k=n.$$

So every common divisor of $k$ and $n+k$ is also a common divisor of $k$ and $n$. The two pairs therefore have the same common divisors. In particular, they have the same greatest common divisor:

$$\gcd(k,n+k)=\gcd(k,n).$$

Deduce the if-and-only-if statement

Two integers are relatively prime (or coprime) when their gcd is $1$. Since the gcds above are equal, they are either both $1$ or both different from $1$. Hence

$$\gcd(k,n+k)=1\quad\Longleftrightarrow\quad\gcd(k,n)=1.$$

This proves both directions at once. If you want to spell them out separately:

• If $\gcd(k,n)=1$, then the gcd identity gives $\gcd(k,n+k)=1$.
• If $\gcd(k,n+k)=1$, the same identity gives $\gcd(k,n)=1$.

Worked example

Take $k=12$ and $n=18$. Then $n+k=30$, and

$$\gcd(12,18)=6,\qquad \gcd(12,30)=6.$$

The common divisors are the same in both cases: $1,2,3,$ and $6$. The gcd is not $1$, so neither pair is coprime.

For a coprime example, take $k=12$ and $n=35$. Then $n+k=47$. Since $12$ and $35$ have no common divisor greater than $1$, the identity gives

$$\gcd(12,47)=\gcd(12,35)=1.$$

You can also check the first gcd directly: $47=3\cdot12+11$, $12=1\cdot11+1$, so the Euclidean algorithm ends at $1$.

A more general version

The same argument works when you add any integer multiple of one number to the other. For integers $a,b$ and $q$,

$$\gcd(a,b+qa)=\gcd(a,b).$$

Indeed, a divisor of $a$ and $b$ divides $b+qa$; conversely, a divisor of $a$ and $b+qa$ divides $(b+qa)-qa=b$. This rule is one of the basic steps in the Euclidean algorithm, which repeatedly replaces a pair of numbers with a pair having the same gcd but smaller entries.

Common mistakes

• Proving only one direction. Showing that common divisors of $k,n$ divide $n+k$ establishes only one inclusion. To prove the gcds are equal, also subtract $k$ from $n+k$ to recover $n$.
• Treating the claim as specific to gcd $1$. The stronger result is $\gcd(k,n+k)=\gcd(k,n)$, regardless of whether that gcd is $1$.
• Assuming positivity is essential. The divisibility argument works for negative integers and for zero as well, as long as the gcd is defined. For example, $\gcd(0,n)=\gcd(0,n+0)=|n|$ when $n\ne0$.
• Ignoring the undefined pair. Under the convention that $\gcd(0,0)$ is undefined, if $k=n=0$, both gcd expressions are undefined, so the stated numerical equality is not applied. Under a convention assigning $\gcd(0,0)=0$, the equality also holds for that pair.

The key idea is that addition and subtraction preserve the set of common divisors when the same term is present in both numbers.