Proving that a function is multiplicative.

Question

Let $f(x)$ be a polynomial with integral coefficients, and let $\psi(n)$ denote the numbers of values $f(0), f(1), ..., f(n-1)$ which are coprime to $n$.

I must show that $\psi$ is multiplicative, meaning that: $$\psi(mn) = \psi(m) \cdot \psi(n)$$ assuming $\gcd(m,n)=1$.

Furthermore, I must show that $$\psi(p^\alpha) = p^{\alpha-1} \cdot (p-b_p)$$ where $b_p$ is the number of integers $f(0), f(1), ..., f(p-1)$ which are divisible by the prime $p$.

I thought that this proof would be similar to the proof of multiplicity for Euler's totient function, but I have not been able to make the connection. I think once I find a proof for the first part, maybe I will be better able to understand the second part. Any help is appreciated!

Answer 1

Hint:

Use the fact that $\psi(m)$ equals the number of units in the multiplicative group $Z_m^{\times}$. Since $m$ and $n$ are coprime, $ Z_{mn}^{\times}\cong Z_m^{\times}\times Z_n^{\times}$. Thus there is $ \psi(mn)=\psi(m)\psi(n)$.

Answer 2

We start with a lemma.

Lemma: Let $p$ be a prime number. Then for every $f(x)\in \mathbb{Z}[x]$ and $k\in \mathbb{Z}$ $$f(p+k)\equiv f(k) \pmod p.$$

Proof: Let's suppose that $f(x)=c_{0}x^n+\ldots +c_{1}x+c_{n}$, then $$f(p+k)=c_{0}(p+k)^n+\ldots c_{1}(p+k)+c_{n}\equiv c_{0}k^n+\ldots c_{1}k+c_{n}=f(k) \pmod p. \tag*{$\blacksquare$}$$

First, let's take $n=p^a$, we can make $p^a/p=p^{a-1}$ groups of $p$ elements in the set $\{f(0), f(1),\ldots, f(p-1), f(p),\ldots, f(2p-1),\ldots, f(p^a-p),\ldots, f(p^a-1)\}$. By the lemma each group has $b_{p}$ numbers which are divisible by $p$. Then, in total we have $p^a-p^{a-1}\cdot b_{p}=p^{a-1}(p-b_{p})$ numbers which aren't divisibles by $p$, i.e. coprime with $p^a$. So, $\psi(p^a)=p^{a-1}(p-b_{p})$.

Now, let's suppose that $n=p_{1}^{a_{1}}\cdots p_{r}^{a_{r}}$, the idea is to apply the previous reasoning for each prime factor $p_{i}$, but to avoid repetitions, i.e., numbers which are multiple of more than one prime factor, we'll successively be subtracting the multiples of $p_{i}$, starting with $p_{1}$.

Set $n=n_{0}$, and pick $p_{1}$, the number of multiples of $p_{1}$ is $$m_{1}=(p_{1}^{a_{1}}\cdots p_{r}^{a_{r}}/p_{1})\cdot b_{p_{1}}=p_{1}^{a_{1}-1}\cdots p_{r}^{a_{r}}b_{p_{1}},$$ then we put $n_{1}=n_{0}-m_{1}=p_{1}^{a_{1}}\cdots p_{r}^{a_{r}}-p_{1}^{a_{1}-1}\cdots p_{r}^{a_{r}}b_{p_{1}}=p_{1}^{a_{1}-1}\cdots p_{r}^{a_{r}}(p_{1}-b_{p_{1}})$.

Now, for $n_{1}$ we count the number of multiples of $p_{2}$. As in the case of $p_{1}$ we have $m_{2}=p_{1}^{a_{1}-1}p_{2}^{a_{2}-1}\cdots p_{r}^{a_{r}}(p-b_{p_{1}})b_{p_{2}}$, and thus $$n_{2}=n_{1}-m_{2}=p_{1}^{a_{1}-1}\cdots p_{r}^{a_{r}}(p-b_{p})-p_{1}^{a_{1}-1}p_{2}^{a_{2}-1}\cdots p_{r}^{a_{r}}(p-b_{p_{1}})b_{p_{2}}=$$ $$p_{1}^{a_{1}-1}p_{2}^{a_{2}-1}\cdots p_{r}^{a_{r}}(p-b_{p_{1}})(p_{2}-b_{p_{2}}).$$

After applying the same process $r-2$ more times, we deduce that $$\psi(n)=n_{r}=n_{r-1}-m_{r}=$$ $$=p_{1}^{a_{1}-1}\cdots p_{r}^{a_{r}}(p_{1}-b_{p_{1}})\ldots (p_{r-1}-b_{p_{r-1}})-p_{1}^{a_{1}-1}\cdots p_{r}^{a_{r}-1}(p_{1}-b_{p_{1}})\ldots (p_{r-1}-b_{p_{r-1}})b_{p_{r}}=$$ $$=p_{1}^{a_{1}-1}\cdots p_{r}^{a_{r}-1}(p_{1}-b_{p_{1}})\ldots (p_{r}-b_{p_{r}}).$$

Finally, applying the last formula it's easy to deduce that if $\gcd(m,n)=1$, then $$\psi(mn)=\psi(m)\psi(n).$$

Note: If the process isn't very clear I recommend you to apply it to $n=30$.