Safe prime mod 24

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?

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

4 Answers

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

-

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

-

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

-

$(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}$

-