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.

Given a safe-prime $p = 2q + 1$ where $q$ is also a prime and $p \gt 7$, I've read in a crypto.se answer that either $p \equiv 11 \pmod {24}$ or $p \equiv 23 \pmod {24}$.

I understand the proofs of why $p^2 \equiv 1 \pmod {24}$, and $p \equiv 1 \pmod 6$ or $p \equiv 5 \pmod 6$ for any prime $p$, and I can see that $p \equiv 11 \pmod {24}$ and $p \equiv 23 \pmod {24}$ are consistent with that, but can anyone explain why the other possible congruences for a prime $p$ (such as $p \equiv 1 \pmod {24}$) are excluded by $p$ being a safe prime?

My reasoning so far is:


For a prime $p \equiv 1 \pmod 6$ and $p \equiv (1,7,13,19) \pmod {24}$, or $p \equiv 5 \pmod 6$ and $p \equiv (5,11,17,23) \pmod {24}$.

For a safe prime $p = 2q + 1$ it cannot be true that $p \equiv 1 \pmod 6$, otherwise $2q$ would be divisible by 6 and $q$ would not be prime. This eliminates 1, 7, 13 and 19.

Likewise $p = 2q+1 \equiv 5 \pmod {24}$ and $p = 2q+1 \equiv 17 \pmod {24}$ cannot hold, otherwise $q$ would have to be even: $q \equiv 2 \pmod {24}$ or $q\equiv 8\pmod {24}$ respectively.

This leaves $p \equiv 11 \pmod {24}$ or $p \equiv 23 \pmod {24}$ as possible congruences.


Is this correct and sufficient, and/or is there a better way of demonstrating that either $p \equiv 11 \pmod {24}$ or $p \equiv 23 \pmod {24}$ can and must hold?

share|improve this question
1  
What about $p=7$? –  Barry Cipra Mar 19 at 10:12
    
I missed that in my description - to be fair the original answer did have that caveat. –  archie Mar 19 at 10:15

4 Answers 4

up vote 3 down vote accepted

A prime must be $\{1,5\} \text{ mod } 6$, so $\{1,5,7,11\} \text{ mod } 12$, so $\{1,5,7,11,13,17,19,23\} \text{ mod } 24$. This is true for $q$. Double each of these and add 1:

$1 \rightarrow 3 \not \in \{1,5,7,11,13,17,19,23\}$

$5 \rightarrow 11 \in \{1,5,7,11,13,17,19,23\}$

$7 \rightarrow 15 \not \in \{1,5,7,11,13,17,19,23\}$

$11 \rightarrow 23 \in \{1,5,7,11,13,17,19,23\}$

$13 \rightarrow 3 \not \in \{1,5,7,11,13,17,19,23\}$

$17 \rightarrow 11 \in \{1,5,7,11,13,17,19,23\}$

$19 \rightarrow 15 \not \in \{1,5,7,11,13,17,19,23\}$

$23 \rightarrow 23 \in \{1,5,7,11,13,17,19,23\}$

So the only options for $p$ are $11$ and $23 \text{ mod } 24$.

share|improve this answer

Since $24=3\cdot 8$, work modulo $3$ and modulo $8$ and then put the answer back together using the Chinese remainder theorem.

  • A safe prime $p>7$ is always $p\equiv 2 \bmod 3$. This can be shown by considering the options for $q\bmod 3$. Since $p>7$, we have $q>3$, and so $q\not\equiv 0\bmod 3$. And if $q\equiv 1 \bmod 3$, then $p=2q+1$ is divisible by $3$, so it is not a prime. Hence $p\equiv q\equiv 2 \bmod 3$.

  • Now consider the options for $q\bmod 8$. Since $q$ is prime, $q\equiv 1,3,5,7\bmod 8$ and, respectively, $p$ would be $p\equiv 2q+1\equiv 3,7,3,7\bmod 8$, so there are only two possibilities $p\equiv 3$ or $7\bmod 8$.

Now we can use the Chinese remainder theorem. Solving: $$\begin{cases} x\equiv 2\bmod 3,\\ x\equiv 3 \text{ or } 7 \bmod 8, \end{cases}$$ leads to only two solutions modulo $24$, namely $11$ or $23\bmod 24$.

share|improve this answer

I suggest you change to "otherwise $q$ would have to be even: $q \equiv 2$ or $14 \pmod{24}$, or $q \equiv 8$ or $20\pmod{24}$ respectively."

I would approach it from the other direction, checking candidates for $q$, because multiplication is safer than division in modular atithmetic. There are $12$ odd congruency classes $\pmod{24}$. The four classes $3, 9, 15, 21$ can be discarded as candidates for $q$ because of divisibility by $3$ (apart from the number $3$ itself). Any odd number $\equiv 1 \pmod{6}$ may also be safely discarded, because if $q\equiv 1 \pmod{6}$, then $p = 2q + 1 \equiv 3\pmod 6$. So we discard the four classes $1, 7, 13, 19$ as candidates for $q$. Thus we're left with four candidates for $q$: $5, 11, 17, 23$. In each case $2q + 1 \equiv 11$ or $23\pmod{24}$.

That being said, I would also find it faster, easier and better to work out modulo $12$. $p \equiv 11$ or $23 \pmod{24}$ is exactly the same as saying $p\equiv 11 \pmod{12}$. In this case we only have six odd congruency classes, and four of them are removed by observing that $q \equiv 5 \pmod6$. The remaining two possibilities ($q \equiv 5$ and $q\equiv 11$) both produce $p \equiv 11$.

share|improve this answer

$(q,24) = 1\Rightarrow q \in \pm\!\!\overbrace{\{1,5,7,11\}}^{\rm\large coprime\ to\ 2,\,3}\!\!\!,\,$ $\,p=1\!+\!2q\,$ is coprime to $\,24\,$ iff $\,3\nmid p\,$ iff $\,q\equiv -1\pmod 3,\,$ therefore $\,\ q \,\in\, \{-1,5,-7,11\}\,\Rightarrow\,1\!+\!2q = \{-1,11,-13,23\}\equiv \{11,23\}\pmod{24}$

share|improve this answer

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.