It's a well known fact of live, that in any field, the roots of $\Phi_n(x)$, the $n$-th cyclotomic polynomial, are exactly the primitive $n$-th roots of unity. Especially the roots of $\Phi_{p-1}(x) %Error. "modp" is a bad command. $ are exactly the primitive roots $\mod p$. And by Vieta, the sum of the roots of a polynomial is the coefficient of $x^{n-1}$, $n$ the polynomial's degree. Thus we look for the coefficient of $x^{\varphi(p-1)-1}$ of $\Phi_{p-1}(x)$, but by it's symmetry we can also look for the coefficient of $x$. So we search for $\Phi_n^\prime(0)$ (we take arbitrary $n$ instead of $p-1$). Deriving the recursive formulas $\Phi_{pn}(x) = \frac{\Phi_n(x^p)}{\Phi_n(x)}$ iff $p\nmid n$ and $\Phi_{pn}(x) = \Phi_n(x^p)$ iff $p|n$, we get our result $\mu(n)=\Phi_n^\prime(0)$ by induction on prime divisors.

Another way to conclude: let $f(n)$ be the coefficient of $x^{n-1}$ in $\Phi_n(x)$, or the sum of the roots of $\Phi_n(x)$. We know that $\prod_{d \mid n} \Phi_d(x) = x^n-1$. If we just compare the sum of the roots of the polynomials in LHS and RHS, we get: $\sum_{d \mid n} f(d) = 0$ if n > 1, and $f(1) = 1$. But this is a definition of $\mu$!!

Are there any elementary solutions? I guess this isn't well known to high school students.

I don't see anything nonelementary (the polynomials pop out if you start thinking about it). And to be known for high school students can't be a good way to judge as even Fermat's little theorem isn't known to them...

FLT is standard part of any olympiad training. This isn't, at least it's not in any of the standard olympiad books I have here... Seriously, I heared about this for the first time in second year of university...

Not the cyclotomic polynomials itself occure, but the polynomials with roots the $ g_i$ (and they are the same). After some more work, one considers the other ones, too. I agree that the problem gets a lot easier if you know them, but primitive roots are in their nature primitive roots of unity. And if some training doesn't consider them, then they should be added

Filling in an elementary solution void here... $ \sum_{(a,p - 1) = 1,1\le a\le p - 1}g^a$ is what we have to evaluate, where $ g$ is one of the primitive roots. Let $ k$ be the number of distinct prime factors of $ p - 1$. Now, by PIE (Principle of Inclusion Exclusion) this is equivalent to $ 1 + g + g^2 + ... + g^{p - 1} - \sum_{a|p - 1, a prime} (1 + g^a + g^{2a} + ... + g^{p - 1}) + \sum_{a,b|p - 1, a < b primes} - ... + ( - 1)^{k}(1 + g^{\Pi prime factors} + g^{2\Pi prime factors} + ... + g^{p - 1})$. All but the last term definitely evaluate to 0 by the sum of a geometric series (using $ g^p\equiv 1$ mod p), and the final term turns out to be $ \mu(p - 1)$ mod p upon inspection, hence the desired result. Cheers, Rofler

$ \sum_{(a,p - 1) = 1,1\le a\le p - 1}g^a=$$ 1 + g + g^2 + ... + g^{p - 1} - \sum_{a|p - 1, a prime} (1 + g^a + g^{2a} + ... + g^{p - 1}) + \sum_{a,b|p - 1, a < b primes} - ... + ( - 1)^{k}(1 + g^{\Pi prime factors} + g^{2\Pi prime factors} + ... + g^{p - 1})=\mu(p-1)$