Clarification about Carmichael's Lambda Function

Question

By definition Carmichael function $\lambda(n)$ is the the smallest positive integer $m$ such that $$ x^m\equiv 1\pmod{n} $$ for all $1\leq x\leq n$ such that $\gcd(x,n)=1$. Moreover it is simple to compute $\lambda(n)$ thanks to Carmichael's theorem.

Consider now this problem: find the smallest positive integer $m$ such that $$ 13^m\equiv 1\pmod{2013} $$ Because $\gcd(13,2013)=1$ we have that $m=\lambda(2013)=60$. But we also have $13^{30}\equiv 1\pmod{2013}$ and of course $30<60$. This seems to contradict the Carmichael's theorem. How it could be possible?

Thanks

Answer 1

As you wrote, $\lambda(n)$ is the the smallest positive integer $m$ such that $x^m\equiv1\pmod n$ for all $1\le x \le n$ such that $\operatorname{gcd}(x,n)=1$. The important words you seem to be overlooking are "for all".

Indeed, $13^{30}\equiv1\pmod {2013}$, but that's only one value of $x$. For $x=2$, for example, $2^{30}\equiv 1585\pmod {2013}$, so $\lambda(2013)$ can't be $30$. However, $2^{60}\equiv 1\pmod {2013}$, and the same is true for every other $x$ coprime to $2013$.

Answer 2

$\lambda(n)$ is the the smallest positive integer $m$ such that $$ x^m\equiv 1\pmod{n} $$ for all $1\leq x\leq n$ such that $\gcd(x,n)=1$.

Because $\lambda(2013)=60,$ we have $x^{60}\equiv 1\pmod{2013}$ for all $x$ relatively prime to $n$.

$x^{30}\equiv 1\pmod{2013}$ may hold for some but not all such $x$.

For example, $17^{30}\not\equiv 1 \pmod{2013}.$