Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
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. –  Rick Sladkey Oct 27 '12 at 18:04
    
So this takes as long as factoring N, right? (plus, the computation of the terms in the sum) –  Mitch Oct 27 '12 at 18:34
    
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$. –  André Nicolas Oct 27 '12 at 18:48
1  
@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) –  André Nicolas Oct 27 '12 at 20:39
1  
(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$. –  André Nicolas Oct 27 '12 at 20:43
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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