How would I go about calculating $\lambda(49392)$ by hand?
I have $\lambda$ defined in a book as $$ \lambda(n) = max{\{\bar{a} | \bar{a} \in Z_n^*\}} \ \cdot \ ord_{Z_n^{*}} (\bar{a}) $$
where $Z_n^*$ is the set of residue classes of $a$ such that $a$ and $n$ are co-prime.
If I follow this correctly, then the max residue class would be $\overline{49391}$, since $49391, 49392$ are coprime. Then I would have to multiply this by the order of $49391$ in the group $Z_m^*$, meaning I should find a minimal power $k$ such that $49391^k \equiv 1 \ \bmod \ 49392$.
I have found this $k$ to be $2$.
However, this is not in line with what I have found online about the definition of $\lambda$.
Elsewhere I have found that it is defined as "the lowest power $k$ such that every (coprime of $n$) to the power $k \equiv 1 \ \bmod \ n$".
In that case, I have found $k = 588$ by several online calculators, and it seems to be the case.
Do you have any idea as to what I am missing? Any idea/hint appreciated.
$\endgroup$ 12 Answers
$\begingroup$Details of Carmichael's Lambda Function:
Definition
Let $n$ be a positive integer. Then $\lambda(n)$ is defined to be the smallest positive integer $k$ such that $a^k \equiv 1 \pmod n$ for all $a$ such that $\text{gcd}(a,n)=1$.
Note that $\lambda(n)$ always exists because $k= \phi(n)$ satisfies the equation above, by Euler's theorem. So $\lambda(n) \le \phi(n)$.In fact, $\lambda(n)|\phi(n)$, by a standard division algorithm argument: let $\phi(n) = \lambda(n) q+r,0 \le r < \lambda(n)$; then it's clear that $a^r \equiv 1 \pmod n$ for all $a$ coprime to $n$. This contradicts minimality of $\lambda(n)$ unless $r=0$.
Computing Carmichael's Function
Values of Carmichael's lambda function can be calculated using the following formulas:
We have
$$\begin{aligned} \lambda\left(p^{\alpha}\right) &= \begin{cases} \phi\left(p^{\alpha}\right) &\text{ if } \alpha \leq 2 \text{ or } p \geq 3 \\ \frac{1}{2} \phi\left(p^{\alpha}\right) &\text{ if } \alpha \geq 3 \text{ and } p = 2 \end{cases} \\\\ \lambda\left( {p_1}^{\alpha_1} \cdots {p_k}^{\alpha_k} \right) &= \text{lcm} \, \big(\lambda\left({p_1}^{\alpha_1}\right), \cdots, \lambda\left({p_k}^{\alpha_k}\right)\big), \end{aligned}$$
where the $p_i$ are distinct positive prime numbers.
Example
Find the smallest positive integer $a$ such that $360|(x^a-1)$ for any $x$ relatively prime to $360$.
We have $\lambda(360) = \text{lcm}\big(\lambda(2^3),\lambda(3^2),\lambda(5)\big) = \text{lcm}(2,6,4) = 12$
Note in this example that $360\Big|x^3(x^{12}-1)$ for all $x$, since $2^3,3^2,5$ all either divide $x^3$ or $x^{12}-1$ depending on whether $x$ is divisible by $2,3,5$ respectively.
$\endgroup$ $\begingroup$The Carmichael function is the maximum order of elements of $\mathbb Z_n^*$.
Since $49392=2^43^27^3$, the Carmichael function is the least common multiple of $\frac12\phi(2^4)=4$, $\phi(3^2)=6$, and $\phi(7^3)=49\times6$, which is $588$.
$\endgroup$
