# $\gcd(p,q) = 1$, but $\gcd(p+k_1N,q)>1$

Suppose that p and q are naturals such that $$\gcd(p,q) = 1$$. Let $$N \in \mathbb{N}$$ be arbitrary and suppose that $$\gcd(p+k_1N,q)>1$$ for some $$k_1 \in \mathbb{Z}$$. Does there exist $$k_2 \in \mathbb{Z}$$ such that $$\gcd(p+k_1N,q+k_2N) = 1$$?

I strongly suspect that this is true, after I ran several computer verifications. However, I can't seem to prove this, nor construct a counterexample. Here's what I've tried though:

Let $$A:= \left\{ a_1,a_2,...,a_n \right\}$$ be the prime factors of $$p$$, $$B:= \left\{ b_1,b_2,...,b_m \right\}$$ the prime factors of $$q$$ and $$C:= \left\{ c_1,c_2,...,c_l \right\}$$ the prime factors of $$p+k_1N$$. Then if we list the common prime factors between $$p+k_1N$$ and $$q$$ as $$\left \{ c_i,c_{i+1},...,c_{i+j} \right \}$$, then because they all divide $$p+k_1N$$ and none of them divides $$p$$ (otherwise $$\gcd(p,q) > 1$$), we must have that none of them divides $$k_1N$$ so, in particular, none of them divides $$N$$. Thus $$\gcd(p+k_1N,q+N) \neq \gcd(p+k_1N,q) \neq 1$$.

I hope to continue in this fashion the process of removal of common factors by adding clever multiples of $$N$$ to q until we end up removing all of them, but I can't see how.

I don't know if this is a known result or not since I couldn't find it anywhere (although it looks very elementary).

Thank you in advance!

By here if $$\gcd(a,b,c)=1$$ then there exists $$k_2$$ such that $$\!\!\overbrace{\gcd(\color{#c00}ak_2\!+\color{#0a0}b,c) = 1}^{\large\ \ \gcd(\color{#c00}Nk_2\ +\ \color{#0a0}q,\,\,Nk_1+p)\ }\!\!\!,\,$$ true for OP by $$\gcd(\color{#c00}a,\color{#0a0}b,c) = \gcd(\color{#c00}N,\color{#0a0}q,\,Nk_1\!+\!p) = \gcd(N,q,p) = 1,\ \ {\rm by}\ \ \gcd(p,q) = 1\qquad$$