4
$\begingroup$

This is a very elementary doubt.

Is it true that, $\phi(n)$ the smallest number for which $a^{\phi(n)} \equiv 1 \pmod n$, where $\gcd(a,n)=1$.

  • 3
    No, see [Carmichael function](http://en.wikipedia.org/wiki/Carmichael_function)2012-03-04

1 Answers 1

10

No; it's not the smallest for specific values of $a$; it's not even the smallest that works for all $a$.

For example, $\phi(8) = 4$, but for every odd integer $n$, $n^2\equiv 1 \pmod{8}$.

The number you are looking for is called the "reduced totient function", "least universal exponent function", or Carmichael function $\lambda(n)$. This is the smallest positive integer such that for all $a$ with $\gcd(a,n)=1$, we have $a^{\lambda(n)}\equiv 1\pmod{n}$. It always divides $\phi(n)$.

  • 0
    Maybe it's also worth mentioning that $\lambda(p) = \phi(p)$ for prime p..2012-03-04