1
$\begingroup$

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?

Thanks.

$\endgroup$
  • 1
    $\begingroup$ Note that $\gcd(k,n) = \gcd(k + n, n)$. $\endgroup$ – Daniel Fischer May 28 '17 at 15:23
  • $\begingroup$ @DanielFischer can you elaborate a bit more on how this relation will help me, please? $\endgroup$ – Kushal Bhuyan May 28 '17 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$ – Daniel Fischer May 28 '17 at 15:32
  • $\begingroup$ @DanielFischer if $m$ is not a multiple of $n$, then how difficult is the problem to solve $\endgroup$ – Kushal Bhuyan May 28 '17 at 16:41
  • 3
    $\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$ – Daniel Fischer May 28 '17 at 17:35
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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