lcm of orders of reduced residue classes of $1001$ By Euler's theorem, I know that all orders of reduced residue classes of $1001$ must divide $\phi(1001) = 720$. However, by a computer program, I know that the lcm of the orders of all $720$ reduced residue classes is $60$ (and, therefore, $1001$ has no primitive roots).
I was wondering if there was a way to see why $60$ is in fact the smallest number which all reduced residue orders must divide. Is there a way, without computing everything explicitly, I could have determined this?

We have $1001=7\cdot 11\cdot 13$. Since $7$, $11$, and $13$ are primes, there are objects of order respectively $6$, $10$, and $12$ modulo $7$, $11$, and $13$. Thus by the Chinese Remainder Theorem there is an element of order (modulo $1001$) equal to the lcm of $6$, $10$, and $12$, which is $60$.
It is easy to show that there is no element of order greater than $60$. If $a$ is relatively prime to $1001$, then by Fermat's Theorem we have $a^6\equiv 1\pmod{7}$, and therefore $a^{60}\equiv 1\pmod{7}$. Similarly, $a^{60}\equiv 1$ modulo $11$ and $13$, so $a^{60}\equiv 1\pmod{1001}$.
For the general result along these lines, please search under the Carmichael $\lambda$-function, or least universal exponent.
