0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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) $\endgroup$ – Bill Dubuque Mar 27 at 17:20
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

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.