What's the condition for (x+kp) and pq being coprime?

Question

Suppose $p$ and $q$ are large primes and $N=pq$.

$x$ is an arbitrary integer in $\mathbb{Z}_p$ and $k$ is a random integer.

Then what is the condition for $k$ (suppose $x$ is fixed) such that $(x+kp)$ and $N=pq$ are coprime?

Answer 1

Since $p$ and $q$ are prime, a number $n$ is coprime to $N$ if and only if $n\ne 0\ (\ mod\ p)$ and $n\ne 0\ (\ mod\ q)$. It is easy to see that $x+kp\ne 0\ (\ mod \ p\ )$ is equivalent to $x\ne 0\ (\ mod\ p\ )$. If this does not hold, $x+pq$ cannot be coprime to $N$. The other condition is simply $x+kp\ne 0\ (\ mod\ q\ )$, giving $k\ne -xp^{-1}\ (\ mod\ q\ )$, where $p^{-1}$ is the multiplicative inverse of $p$ in $\mathbb Z_q$