Clarification about Carmichael's Lambda Function

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

• The theorem doesn't say the the exponent is minimal for each value of $x$ - only for all $x$ (hence the alternative name universal exponent) – Bill Dubuque Mar 27 at 17:20

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$$.
$$\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}.$$