The following problem is from Ireland and Rosen's Intro to Modern Number Theory, Exercise 23 Chapter 2.
Let $f(x)\in\mathbb{Z}[X]$ and let $\psi(n)$ be the number of $f(j)$, $j=1,2,\dots,n$ such that $(f(j),n)=1$. Show that $\psi(n)$ is multiplicative and that $\psi(p^t)=p^{t-1}\psi(p)$. Conclude that $\psi(n)=n\prod_{p|n}\psi(p)/p$.
I've been thinking about this on and off today, and I haven't even made much progress on the first part showing $\psi$ is multiplicative. I tried working out a few examples to get a feel. Let $\Psi(n)$ be the set of numbers $j$ such that $(f(j),n)=1$. Taking $f(x)=x^2+1$, I found that $\psi(6)=3$, and $\Psi(6)=\{2,4,6\}$. Also $\Psi(2)=\{2\}$ and $\Psi(3)=\{1,2,3\}$. This led me to guess that $\psi(ab)=\psi(a)\psi(b)$ when $(a,b)=1$ just by multiplying elements pairwise from $\Psi(a)$ and $\Psi(b)$ to get the elements in $\Psi(ab)$.
But I tried another calculation with $f(x)=x^2+2x+2$, and found $\Psi(6)=\{1,3,5\}$ but $\Psi(2)=\{1\}$ and $\Psi(3)=\{1,2,3\}$, so my idea doesn't work.
I do see that once I know that $\psi(p^t)=p^{t-1}\psi(p)$, then since $\psi$ is multiplicative, then $ \psi(n)=\prod_{p|n}\psi(p^t)=\prod_{p|n}p^{t-1}\psi(p)=\prod_{p|n}p^t\psi(p)/p=n\prod_{p|n}\psi(p)/p. $
Edit: With Gerry Myerson's help, I see that $\psi(p^t)=p^{t-1}\psi(p)$, for if $a_1,\dots, a_{\psi(p)}$ are all such that $(f(a_i),p)=(f(a_i),p^t)=1$, then the same holds for $a_1+kp,\dots, a_{\psi(p)}+kp$ for $k=1,2,\dots,p^{t-1}$.
I don't see how $\psi$ is multiplicative in first place. Why is that? Thanks.