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
    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.2011-07-31
  • 0
    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.2011-07-31
  • 0
    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$?2011-07-31
  • 0
    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.2011-07-31
  • 0
    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.2011-08-01
  • 0
    It does so by showing $\sum_{d|n}\phi(d)=n$ by listing off $1/n, 2/n,\dots, (n-1)/n$ and reducing to lowest terms, and then uses Moebius inversion. The proof is a sparse one liner, so I don't know how much I can adapt. At this point maybe I'll just "cheat" and use CRT.2011-08-01
  • 0
    Yes, I see. It's possible the authors made a mistake, putting this question so early in the book.2011-08-01
  • 0
    Yes, I hope that's the case. Thanks for taking the time to read through all this.2011-08-01
  • 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