Return to Answer

Let $n=p_1 \dots p_k$, where $p_j$ are distinct primes. Then $$\mu(n)=\mu(p_1 \dots p_k)=\mu(p_1)\dots \mu(p_k).$$ Then to compute $\mu(n)$, it is necessary to compute $\mu(p_j)$ for each $p_j$. This implicitly requires recognizing that $p_1 \dots p_k$ is the prime factorization of $n$.

When $n$ is divisible by a square, you don't have to compute the prime factorization of $n$. But you do have to find a nontrivial factor of $n$: If $n$ is square, in order to determine that it is square, you have to take its square root, in which you find a nontirival factor of $n$. A fortiori, if $n$ is not a square but is still not squarefree, in order to determine that $\mu(n)=0$, it is necessary to find a nontrivial factor of $n$.

Here's an analogy for the squarefree case: In order to know whether there are an odd or even number of jelly beans in a jar, one must count the jelly beans. This is why you must compute the prime factorization of a number to compute its Mobius function, when it is not divisible by a square. But in order to know that there is more than one jelly bean in a jar, one does not need to examine any of the jelly beans in the jar. One can just shake the jar and hear that there is more than one jelly bean. This is why you don't have to factor a number to know it is composite. Algorithms like Fermat's Little Theorem allow one to "shake the number up" to know it is composite.

Here's an analogy for the non-squarefree case: You have a jar of gourmet jelly beans, where there are many different flavors. In order to find whether there are two jelly beans that have the same flavor, you have to find two jelly beans, examine both of them, and find them to have the same flavor. You cannot prove existentially that two jelly beans with the same flavor must exist without knowing the flavor.

Let $n=p_1 \dots p_k$, where $p_j$ are distinct primes. Then $$\mu(n)=\mu(p_1 \dots p_k)=\mu(p_1)\dots \mu(p_k).$$ Then to compute $\mu(n)$, it is necessary to compute $\mu(p_j)$ for each $p_j$. This implicitly requires recognizing that $p_1 \dots p_k$ is the prime factorization of $n$.

Here's an analogy: In order to know whether there are an odd or even number of jelly beans in a jar, one must count the jelly beans. This is why you must compute the prime factorization of a number to compute its Mobius function, when it is not divisible by a square. But in order to know that there is more than one jelly bean in a jar, one does not need to examine any of the jelly beans in the jar. One can just shake the jar and hear that there is more than one jelly bean. This is why you don't have to factor a number to know it is composite. Algorithms like Fermat's Little Theorem allow one to "shake the number up" to know it is composite.

When $n$ is divisible by a square, you don't have to compute the prime factorization of $n$. But you do have to find a nontrivial factor of $n$: If $n$ is square, in order to determine that it is square, you have to take its square root, in which you find a nontirival factor of $n$. A fortiori, if $n$ is not a square but is still not squarefree, in order to determine that $\mu(n)=0$, it is necessary to find a nontrivial factor of $n$.

Let $n=p_1 \dots p_k$, where $p_j$ are distinct primes. Then $$\mu(n)=\mu(p_1 \dots p_k)=\mu(p_1)\dots \mu(p_k).$$ Then to compute $\mu(n)$, it is necessary to compute $\mu(p_j)$ for each $p_j$. This implicitly requires recognizing that $p_1 \dots p_k$ is the prime factorization of $n$.

When $n$ is divisible by a square, you don't have to compute the prime factorization of $n$.

Here's an analogy: In order to know whether there are an odd or even number of jelly beans in a jar, one must count the jelly beans. This is why you must compute the prime factorization of a number to compute its Mobius function, when it is not divisible by a square. But in order to know that there is more than one jelly bean in a jar, one does not need to examine any of the jelly beans in the jar. One can just shake the jar and hear that there is more than one jelly bean. This is why you don't have to factor a number to know it is composite. Algorithms like Fermat's Little Theorem allow one to "shake the number up" to know it is composite.

Let $n=p_1 \dots p_k$, where $p_j$ are distinct primes. Then $$\mu(n)=\mu(p_1 \dots p_k)=\mu(p_1)\dots \mu(p_k).$$ Then to compute $\mu(n)$, it is necessary to compute $\mu(p_j)$ for each $p_j$. This implicitly requires recognizing that $p_1 \dots p_k$ is the prime factorization of $n$.

When $n$ is divisible by a square, you don't have to compute the prime factorization of $n$. But you do have to find a nontrivial factor of $n$: If $n$ is square, in order to determine that it is square, you have to take its square root, in which you find a nontirival factor of $n$. A fortiori, if $n$ is not a square but is still not squarefree, in order to determine that $\mu(n)=0$, it is necessary to find a nontrivial factor of $n$.

Here's an analogy for the squarefree case: In order to know whether there are an odd or even number of jelly beans in a jar, one must count the jelly beans. This is why you must compute the prime factorization of a number to compute its Mobius function, when it is not divisible by a square. But in order to know that there is more than one jelly bean in a jar, one does not need to examine any of the jelly beans in the jar. One can just shake the jar and hear that there is more than one jelly bean. This is why you don't have to factor a number to know it is composite. Algorithms like Fermat's Little Theorem allow one to "shake the number up" to know it is composite.

Here's an analogy for the non-squarefree case: You have a jar of gourmet jelly beans, where there are many different flavors. In order to find whether there are two jelly beans that have the same flavor, you have to find two jelly beans, examine both of them, and find them to have the same flavor. You cannot prove existentially that two jelly beans with the same flavor must exist without knowing the flavor.

Let $n=p_1 \dots p_k$, where $p_j$ are distinct primes. Then $$\mu(n)=\mu(p_1 \dots p_k)=\mu(p_1)\dots \mu(p_k).$$ Then to compute $\mu(n)$, it is necessary to compute $\mu(p_j)$ for each $p_j$. This implicitly requires recognizing that $p_1 \dots p_k$ is the prime factorization of $n$.

When $n$ is divisible by a square, you don't have to compute the prime factorization of $n$.

Let $n=p_1 \dots p_k$, where $p_j$ are distinct primes. Then $$\mu(n)=\mu(p_1 \dots p_k)=\mu(p_1)\dots \mu(p_k).$$ Then to compute $\mu(n)$, it is necessary to compute $\mu(p_j)$ for each $p_j$. This implicitly requires recognizing that $p_1 \dots p_k$ is the prime factorization of $n$.

When $n$ is divisible by a square, you don't have to compute the prime factorization of $n$.

Here's an analogy: In order to know whether there are an odd or even number of jelly beans in a jar, one must count the jelly beans. This is why you must compute the prime factorization of a number to compute its Mobius function, when it is not divisible by a square. But in order to know that there is more than one jelly bean in a jar, one does not need to examine any of the jelly beans in the jar. One can just shake the jar and hear that there is more than one jelly bean. This is why you don't have to factor a number to know it is composite. Algorithms like Fermat's Little Theorem allow one to "shake the number up" to know it is composite.