RSA cryptosystem decryption exponent

Question

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?

Answer 1

We note that if

$$de\equiv 1\pmod{\varphi(n)}$$

then

$$\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)}$$