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.

$\endgroup$

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ For reference, the general formula for the number that are coprime is $\sum_{d|N}{\mu(d)\left \lfloor \frac{X-1}{d} \right \rfloor}$, where $\mu(n)$ is the Möbius function. $\endgroup$ Commented Oct 27, 2012 at 18:04
  • $\begingroup$ So this takes as long as factoring N, right? (plus, the computation of the terms in the sum) $\endgroup$
    – Mitch
    Commented Oct 27, 2012 at 18:34
  • $\begingroup$ Bumping into the factorization issue is inevitable. For example, if $N$ is the product of two (unknown) distinct primes, and we know $\varphi(n)=(p-1)(q-1)=pq-p-q+1$, then we can calculate $p+q$, and then cheaply $p$ and $q$. $\endgroup$ Commented Oct 27, 2012 at 18:48
  • 1
    $\begingroup$ @My previous comment was just saying that to compute $\varphi(N)$ we need to know the prime factorization of $N$, which for huge $N$ may be computationally difficult. But assume we know the prime factorization, as your post says to. The problem of number of relatively primes is a different when $x\lt N$ than when $x$ is much bigger than $N$. For $\lt N$ it is as in my answer above, or in the comment by Rick Sladkey, which is essentially the same calculation. For $x$ much bigger than $N$, first divide $x$ by $N$, $x=qN+r$. For the relatively primes, the number is $q\varphi(N)$, plus (cont) $\endgroup$ Commented Oct 27, 2012 at 20:39
  • 1
    $\begingroup$ (cont) the relatively primes from $qN+1$ to $qN+r$, which is the same as the number from $1$ to $r$. That part is computed as in the main post. That can help by making the numbers much smaller, making the exact integer arithmetic cheaper. This only matters for enormous $x$. $\endgroup$ Commented Oct 27, 2012 at 20:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .