3
$\begingroup$

Let $\lambda$ be the Carmichael Lambda function, as defined on wikipedia. Let $a,b\in\mathbb{Z}.$ Prove the following

  1. If $a \mid b$ then $\lambda(a) \mid\lambda(b).$
  2. $\lambda(\operatorname{lcm}(a,b)) = \operatorname{lcm}(\lambda(a), \lambda(b))$.

I think the first statement can be shown using the unique factorization theorem and a case-by-case proof for the values of $\lambda$ on prime powers.

Wikipedia says that the second statement follows immediately from the recursive definition, but I don't think this is so; there's more to it than that. However, I'm not really sure how to prove the second statement by using the first definition more closely; if $a$ and $b$ are coprime then maybe using the unique factorization theorem will help but I'm not sure how to extend this result to when $a$ and $b$ are not coprime. I'd probably start by using this result for $\frac{a}{\gcd(a,b)}$ and $\frac{b}{\gcd(a,b)}.$

$\endgroup$

1 Answer 1

3
$\begingroup$

Hint $ $ Like analogous proofs for Euler $\phi$ (totient) function, by multiplicativity we can reduce to the case of prime powers, where the proofs are straightforward. Alternatively, and more conceptually, we can use the universal properties of lcm and $\lambda$ (= universal order or expt). Let's prove $(2)$ in this manner. First, by $(1)$ and the lcm universal property we have, with $[x,y] := {\rm lcm}(x,y)$

$$a,b\mid [a,b]\,\Rightarrow\, \lambda(a),\lambda(b)\mid \lambda([a,b])\,\Rightarrow\, [\lambda(a),\lambda(b)]\mid \lambda([a,b])\qquad$$

For the reverse divisibility, if $(x,[a,b])=1$ then $(x,a)=1=(x,b),\,$ so $\,x^{\lambda(a)}\equiv 1\pmod{\!a},\,$ $\,x^{\lambda(b)}\equiv 1\pmod{\!b},\,$ so $\,x^{[\lambda(a),\lambda(b)]}\equiv 1\pmod{[a,b]},\,$ thus $\,\lambda([a,b])\mid [\lambda(a),\lambda(b)],\,$ by the universal analog of the Order Theorem, which shows that the minimal universal expt $\,\lambda\,$ divides every universal expt.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .