Let $m$ and $n$ be two integers such that $m>n$. Then find the number of integers less than $m$ and relatively prime to $n$.

I had come across a problem of this type with specific values for $m$ and $n$, unfortunately, the values I don't remember anymore. So I asked this general question. How to solve this type of question?

My thoughts are that we need to count the numbers. So we can count the number of integers less than $m$ and relatively prime to $m$ using Euler's totient function. Now among those numbers, also belongs the numbers which are relatively prime to $n$. We can also find the numbers less than $n$ and relatively prime to $n$. That will give a rough estimation. But how do we know about the actual number of such integers? Can anybody help me with this?


  • 1
    $\begingroup$ Note that $\gcd(k,n) = \gcd(k + n, n)$. $\endgroup$ Commented May 28, 2017 at 15:23
  • $\begingroup$ @DanielFischer can you elaborate a bit more on how this relation will help me, please? $\endgroup$ Commented May 28, 2017 at 15:29
  • $\begingroup$ It tells you how many integers $an < k \leqslant (a+1)n$ are coprime to $n$. If $m$ is a multiple of $n$, that finishes it. If $m = q\cdot n + r$ with $0 < r < n$, the remaining part of the problem is difficult. $\endgroup$ Commented May 28, 2017 at 15:32
  • $\begingroup$ @DanielFischer if $m$ is not a multiple of $n$, then how difficult is the problem to solve $\endgroup$ Commented May 28, 2017 at 16:41
  • 4
    $\begingroup$ Let us define $\Phi(n,m)$ as the number of positive integers coprime to $n$ and not exceeding $m$. Then the above gives us $$\Phi(n,m) = \biggl\lfloor \frac{m}{n}\biggr\rfloor\cdot \varphi(n) + \Phi\biggl(n, m - n\cdot \biggl\lfloor \frac{m}{n}\biggr\rfloor\Biggr).$$ Assuming one knows $\varphi(n)$, the problem is then to find $\Phi(n,r)$ for $0 \leqslant r < n$. If the numbers coprime to $n$ were evenly distributed, then $\Phi(n,r)$ would be close to $\frac{r}{n-1}\cdot \varphi(n)$. But since the numbers coprime to $n$ are in general not very close to being evenly distributed, $\endgroup$ Commented May 28, 2017 at 17:35

1 Answer 1


If primes $p_1, p_2$ are the only prime factors of $n$, then we get numbers relatively prime to $n$ and less than $m$ are (assuming $p_1, p_2$ are not factors of $m$):

$$m - \lfloor\frac{m}{p_1}\rfloor - \lfloor\frac{m}{p_2}\rfloor + \lfloor\frac{m}{p_1p_2}\rfloor$$

We can have a generalized expression for any number of prime factors of $n$ using PIE.


You must log in to answer this question.

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