8
$\begingroup$

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.

1 Answers 1

5

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.

  • 0
    This is generalization of $phi(n)$ by P. Kevasa Menon labeled $\phi_f(n)$ and defined as the number of integers x (mod n) such that (f(x),n)=1. Some resources Maybe one doesn't use CRT: P. Kesava Menon, An extension of Euler's function, Math Student 35(1967), 55-59 H. Stevens, Generalizations of the Euler Á -function, Duke Math. J. 38(1971), 181-186. J. Chidambaraswamy, Totients with respect to a polynomial, Indian J. Pure Appl. Math. 5(1974), 601-608. J. Chidambaraswamy, Totients and unitary totients with respect to a set of polyno-mials, Indian J. Pure Appl. Math 10(1979), 287-302.2012-08-15