Are there more numbers in this integer sequence? 3, 8, 12, 24 I was using some low primes for RSA encryption today, and noticed that for $p=5$, $q=7$, and ANY valid encryption key value, encrypt(encrypt(message)) = message. I thought this was an interesting property, so I found this sequence: $3, 8, 12, 24$. It can be described using these rules:
$N$ is a member of the sequence if and only if:
For each prime number $p$, such that $\sqrt{N} \le p < N$: $p^2 \equiv 1 \bmod N$
Unfortunately, I have only been able to find 4 members of the sequence: $3, 8, 12$ and $24$. Are there any other members? I have tried all numbers up to 75 million. If there's a proof why this is impossible, I'd love to see it!

I assume that you are looking for numbers $N \in \Bbb N$ satisfying $x^2 \equiv 1 \bmod N$ for all $1\le x \le N$ such that $(x,N)=1$. This is a necessary condition for $N=\varphi(M)$ to have the described property for RSA-encryption with modulus $M$. Algebraically speaking this means that any element of the multiplicative group $(\Bbb Z/N \Bbb Z)^\times$ has order $2$.


*

*If $N=2^k$ is a power of $2$, the group is $(\Bbb Z/N \Bbb Z)^\times = (\Bbb Z/2 \Bbb Z)\times(\Bbb Z/2^{k-2} \Bbb Z)$.

*If $N = p^k$ is a power of a prime $p>2$, the group is $(\Bbb Z/N \Bbb Z)^\times = (\Bbb Z/(p-1) \Bbb Z)\times (\Bbb Z/p^{k-1} \Bbb Z)$

*If $N = \prod p_i^{k_i}$ is composite, the group is the product of the groups corresponding to the prime powers, that is $(\Bbb Z/N \Bbb Z)^\times = \prod (\Bbb Z/p_i^{k_i} \Bbb Z)^\times$ 


As $N$ satisfies the described property iff $(\Bbb Z/N \Bbb Z)^\times$ can be written as a product of copies of $(\Bbb Z / 2\Bbb Z)$:


*

*the highest power of $2$ dividing $N$ is $3$

*the highest power of $3$ dividing $N$ is $1$

*no other prime divides $N$


So $24$ is the maximal number of the sequence.
