RSA: why $( e^{-1} ~\text{mod}~ n \cdot \varphi(n)) ~\text{mod}~ \varphi(n) = e^{-1} ~\text{mod}~ \varphi(n)$ holds for a specific setting of RSA

Question

Let $p,q$ are primes and $n = pq$ as in every RSA setting and now use a random $e$ that holds the following properties

• $gcd(e, \phi(n)) \neq 1$
• $(e^{-1} ~\text{mod} ~\phi(n))^{4}\cdot3 < n$
• $e^{-1} ~\text{mod} ~\phi(n) < \sqrt[3]{n}$ (integer square root), where $\sqrt[3]{n} \in \mathbb{Z}$

where $\phi$ is euler's totient function. This $e$ is used as the public exponent for the public key and $d$ is the private exponent for the private key.

Remember that $\phi(n) | ed - 1$, as $ed = 1 + k \cdot \phi(n)$ holds for $k \in \mathbb{Z}$. The question is, why it holds that $$(e^{-1} ~\text{mod}~ n \cdot \phi(n)) ~\text{mod}~ \ \phi(n) = e^{-1} ~\text{mod}~ \phi(n)\text{?}$$ Could someone explain it mathematically or give a proof why that holds?

A related question regarding multiple of $\phi(n)$ is asked in this question. Unfortunately, I don't understand the relation between the multiple of $\phi(n)$, the $gcd$ and why this equation $ed = 1 ~\text{mod}~ k \cdot \phi(n)$ holds $ed = 1 ~\text{mod}~ \phi(n)$ for $k \in \mathbb{Z}$.

Additionally it would be nice to read a proof for the related question regarding the multiple of $\phi(n)$, if someone knows why that holds.

Answer 1

The question is, why it holds that $(e^{−1} \bmod n \cdot \phi(n)) \bmod \phi(n)=e%{−1} \bmod \phi(n)$?

Actually, we have the more general identity $(A \bmod BC) \bmod C \equiv A \bmod C$, for any integers $A, B, C$. In your specific case, we have $A = e^{-1} \bmod \phi(n)$, $B = n$, and $C = \phi(n)$

This more general identity can be easily be seen from two facts:

$X \bmod Y = X + k \cdot Y$ for some integer $k$ (which may be negative)

$X \bmod Y = Z \bmod Y$ if and only if $X - Z = k'\cdot Y$ for some integer $k'$.

From the first fact, we can see that $A \bmod BC = A + kBC$ (for some integer $k$ - we don't care what that integer is)

From the second fact, we see that $(A + kBC) \bmod C = A \bmod C$ holds if we have $A + kBC - A = k'C$ for some integer $k'$; we can immediately see that this holds for the integer $k' = kB$, hence this is true.

Since the general identity holds in all cases, it also holds in your specific case.