# Prove that if $e.d \equiv 1 \text{ mod } pq$ then it's impossible to have $e.d \equiv 1 \text{ mod } (p-1)(q-1)$

I am studying RSA 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 \text{ mod } \phi(n).$$

Now I want to prove that for the same pair $$(e, d)$$ it no longer holds that:

$$e * d \equiv 1 \text{ mod } 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.

• What is the proposition to prove exactly? The proposition in title is incorrect. A counterexample is $e=d=1$. Another with $e$ valid in some mathematical definition of RSA is $p=13$, $q=17$, $e=5$, $d=16973$. These parameters work, in the sense that we can successfully decrypt with $(n,d)$ what was encrypted with $(n,e)$.
– fgrieu
Commented Dec 3, 2023 at 17:52
• I don't understand what you exactly mean. I think your question can be converted to another representation: There is no isomorphic function $\zeta:Z^*_{\phi(N)}\to Z^*_N$ , s.t. given two group elements $e,d=e^{-1} \in Z^*_{\phi (N)}$, $\zeta(e)\cdot\zeta(d)=1modN$. Commented Dec 4, 2023 at 0:37

Now I want to prove that for the same pair $$(e,d)$$ it no longer holds that:

That you are running into difficulties proving it may be due to the fact that it is, as you have laid out, not true.

Consider the values:

$$e = 1 + apq(p-1)(q-1)$$ $$d = 1 + bpq(p-1)(q-1)$$

for arbitrary integers $$a, b$$.

With these values, it is straight-forward to verify that these both hold:

$$ed = 1 \pmod{(p-1)(q-1)}$$ $$ed = 1 \pmod{pq}$$

Of course, if $$a, b > 0$$, these are huge values of $$d, e$$, but there's nothing that says they can't be huge.

On the other hand, if we add in the assumptions that:

• $$p-1$$ does not have $$q$$ as a factor
• $$q-1$$ does not have $$p$$ as a factor
• $$p, q$$ are both primes (standard with RSA; let us be explicit about that)
• $$e, d > 1$$
• $$e, d < \phi(n)$$

Then both relations cannot hold simultaneously. I believe that you would find it instructive to show that from what you have; the steps you have written out is already half the work...

To show that the first two assumptions are necessary, I found this counterexample if we don't include those assumptions:

$$N = 5671 = 53 \times 107$$ $$E = 615$$ $$D = 959$$

Computation shows that both $$E\cdot D = 1 \pmod{N}$$ and $$E \cdot D = 1 \pmod{\phi(N)}$$