I am studying R.S.A. cryptosystem and here is the question that came to my mind. Let’s pick $p, q$ to be two primes and $n = p * q$. From that we calculate Euler’s totient function:
$$ \phi(n) = (p - 1)(q - 1). $$ Then we chose the public and private key pair as $e, d$ such that: $$ e * d \equiv 1 \bmod \phi(n). $$
Now I want to prove that for the same pair $(e, d)$ it no longer holds that:
$$ e * d \equiv 1 \bmod n. $$
I have tried writing: $$ e * d = k * \phi(n) + 1\\ e * d = l * n + 1, $$ for some integer $k$ and $l$. So it should be that: $$ k * \phi(n) + 1 = l * n + 1 \\ k * \phi(n) = l * n. \\ $$ So replacing the values of $n = pq$ and $\phi(n) = (p - 1)(q - 1)$ we get: $$ k * (p - 1) * (q - 1) = l * p * q. $$ I sense that there is an impossibility. But can’t figure out what it is. Thanks in advance.
The statement you have given appears to be false. A counterexample which first strung to my mind is $e = 31$ and $d = 27791$. Taking $p = 89, q = 11$, we get $e*d$ congruent to both $1$ mod $(p*q)$ and $1$ mod $((p-1)*(q-1))$