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

130 Views Asked by At

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$?

1

There are 1 best solutions below

2
On BEST ANSWER

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$.