I am working on a problem where it has become important to count (or at least bound from above and below) the number of elements of ${\bf Z}/n{\bf Z}$ that have order less than a given $k$, where $2\leq k\leq n$. In the absence of deeper insights, I proceeded to write this as the sum $$\sum_{j=1}^{k-1} [j\backslash n] \varphi(j),$$ where $[j\backslash n]$ is $1$ if $j$ divides $n$ and $0$ otherwise. If $n$ is prime, then this sum equals $1$ for any $2\leq k\leq n$, and when $k=n$, the sum equals $n-\varphi(n)$. But besides these special cases, I haven't been able to get anything more out of this sum.
There are formulas $$\sum_{j\backslash n} \varphi(j) = n\quad\hbox{and}\quad \sum_{j=1}^{n} \varphi(j) = {3\over \pi^2}n^2 + O\big(n(\log n)^{2/3}(\log\log n)^{4/3}\big),$$ but I'm not too sure how to combine them to tackle my summation. I am not too familiar with the totient function, so perhaps this has been studied before. A reference to an asymptotic result like the one on the right above would be an amazing help. Bounds that work for all $n$ and $k$ would be nice, but it would also be okay if $k$ is not allowed to be too big (e.g. $k\sim\log n$).
The number of elements in a group with order less than a given $k$ seems to be a natural question in group theory, so I might be barking up the wrong tree with this sum. Have any other methods been devised to count it?
