1
$\begingroup$

Is it true that $\varphi(n)$ is generally larger than $\lambda(n)$ for the same $n$? If so, can anyone give me a proof?

$\endgroup$
2
$\begingroup$

As $n$ is the product of primes $p$ and $q$, $\varphi(n) = (p - 1)(q - 1)$ and $\lambda(n) = \operatorname{lcm}(p - 1, q - 1)$. The former multiplies $p - 1$ and $q - 1$, whereas the latter finds the least common multiple of the two. Naturally, $\forall a,b:\operatorname{lcm}(a,b) \le a\cdot b$, so we can say that $\forall n:\lambda(n) \le \varphi(n)$. In the case that the LCM for $a,b$ is $a$ and $b$ themselves, then they will be equal. Otherwise, the LCM will always be smaller. As $p$ and $q$ are always primes and therefore odd, we have $2\mid\gcd(p - 1, q - 1)$, thus $\lambda(n) < \varphi(n)$.

So yes, it is true.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Also note that in the typical case (e.g. RSA) that $p,q$ are both odd, we always have $2\mid\gcd(p-1,q-1)$, hence $\lambda(pq) \mathrel{\color{red}<}\varphi(pq)$. $\endgroup$ – yyyyyyy May 19 '19 at 8:08
  • $\begingroup$ @yyyyyyy Thanks! Does this edit look correct? $\endgroup$ – forest May 19 '19 at 8:14

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.