# RSA cryptosystem decryption exponent

Show that in RSA cryptosystem the decryption exponent $d$ must satisfy the congruence

$$de\equiv 1\pmod{{\rm lcm}{(p-1,q-1)}}$$

So in the RSA cryptosystem we pick two primes $p$ and $q$. Then $n=pq$. Then pick an encryption exponent $e\in\{1,..., \varphi(n)\}=\{1,...,(p-1)(q-1)\}$. Then given a message $0\le m< n$ we may encrypt by

$$c = m^e\pmod{n}$$

and decrypt by

$$m = c^d\pmod{n}$$

where $ed\equiv 1\pmod{\varphi(n)}$.

So this proof amounts to showing $\varphi(n)=(p-1)(q-1)={\rm lcm}(p-1,q-1)$. Here is where my confusion arises.. Clearly this is not generally true. So what is wrong here?

• $\varphi(n)$ is a multiple of $\text{lcm}(p-1,q-1)$. Unless $p-1$ and $q-1$ are relatively prime, which can only happen if either $p$ or $q$ is $2$, the multiple is by a non-trivial factor. – Einar Rødland Apr 5 '16 at 20:51

$$de\equiv 1\pmod{\varphi(n)}$$
$$\varphi(n) = (p-1)(q-1) = \beta{\rm lcm}(p-1,q-1)$$
for some constant $\beta$. Hence
$$de = 1 + \alpha\varphi(n) = 1+\alpha\beta{\rm lcm}(p-1,q-1)\equiv 1\pmod{{\rm lcm}(p-1,q-1)}$$