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

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

  • $\begingroup$ Marvelous! Thank you very much! $\endgroup$ – Analyst Jul 28 at 22:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.