# For which numbers, every possible order can be achieved?

Let $n\ge 2$ be a natural number.

Then, every possible order of an number modulo $n$ is a divisor of $\lambda(n)$. $\lambda(n)$ is the Carmichael-function, it is the largest possible order modulo $n$.

Which numbers $n$ have the following property : For every $d|\lambda(n)$, except $d=1$, there is a number $a$ with $1<a<n$, such that the order of $a$ modulo $n$ is $d$ ?

Additionally : If we are looking for a number a with order $2$, for which $n$ can we avoid $a=n-1$, which is trivial ?

I experimented with PARI/GP and it seems that the desired property is fulfilled, if there is a number $a$ with order $\phi(n)$ modulo $n$.

• See here for some stuff about finding square roots of $1$ modulo $n$. Also here, here or here. This is one of the more frequently recurring themes. – Jyrki Lahtonen Nov 20 '15 at 10:37
• But did I understand the main question correctly? If $a$ is of order $\lambda(n)$, and $d\mid\lambda(n)$, then $a^{\lambda(n)/d}$ is automatically of order $d$, right? – Jyrki Lahtonen Nov 20 '15 at 10:39
• How can we be sure, that the order of $a^{\lambda(n)/d}$ is not smaller than $d$ ? – Peter Nov 20 '15 at 10:46
• Yes. ${}{}{}{}$ – Jyrki Lahtonen Nov 20 '15 at 10:51
• Peter, the congruence $x^2\equiv1\pmod n$ has $2^{t+e}$ pairwise incongruent solutions, where $t$ is the number of odd prime factors of $n$. The extra $e$ depends from the power of $2$ dividing $n$. If $n$ is not divisible by four, then $e=0$. If $n$ is divisible by four but not by eight, then $e=1$. If $8\mid n$, then $e=2$. That's more or less covered in the questions I linked. Chinese remainder theorem reduces the problem to the case where $n$ is a prime power, and this is what you get. You can avoid $a=n-1$, whenever $t+e>1$. – Jyrki Lahtonen Nov 20 '15 at 15:58