Euler's totient function for a prime power input can be written as follows:

$$\phi(p_n^k) = (p_n - 1)p_{k-1}$$

This function counts those numbers that are smaller than $p_n^k$ but which are also relatively prime to it. Take notice of that; both the upper-bound on the numbers which are counted by this function and the number to which the countable elements are relatively prime are equal to each other (note that this is one way of looking at it; another, probably more accurate way, is to see the totient as returning the size of any reduced residue system modulo it's input, regardless of whether the elements of that system are smaller than or larger than the input).

Is there a way to count those numbers smaller than an integer $x < p_n^k$ which are relatively prime with $p_n^k$?


Let $y$ be a positive integer. The number of integers in the interval $1$ to $y$ which are divisible by the prime $p$ is $\left\lfloor \frac{y}{p}\right\rfloor$. (We are using the "floor," aka the "greatest integer" function.) So the number of integers in the interval from $1$ to $y$ which are relatively prime to $p$ is $$y-\left\lfloor \frac{y}{p}\right\rfloor.$$

Your question asks about integers less than $x$. So in the expression above, replace $y$ by $x-1$.

  • $\begingroup$ Excellent answer! Been banging my head on this for a while now. While it isn't what I was expecting, this is very useful to my current research. Thanks. $\endgroup$ – Adam Aug 25 '13 at 20:26
  • $\begingroup$ You are welcome. Note that by taking $y=p^k$ we get $p^k-p^{k-1}=(p-1)p^{k-1}$, the usual $\varphi$-function formula. $\endgroup$ – André Nicolas Aug 25 '13 at 20:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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