Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
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

1 Answer 1

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

 
discard

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.