I need a hint for this question please: Find the sum of the orders mod 83 over all elements of the set $\{1,2,3,\ldots,82\}$. (If multiple elements have the same order, add that term multiple times.)
I figured out that all numbers except $1$ (has order $1$) and $82$ (has order $2$) must have orders of $41$ or $82$. But how do I know how many numbers with orders of $41$ or $82$ there are?
83 is prime, so the multiplicative group is equivalent to the cyclic group with $\phi(83)=82$ elements. In a cyclic group of order $n$, there are $\phi(d)$ elements of order $d$ (where $d$ must divide $n$). So the answer is $\sum_{d|n}d\phi(d)$. I'm not sure if there's a closed expression for this, but with $n=82$, I get 4923.