Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
Multiply by $2$. – André Nicolas Jun 14 '11 at 15:58
@user6312: Oh, now I feel dumb. Thanks! But I can't mark a comment as an answer. – jnm2 Jun 14 '11 at 16:00
That's OK, I knew that quickly enough would come an answer that you could accept. – André Nicolas Jun 14 '11 at 16:08
up vote 1 down vote accepted

Just expand:

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

share|cite|improve this answer
+1. Note that $r$ is odd so $(r-1)/2$ is an integer. – Henry Jun 14 '11 at 16:00

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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