# Why does $q \equiv (r-1)/2 \mod r$ mean that $2q \equiv -1 \mod r$?

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

• 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

Just expand:

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