# Counting elements of reduced residue systems modulo one number which are smaller than another

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$.
• 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. – André Nicolas Aug 25 '13 at 20:31