# Using Carmichael function in RSA.

Given e and d as the encryption and decryption component respectively, textbook RSA has the property $ed\equiv 1\pmod {\phi(n)}$. The requirement is that suppose there is another function $\lambda(n)$ such that $$\lambda(n) = {\phi(n)\over gcd (p-1, q-1)}$$ and $$ed\equiv 1\pmod{\lambda(n)}$$I need to prove that e and d still work as encryption and decryption components. I know that $\lambda(n ) = lcm(p-1,q-1)$ but I am totally lost about how this general proof proceeds. PKCS#1 uses this function instead of $\phi(n)$ but I am not able prove that this works.

So this all comes down to showing that $a^{\lambda(n)} \equiv 1 \pmod n$.

So for ease, call $\lambda = \text{lcm}(p-1,q-1) = \text{lcm}(\varphi(p),\varphi(q))$.

Consider $a^\lambda \pmod {pq}$. On the one hand, $\lambda = \varphi(p)m$ for some multiple $m$ of $\varphi(p)$, so that $a^\lambda = a^{\varphi(p)m} \equiv 1^m \equiv 1 \pmod p$. On the other hand, $\lambda \equiv \varphi(q)n$ for some multiple $n$ of $\varphi(q)$, so that $a^\lambda = a^{\varphi(q)n} \equiv 1^n \equiv 1 \pmod q$.

So by the Chinese Remainder Theorem, we must have that $a^{\lambda(pq)} \equiv 1 \pmod{pq}$.

So if you have $ed \equiv 1 \mod {\lambda(pq)}$, then in particular we have some positive coefficient $k$ such that $ed = k\lambda(pq) + 1$. Then $a^{ed} = a^{\lambda(pq)}a \equiv 1 \cdot a \equiv a \mod pq$.

So if you transmit $a^e$, then you can recover $a$ by raising to the $d$, where $d$ is the multiplicative inverse of $e \mod \lambda(pq)$.

Because $\lambda(n) = \mathrm{lcm}(p-1,q-1)$, $ed \equiv 1 \pmod{\lambda(n)}$ implies that $ed\equiv 1 \pmod{p-1}$. Then $$a^{ed} = a^{1+k(p-1)} = a\cdot \left(a^{p-1}\right)^k$$ If $a\equiv 0\pmod p$, then $a^{ed} \equiv 0^{ed} \equiv 0 \pmod p$. Otherwise, $a^{p-1} \equiv 1 \pmod p$ by Fermat's theorem, so in the end we obtain $a^{ed} \equiv a\pmod p$ in all cases. The same reasoning applies modulo $q$, so we obtain $$\left\{\begin{array}{l} a^{ed} \equiv a \pmod p \\ a^{ed} \equiv a \pmod q \end{array}\right.,$$ which implies $a^{ed}\equiv a \pmod{pq}$ by the Chinese theorem since $p$ and $q$ are coprime.