# On the Euler totient function and Euler's theorem

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

-
No. Consider $a=1$. – Alex Becker Mar 4 '12 at 4:27
No, see Carmichael function – sdcvvc Mar 4 '12 at 4:35

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)$.
Maybe it's also worth mentioning that $\lambda(p) = \phi(p)$ for prime p.. – aelguindy Mar 4 '12 at 11:28