Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 5 down vote accepted

For the first part of the problem, I think what you're missing is the Chinese Remainder Theorem.

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.

share|cite|improve this answer
Thanks, I hadn't thought of that, but I'm hoping to avoid CRT since it isn't introduced until Section 4 of Chapter 3. – yunone Jul 31 '11 at 6:42
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.