RSA: select $e$ given $n$ and $\varphi(n)$ I have a question for a course I am doing. In an RSA question, it asks "Is it possible to select $e$ in such a way that it coincides with the corresponding private key $d$? If it is possible, provide a value for such an $e$.

So, this is only part of the question (last part really).

$$n = 22499$$
$$\varphi(n) = 22200$$

How would I go about this? I am completley lost. I have, by luck come across an answer of $149$. $149^2 = 1 \pmod{22200}$. This is because $ed = 1 \pmod{\varphi(n)}$. Is there a method to calculate such a number? [$a^x = 1 \pmod{\varphi(n)}$]
There are four different solutions, of which three have been identified as the "trivial solutions" in the comments to this question.


$e=d=1$ which is obviously fullfilling the condition that $1\cdot 1\equiv 1 \pmod{\varphi(n)}$ should hold.
$e=d=\varphi(n)-1$ which is fullfilling the condition that $(\varphi(n)-1)^2\equiv 1 \pmod{\varphi(n)}$ as $(\varphi(n)-1)^2=((\varphi(n))^2-2\varphi(n)+1) \bmod{\varphi(n)}=1$
$e=d=\sqrt{\varphi(n)+1}$ (if integer) which is also obviosuly true as $\sqrt{\varphi(n)+1}^2=(\varphi(n)+1)\bmod{\varphi(n)}=1$, this is the solution you stumbled across.
Use a full modular square root finding algorithm as documented as algorithm 3.44 in the Handbook of Applied Cryptography on page 102. (PDF version) However this requires you to know the prime factorization of $\varphi(n)$ which may be infeasible to obtain for sufficiently large $n$.