A problem on Möbius function

95 Views Asked by At

Here is an exercise from the text book "Combinatorics" (J.H.van Lint, R.M. Wilson)

Let $f_n(z)$ be the function that has all its zeros as all the numbers $\alpha$ for which $\alpha^n=1$ but $\alpha^k\ne1$ for $1\leq k\leq n$. Prove that $$f_n(z)=\prod\limits_{k|n}(z^k-1)^{\mu (n/k)}.$$

1

There are 1 best solutions below

2
On BEST ANSWER

denote $\alpha$ the primitive root of nth unit, then the n roots are $\alpha^i$, $i=1\dots n$ and $\alpha^n=1$. denote $(x,y)=gcd(x,y)$.

so

$$z^n-1=\prod_{i=1}^{n}(z-\alpha^i)$$

then we focus on what $f_n(z)$ is like, the root of $f_n(z)$ is something like $\alpha^i$, then we find out what $i$ is in $f_n(z)$

if $(i,n)=d>1$, that is to say we have a root $\alpha^i$ in $f_n(z)$, then

$$ (\alpha^i)^{\frac{n}{d}}=(\alpha^{\frac{i}{d}})^n=1 $$

but $n/d<n$, which violate the defination of $f_n(z)$

so

$$ f_n(z)=\prod_{(i,n)=1}(z-\alpha^i) $$

then we take a deep look at $z^n-1$

$$ z^n-1=\prod_{i=1}^{n}(z-\alpha^i)=\prod_{d|n}\prod_{(i,n)=d}(z-\alpha^i)=\prod_{d|n}\prod_{(i/d,n/d)=1}(z-(\alpha^d)^{i/d})=\prod_{d|n}f_{n/d}(z)=\prod_{d|n}f_d(z) $$

then we can use Möbius inversion formula, and get

$$ f_n(z)=\prod\limits_{d|n}(z^d-1)^{\mu (n/d)} $$