number theory - $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!

Answer

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$$

As explained there, a solution can be efficiently computed by gcd calculations.