0
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.