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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .