Modified RSA Proving $x^{(p-1)(q-1)/\gcd(p-1,q-1)} \equiv 1 \mod pq$

275 Views Asked by At

In RSA, we use $ab \equiv 1 \mod \varphi(n)$ for $n=pq$ product of distinct odd primes. In an exercise of Stinson's book, Cryptography : Theory and Practise, it is said that if we change $\varphi(n)$ to $\lambda(n)=\frac{(p-1)(q-1)}{\gcd(p-1,q-1)}$, we are still able to do the same encryption and decryption. How can we prove this? I am still unable see why this is true. And also, can we generalise to other $n$ which is not product of two distinct odd primes? Thank you.