# Counting which values of a polynomial in $\mathbb{Z}[X]$ are coprime to a given integer.

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.

-

EDIT: For the second part, can you see that $f(j)$ is relatively prime to $p$ if and only if it is relatively prime to $p^t$? And that if $f$ is a polynomial with integer coefficients then $f(j+p)$ is relatively prime to $p$ if and only if $f(j)$ is relatively prime to $p$? That should get you started.
OK, then, has there already been a proof that the Euler phi-function is multiplicative? That's the case $f(x)=x$ of your problem. Maybe you could mimic the phi-function proof, just modifying it where necessary. – Gerry Myerson Jul 31 '11 at 9:30
Thanks for your added edit. The first part is clear to me. For the second sentence, I believe this follows since after expanding the terms of $f(j+p)$, it will essentially be $f(j)$ with many added terms which are all multiples of $p$? Is the point then that $1,2,\dots,p^t$ can be divided into $p^{t-1}$ intervals of length $p$, each with $\psi(p)$ integers coprime to $p$ (and hence $p^t$) after applying $f$, for a total of $p^{t-1}\psi(p)$ integers coprime to $p^t$ after applying $f$? – yunone Jul 31 '11 at 10:06
The text derives the formula for $\phi$, and from that I can easily see that $\phi$ is multiplicative. But I don't see how to apply that idea to anything other than monomials in $\mathbb{Z}[X]$ since I don't see how $\phi$ deals with $+$ between terms of a polynomial. Sorry I'm slow, thanks for your help so far. – yunone Jul 31 '11 at 10:09
How does the text derive the formula for phi, without first proving it's multiplicative? Maybe you could follow the derivation of the formula for phi and see if you can warp it to handle the $f$ problem. – Gerry Myerson Aug 1 '11 at 1:43