# Möbius function help

Given some large random integer k, how much longer would it take to determine the primality of k, then to calculate mobius(k), and how much longer would it take to factor k, then to calculate mobius(k). I saw some formula that had to do with primitive roots to calculate mobius(k), but I don't understand why it works nor how or how much faster it is, then say trying to factor the integer k.

-

I think the formula you're looking for involves Ramanujan sums, where $$c_q(n)= \sum_{a=1}_{(a,q)=1}^{q}e^{2\pi i\frac{a}{q}n} = \mu(n)$$ if $(n,q)=1$, where $\mu(n)$ is your Möbius function. I actually saw this today and was thinking the same thing; it's an interesting result, but is it any faster for primality testing? I don't know, we're looking at things of this form to get a hold on Goldbach's conjecture. Should be a comment, but there was no way the sum term would be readable in comment-form.
It cannot be faster than primality testing in the case where $n$ is suspected to be either prime or the product of two primes, can it? –  Hagen von Eitzen Nov 23 '12 at 6:53
Clearly if $n$ is suspected to be either prime of the product of two primes than the Mobius function would be able to determine primality of $n$.. and this looks like a pretty fast way to calculate $\mu$ –  user45793 Nov 23 '12 at 7:04
Something seriously wrong here. If $n$ is odd, you can take $q=2$, and the formula says $\mu(n)=e^{\pi in}=-1$. Please check your source. –  Gerry Myerson Nov 23 '12 at 11:49
@GerryMyerson it should be the sum of the primitive nth roots of unity $\mu(n)=\sum_{k}e^{2\pi i k/n}$, where k ranges over the integers coprime to n –  Ethan Mar 28 '13 at 5:45
My understanding is that no one knows a way to calculate $\mu(n)$ guaranteed to be significantly faster than fully factoring $n$ into primes. Determining primality is much faster than factoring, hence, faster than computing $\mu$.