= Solution
For distinct <prime numbers> $p,q$, compute the <Euler totient function>
$$
\varphi(n)=(p-1)(q-1).
$$
The <RSA cryptosystem> private exponent is a <modular multiplicative inverse> of the public exponent:
$$
\boxed{d\equiv 3^{-1}\pmod{\varphi(n)},\qquad 3d\equiv1\pmod{\varphi(n)}.}
$$
Use the <extended Euclidean algorithm> on $3$ and $\varphi(n)$. It produces <integers> $u,v$ with $3u+\varphi(n)v=1$, and reducing $u$ modulo $\varphi(n)$ gives a suitable positive $d$. Searching through possible exponents is unnecessary.
To see correctness even for a <plaintext> sharing a factor with $n$, write $3d=1+t\varphi(n)$. Modulo $p$, either $m=0$ or <Fermat's little theorem> gives $m^{3d}=m$; the same holds modulo $q$. The <Chinese remainder theorem> then gives $c^d=m\pmod n$. One may alternatively invert $3$ modulo $\operatorname{lcm}(p-1,q-1)$, but inversion modulo $\varphi(n)$ is sufficient for this paper.
Back to article page
