# Proof that $gcd(e, \lambda(N)) = 1 \hspace{1mm} \Longleftrightarrow \hspace{1mm} gcd(e, \varphi(N)) = 1$

What is the proof for the fact that $gcd(e, \lambda(N)) = 1 \hspace{1mm} \Longleftrightarrow \hspace{1mm} gcd(e, \varphi(N)) = 1$

Where:

$N = P * Q$ where $P$ and $Q$ are both primes.

$\varphi(N)$ is Euler phi function

$\lambda(N)$ is Carmichael function

An outline of the proof is:

$gcd(a,b)=1$ is equivalent to the claim that $\not\exists p_\text{ prime}: p|a \land p|b$ (that is, there does not exist a prime $p$ that is a factor of both $a$ and $b$)

Now, for all primes $p$, $p | \phi(N)$ iff $p | \lambda(N)$ (that is, for all primes $p$, either they are a factor of both $\phi(N)$ and $\lambda(N)$, or they are a factor of neither). This can be seen by examing the relation $\phi(N) = (p-1)(q-1)$ and $\lambda(N) = (p-1)(q-1)/gcd(p-1,q-1)$, and observing that if $gcd(p-1,q-1)$ had a prime power factor $r^n$, then both $p-1$ and $q-1$ were multiples of $r^n$, and hence $(p-1)(q-1)$ had $r^{2n}$ as a factor, and so $(p-1)(q-1)/gcd(p-1,q-1)$ has $r^n$ (and hence $r$) as a factor.

So, if $gcd(e, \lambda(N))=1$, then:

• For any prime factor $p$ of $e$, $p$ is not a factor of $\lambda(N)$
• Hence, For any prime factor $p$ of $e$, $p$ is not a factor of $\phi(N)$
• Hence, $gcd(e, \phi(N))=1$

And versa-visa, showing the equivalence.