In the paper Safe Prime Generation with a Combined Sieve by Michael J. Wiener, the author states:

For any small odd prime $r$, we can eliminate candidates for $q$ that are congruent to $(r − 1)/2\mod r$ because they lead to $p$ being divisible by $r$.

(where $p = 2q + 1$)

But he did not explain why for the uninitiated. As such I would like to know why $(p-1)/2 \equiv (r-1)/2 \mod r$ means that $p \equiv 0 \mod r$.

Or to put it another way, why does $q \equiv (r-1)/2 \mod r$ mean that $2q \equiv -1 \mod r$?

  • 1
    $\begingroup$ Multiply by $2$. $\endgroup$ – André Nicolas Jun 14 '11 at 15:58
  • $\begingroup$ @user6312: Oh, now I feel dumb. Thanks! But I can't mark a comment as an answer. $\endgroup$ – jnm2 Jun 14 '11 at 16:00
  • $\begingroup$ That's OK, I knew that quickly enough would come an answer that you could accept. $\endgroup$ – André Nicolas Jun 14 '11 at 16:08

Just expand:

$$\begin{eqnarray} q&\equiv&(r-1)/2\mod r\\ 2q&\equiv&r-1\mod r\\ 2q&\equiv&-1\mod r \end{eqnarray}$$


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.