0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ We need $(x,p)=1, (x+kp,q)=1$ $\endgroup$ Aug 22, 2015 at 18:31
  • $\begingroup$ Yes. Since $x \in \mathbb{Z}_p$, we get $(x,p)=1$. Then what's the condition for $k$ such that $(x+kp,q)=1$? More specifically, can we express the condition for $k$ in terms of $x,p,q$? $\endgroup$
    – Paradox
    Aug 22, 2015 at 18:38

1 Answer 1

0
$\begingroup$

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$

$\endgroup$
1
  • $\begingroup$ Thanks for your answer. It is right to me. $\endgroup$
    – Paradox
    Aug 23, 2015 at 2:14

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.