# Median order of an element in an additive group modulo $n$

I'm trying to gain some intuition here. Suppose we have the group $\mathbb{Z}_{n}$ (with the operation being addition modulo $n$). What is the median order of an element of this group when $n$ is a randomly chosen large number? I realize that when $n$ is prime, the median order will be $n$, because all elements other than the identity have order $n$. Also, are there any special values of $n$ that make the median order very small relative to $n$ (say $O(\log n)$)?

If this sounds vague, here is a more concrete explanation of my question: Given a number $n$, let $\alpha(n)$ denote the median order of all elements of the group $\mathbb{Z}_n$. Are there any special values of $n$ (say, $m!$ or $p^m$ for a prime $p$, or something like that) for which $\alpha(n)$ is very small compared to $n$? What if $n$ is a randomly chosen large number? What would you expect the value of $\alpha(n)$ to be? Would it be of the order of $n$?

The key fact, which is worth verifying yourself, is that there are exactly $\phi(d)$ elements of order $d$ in $\Bbb Z_n$ for every $d$ dividing $n$. (Here, $\phi$ is the Euler phi function.)
This allows us to say a lot about questions like this. For example, the mean order is exactly $\frac1n \sum_{d\mid n} d\phi(d)$, which is clearly greater than $\phi(n)$ (just the $d=n$ term alone is that big); one can show that this mean order is also at most $\frac{\pi^2}6\phi(n)$.
Suppose that $M$ is the median order of elements in $\Bbb Z_n$. Then the number of elements of order at most $M$ is at least $n/2$; but by the above, it's also at most $$\sum_{d\le M} \phi(d) \sim \frac3{\pi^2} M^2$$ by a classical result about the summatory function of the Euler phi function. Therefore we must have $$M \gtrsim \sqrt{\frac{\pi^2}6n};$$ in particular, $M=O(\log n)$ isn't possible.
Note that there's a lot of waste in that argument, because it's impossible for all the numbers up to $\sqrt n$ to divide $n$. So there's definitely room for improvement. I suspect that the median order is not $O(n^{1-\epsilon})$ for any $\epsilon>0$.
On the other hand, if the median order is $n/K$, then there are only $K$ possible divisors of $n$ greater than or equal to $n/K$, and the Euler phi function applied to each such divisor is at most $\phi(n)$ (since $\phi(d) \mid \phi(n)$ when $d\mid n$). Therefore the number of elements of order at least $n/K$ is at most $K\phi(n)$, while it must be at least $n/2$. Therefore the median order $M=n/K$ also satisfies $$M \le 2\phi(n).$$ In particular, there are infinitely many integers $n$ such that $M \lesssim 2e^{-\gamma}n/\log\log n$, by a classical result about the maximal order of $n/\phi(n)$ (here $\gamma$ is Euler's constant). I suspect this is reasonably close to the truth - perhaps the right minimal order for the median is something like $n/(\log n)^A$ for some constant $A$.
One more comment: the median order can be smaller than $\phi(n)$ by an arbitrary factor. If $n$ is the product of all the primes between $z$ and $z^{2/(1-2\epsilon)}$, then $\phi(n)/n \sim \frac12-\epsilon$, which means that the median order is strictly smaller than $n$; however, the largest proper divisor of $n$ is $n/z$, so the median order is smaller than $\phi(n)$ by a factor of nearly $z/2$. In fact, since $\log n \sim z^{2/(1-2\epsilon)}$ in this construction, this gives examples where the median order is at most $n/(\log n)^{1/2-\epsilon}$. (And the $\epsilon$ could easily be made quantitative here.)