RSA: If n=35, show that e will equal d

Question

Show that if $n = 35$ is used as an RSA modulus then the encryption exponent $e$ always equals the decryption exponent $d$?

What I have so far:

$n = 35$

Therefore $p = 5$ and $q = 7$ or vice versa, which means Euler's phi function is

$\varphi = (5-1) \cdot (7-1) = 24$

Then to find $e$ we need the fact that $\gcd(e,\varphi) = 1$

$\gcd(e, 24) = 1$

Therefore the possible values of $e$ are only prime. $e = 5, 7, 11, 13, 17, 19, 23$

Then $d$ must follow the equation $d \equiv e^{-1} \mod \varphi$ or $(d\cdot e) \equiv 1 \mod 24$

Then I've tried for all those values which solve that equation. Why is that true? How can I explain this?

Answer 1

The number 24 has the curious property that, for any prime $p > 3$, $p^2 - 1$ is divisible by 24. (In fact, this holds for any odd number $p$ not divisible by 3.)

This follows simply from the fact that $p^2 - 1 = (p-1)(p+1)$; since $p$ is not divisible by either 2 or 3,

• the factors $p-1$ and $p+1$ must both be even,
• one of them must be divisible by 4, and
• one of them must be divisible by 3.

Thus, their product must be divisible by $2\cdot4\cdot3 = 24$.