3
$\begingroup$

To calculate the number of integers co-prime to $N$ and less than $N$ we can simply calculate its ETF (Euler's totient function).

However to calculate the number of integers co-prime to $N$ but less than $X$ where $X < N$, how can we modify it using $\phi(N)$ and the prime factorization of $N$?

I know how to calcuate the ETF but can't proceed how to modify it to get the required result.

Thanks.

1 Answers 1

4

One cannot expect a "closed form" formula. But there is a relatively straightforward algorithm, which is easiest to carry out if $N$ has not too many distinct prime factors. It is convenient to let $Y=X-1$. Assume that $Y \ge 1$.

It is clearer to discuss the number $n$ of integers in the interval $[1,Y]$ that are not relatively prime to $N$. Then the number of integers in our interval that are relatively prime to $N$ is $Y-n$.

If $N$ is a power of the prime $p$, then the integers in our interval that are not relatively prime to $N$ are just the multiples of $p$. And there are $\lfloor Y/p\rfloor$ of these, where $\lfloor x\rfloor$ is the "floor" function, the greatest integer which is $\le x$. Thus in this case, $n=\left\lfloor \frac{Y}{p}\right\rfloor.$ Now suppose that $N$ has two distinct prime factors $p$ and $q$. Then $n$ is the number of integers in our interval that are divisible by $p$ or $q$ or both. If we calculate $\lfloor Y/p\rfloor +\lfloor Y/q\rfloor$ we will have counted twice the numbers that are divisible by both $p$ and $q$. So to get the correct count, we must subtract the number of integers in our interval that are divisible by both $p$ and $q$. This is $\lfloor Y/pq\rfloor$. Thus in this case, $n=\left\lfloor \frac{Y}{p}\right\rfloor+\left\lfloor \frac{Y}{q}\right\rfloor-\left\lfloor \frac{Y}{pq}\right\rfloor.$ With more prime divisors, the same general idea can be used. In each case, we use the Principle of Inclusion/Exclusion, which you can look up. For example, if $N$ has $3$ distinct prime divisors $p$, $q$, and $r$, then $n=\left\lfloor \frac{Y}{p}\right\rfloor+\left\lfloor \frac{Y}{q}\right\rfloor+\left\lfloor \frac{Y}{r}\right\rfloor-\left\lfloor \frac{Y}{qr}\right\rfloor -\left\lfloor \frac{Y}{pr}\right\rfloor-\left\lfloor \frac{Y}{pq}\right\rfloor+\left\lfloor \frac{Y}{pqr}\right\rfloor.$ The pattern for general $N$ is the same.

  • 0
    Pentti Haukkanen calls this the Legendre totient $f$unction.2012-10-31