In the abelian group $\Z/n$, the order of $m\in \Z/n$ can be calculated via the formula $n/{\rm gcd}(m,n)$. This number is just the smallest number you have to multiply $m$ by in order to get a multiple of $n$. So when $n = p$ is a prime, every we see that every nonzero element of $\Z/p$ has order $p$.
However, every nonzero element of $\Z/p$ is prime to $p$, and the nonzero elements of $\Z/p$ form the abelian multiplicative group $\Z/p^\times$ of invertible elements. Then the order of an element $m\in \Z/p^\times$ is a little more tricky to figure out, but we know by Fermat’s Little Theorem that it will be a factor of $p-1$.
This example has a curious property that you may not know about. It is true that $3^5 = 1$ in $\Z/11$. But did you know that $3^5 = 1$ in $\Z/121$? What?! This leads to a natural question:
Not all primes have this property. Consider $p = 5$. Then $3^4 = 1$ in $\Z/5$. However, $3^4 = 6$ in $\Z/25$. In fact, none of the elements $2,3,4$ have the same order in both $\Z/5^\times$ and $\Z/25^\times$. Here are some primes that do have such elements:
So, there are quite a few of them and maybe there are infinitely many. One can go further with this question: what about primes for which there are non-trivial elements in $\Z/p^\times$ with the same order in $\Z/p^\times, {\Z/p^2}^\times,$ and ${\Z/p^3}^\times$? There are fewer of these. But they exist. For example, the identity
$$68^{112} = 1$$
Holds in $\Z/113^k$ for $k=1,2,3$ (but not for $k=4$). This is the only example I know of and maybe it is the only possible example? But I probably just haven’t looked far enough. I wrote the original program to find it in Python but I plan to rewrite it in C with the gmp library to expand the search.
